# 225. Implement Stack using Queues

## Description

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False


Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, top, and empty.
• All the calls to pop and top are valid.

Follow-up: Can you implement the stack using only one queue?

## Solutions

Solution 1: Two Queues

We use two queues $q_1$ and $q_2$, where $q_1$ is used to store the elements in the stack, and $q_2$ is used to assist in implementing the stack operations.

• push operation: Push the element into $q_2$, then pop the elements in $q_1$ one by one and push them into $q_2$, finally swap the references of $q_1$ and $q_2$. The time complexity is $O(n)$.
• pop operation: Directly pop the front element of $q_1$. The time complexity is $O(1)$.
• top operation: Directly return the front element of $q_1$. The time complexity is $O(1)$.
• empty operation: Check whether $q_1$ is empty. The time complexity is $O(1)$.

The space complexity is $O(n)$, where $n$ is the number of elements in the stack.

• import java.util.Deque;

class MyStack {
private Deque<Integer> q1 = new ArrayDeque<>();
private Deque<Integer> q2 = new ArrayDeque<>();

public MyStack() {
}

public void push(int x) {
q2.offer(x);
while (!q1.isEmpty()) {
q2.offer(q1.poll());
}
Deque<Integer> q = q1;
q1 = q2;
q2 = q;
}

public int pop() {
return q1.poll();
}

public int top() {
return q1.peek();
}

public boolean empty() {
return q1.isEmpty();
}
}

/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/

• class MyStack {
public:
MyStack() {
}

void push(int x) {
q2.push(x);
while (!q1.empty()) {
q2.push(q1.front());
q1.pop();
}
swap(q1, q2);
}

int pop() {
int x = q1.front();
q1.pop();
return x;
}

int top() {
return q1.front();
}

bool empty() {
return q1.empty();
}

private:
queue<int> q1;
queue<int> q2;
};

/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/

• # one queue

'''
push(1), [1]
push(2), [1,2] => [2,1]
push(3), [2,1,3] => [1,3,2] => [3,2,1]
push(4), [3,2,1,4] => switch 3 time to get [4,3,2,1]
push(5), [4,3,2,1,5] => switch 4 time to get [5,4,3,2,1]
'''
class Stack:

def __init__(self):
self._queue = collections.deque()

def push(self, x):
q = self._queue
q.append(x)
for _ in range(len(q) - 1):
q.append(q.popleft())

def pop(self):
return self._queue.popleft()

def top(self):
return self._queue[0]

def empty(self):
return not len(self._queue)

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

############

from collections import deque

# two queues
class MyStack:

def __init__(self):
self.q1 = deque()
self.q2 = deque()

def push(self, x: int) -> None:
self.q1.append(x)

def pop(self) -> int:
while len(self.q1) != 1:
self.q2.append(self.q1.popleft())

val = self.q1.popleft()
self.q1, self.q2 = self.q2, self.q1
return val

def top(self) -> int:
while len(self.q1) != 1:
self.q2.append(self.q1.popleft())

# tried to re-use while part, but seems not achievable, since val is retrieved in-between
val = self.q1[0]
self.q2.append(self.q1.popleft())  # note: add back to q2, so q1 will always be empty

self.q1, self.q2 = self.q2, self.q1
return val

def empty(self) -> bool:
return not self.q1

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()


• type MyStack struct {
q1 []int
q2 []int
}

func Constructor() MyStack {
return MyStack{}
}

func (this *MyStack) Push(x int) {
this.q2 = append(this.q2, x)
for len(this.q1) > 0 {
this.q2 = append(this.q2, this.q1[0])
this.q1 = this.q1[1:]
}
this.q1, this.q2 = this.q2, this.q1
}

func (this *MyStack) Pop() int {
x := this.q1[0]
this.q1 = this.q1[1:]
return x
}

func (this *MyStack) Top() int {
return this.q1[0]
}

func (this *MyStack) Empty() bool {
return len(this.q1) == 0
}

/**
* Your MyStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* param_2 := obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.Empty();
*/

• class MyStack {
q1: number[] = [];
q2: number[] = [];

constructor() {}

push(x: number): void {
this.q2.push(x);
while (this.q1.length) {
this.q2.push(this.q1.shift()!);
}
[this.q1, this.q2] = [this.q2, this.q1];
}

pop(): number {
return this.q1.shift()!;
}

top(): number {
return this.q1[0];
}

empty(): boolean {
return this.q1.length === 0;
}
}

/**
* Your MyStack object will be instantiated and called as such:
* var obj = new MyStack()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.empty()
*/


• use std::collections::VecDeque;

struct MyStack {
/// There could only be two status at all time
/// 1. One contains N elements, the other is empty
/// 2. One contains N - 1 elements, the other contains exactly 1 element
q_1: VecDeque<i32>,
q_2: VecDeque<i32>,
// Either 1 or 2, originally begins from 1
index: i32,
}

impl MyStack {
fn new() -> Self {
Self {
q_1: VecDeque::new(),
q_2: VecDeque::new(),
index: 1,
}
}

fn move_data(&mut self) {
// Always move from q1 to q2
assert!(self.q_2.len() == 1);
while !self.q_1.is_empty() {
self.q_2.push_back(self.q_1.pop_front().unwrap());
}
let tmp = self.q_1.clone();
self.q_1 = self.q_2.clone();
self.q_2 = tmp;
}

fn push(&mut self, x: i32) {
self.q_2.push_back(x);
self.move_data();
}

fn pop(&mut self) -> i32 {
self.q_1.pop_front().unwrap()
}

fn top(&mut self) -> i32 {
*self.q_1.front().unwrap()
}

fn empty(&self) -> bool {
self.q_1.is_empty()
}
}