""" 0225.1 - Implement Stack using Queues - Solution 1 - Single Queue (Push Costly) """
#####################################################################################
# Imports
#####################################################################################
from collections import deque
#####################################################################################
# Classes
#####################################################################################
class MyStack:
"""Stack implementation using a single queue."""
def __init__(self):
self.q = deque()
def push(self, x: int) -> None:
"""Push element x onto stack."""
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self) -> int:
"""Remove and return the top element."""
return self.q.popleft()
def top(self) -> int:
"""Return the top element without removing it."""
return self.q[0]
def empty(self) -> bool:
"""Return True if the stack is empty."""
return len(self.q) == 0
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
stack = MyStack()
stack.push(1)
stack.push(2)
print(stack.top()) # 2
print(stack.pop()) # 2
print(stack.empty()) # False
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
/** 0225.1 - Implement Stack using Queues - Solution 1 - Single Queue (Push Costly) */
/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class MyStack {
constructor() {
this.q = [];
}
push(x) {
this.q.push(x);
for (let i = 0; i < this.q.length - 1; i++) {
this.q.push(this.q.shift());
}
}
pop() {
return this.q.shift();
}
top() {
return this.q[0];
}
empty() {
return this.q.length === 0;
}
}
const s = new MyStack();
s.push(1);
s.push(2);
console.log(s.top()); // 2
console.log(s.pop()); // 2
console.log(s.empty()); // false
/** 0225.1 - Implement Stack using Queues - Solution 1 - Single Queue (Push Costly) */
/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class MyStack {
private q: number[] = [];
push(x: number): void {
this.q.push(x);
for (let i = 0; i < this.q.length - 1; i++) {
this.q.push(this.q.shift() as number);
}
}
pop(): number {
return this.q.shift() as number;
}
top(): number {
return this.q[0];
}
empty(): boolean {
return this.q.length === 0;
}
}
const s: MyStack = new MyStack();
s.push(1);
s.push(2);
console.log(s.top());
console.log(s.pop());
console.log(s.empty());
// 0225.1 - Implement Stack using Queues - Solution 1 - Single Queue (Push Costly)
package main
import "fmt"
type MyStack struct {
q []int
}
func Constructor() MyStack {
return MyStack{q: []int{}}
}
func (this *MyStack) Push(x int) {
this.q = append(this.q, x)
for i := 0; i < len(this.q)-1; i++ {
this.q = append(this.q, this.q[0])
this.q = this.q[1:]
}
}
func (this *MyStack) Pop() int {
top := this.q[0]
this.q = this.q[1:]
return top
}
func (this *MyStack) Top() int {
return this.q[0]
}
func (this *MyStack) Empty() bool {
return len(this.q) == 0
}
func main() {
s := Constructor()
s.Push(1)
s.Push(2)
fmt.Println(s.Top()) // 2
fmt.Println(s.Pop()) // 2
fmt.Println(s.Empty()) // false
}
// 0225.1 - Implement Stack using Queues - Solution 1 - Single Queue (Push Costly)
use std::collections::VecDeque;
struct MyStack {
q: VecDeque<i32>,
}
impl MyStack {
fn new() -> Self {
Self { q: VecDeque::new() }
}
fn push(&mut self, x: i32) {
self.q.push_back(x);
for _ in 0..self.q.len() - 1 {
let v = self.q.pop_front().unwrap();
self.q.push_back(v);
}
}
fn pop(&mut self) -> i32 {
self.q.pop_front().unwrap()
}
fn top(&self) -> i32 {
*self.q.front().unwrap()
}
fn empty(&self) -> bool {
self.q.is_empty()
}
}
fn main() {
let mut s = MyStack::new();
s.push(1);
s.push(2);
println!("{}", s.top());
println!("{}", s.pop());
println!("{}", s.empty());
}
""" 0225.2 - Implement Stack using Queues - Solution 2 - Two Queues (Push Costly) """
#####################################################################################
# Imports
#####################################################################################
from collections import deque
#####################################################################################
# Classes
#####################################################################################
class MyStack:
"""Stack implementation using two queues."""
def __init__(self):
self.q1 = deque()
self.q2 = deque()
def push(self, x: int) -> None:
"""Push element x onto stack."""
self.q2.append(x)
while self.q1:
self.q2.append(self.q1.popleft())
self.q1, self.q2 = self.q2, self.q1
def pop(self) -> int:
"""Remove and return the top element."""
return self.q1.popleft()
def top(self) -> int:
"""Return the top element without removing it."""
return self.q1[0]
def empty(self) -> bool:
"""Return True if the stack is empty."""
return len(self.q1) == 0
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
stack = MyStack()
stack.push(1)
stack.push(2)
print(stack.top()) # 2
print(stack.pop()) # 2
print(stack.empty()) # False
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
/** 0225.2 - Implement Stack using Queues - Solution 2 - Two Queues (Push Costly) */
/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class MyStack {
constructor() {
this.q1 = [];
this.q2 = [];
}
push(x) {
this.q2.push(x);
while (this.q1.length) this.q2.push(this.q1.shift());
[this.q1, this.q2] = [this.q2, this.q1];
}
pop() {
return this.q1.shift();
}
top() {
return this.q1[0];
}
empty() {
return this.q1.length === 0;
}
}
/** 0225.2 - Implement Stack using Queues - Solution 2 - Two Queues (Push Costly) */
/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class MyStack {
private q1: number[] = [];
private q2: number[] = [];
push(x: number): void {
this.q2.push(x);
while (this.q1.length) this.q2.push(this.q1.shift() as number);
[this.q1, this.q2] = [this.q2, this.q1];
}
pop(): number {
return this.q1.shift() as number;
}
top(): number {
return this.q1[0];
}
empty(): boolean {
return this.q1.length === 0;
}
}
// 0225.2 - Implement Stack using Queues - Solution 2 - Two Queues (Push Costly)
package main
import "fmt"
type MyStack struct {
q1 []int
q2 []int
}
func Constructor2() MyStack {
return MyStack{q1: []int{}, q2: []int{}}
}
func (this *MyStack) Push(x int) {
this.q2 = append(this.q2, x)
this.q2 = append(this.q2, this.q1...)
this.q1 = this.q2
this.q2 = []int{}
}
func (this *MyStack) Pop() int {
top := this.q1[0]
this.q1 = this.q1[1:]
return top
}
func (this *MyStack) Top() int {
return this.q1[0]
}
func (this *MyStack) Empty() bool {
return len(this.q1) == 0
}
func main() {
s := Constructor2()
s.Push(1)
s.Push(2)
fmt.Println(s.Top())
fmt.Println(s.Pop())
fmt.Println(s.Empty())
}
// 0225.2 - Implement Stack using Queues - Solution 2 - Two Queues (Push Costly)
use std::collections::VecDeque;
struct MyStack {
q1: VecDeque<i32>,
q2: VecDeque<i32>,
}
impl MyStack {
fn new() -> Self {
Self { q1: VecDeque::new(), q2: VecDeque::new() }
}
fn push(&mut self, x: i32) {
self.q2.push_back(x);
while let Some(v) = self.q1.pop_front() {
self.q2.push_back(v);
}
std::mem::swap(&mut self.q1, &mut self.q2);
}
fn pop(&mut self) -> i32 {
self.q1.pop_front().unwrap()
}
fn top(&self) -> i32 {
*self.q1.front().unwrap()
}
fn empty(&self) -> bool {
self.q1.is_empty()
}
}
