225. Implement Stack using Queues

Easy

StackDesignQueue

Answered: Mar 21, 2026

Problem 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.

Examples

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

Complexity Analysis

Time Complexity:

O (n) f or ‘ p o p ‘ an d ‘ t o p ‘, O (1) f or ‘ p u s h ‘ an d ‘ e m pt y ‘.

The pop and top operations drain all but one element from the active queue, requiring $O(n)$ dequeue operations. push simply appends to the active queue in $O(1)$ .

Space Complexity:

O (n)

The two queues together hold all n elements at any point in time.

This approach uses two queues and alternates which one is "active" — all elements are kept in one queue at a time, and new elements are always appended to whichever queue is currently active. For pop and top, we drain all but the last element from the active queue into the inactive one, which effectively reverses their roles, and then dequeue the final element (the stack top).

Complexity Analysis

Time Complexity:

O (n) f or ‘ p o p ‘ an d ‘ t o p ‘, O (1) f or ‘ p u s h ‘ an d ‘ e m pt y ‘.

pop and top iterate through n-1 elements to reach the last one, giving $O(n)$ . Swapping queue references is $O(1)$ . push is a single enqueue, $O(1)$ .

Space Complexity:

O (n)

All n elements are distributed across the two queues at any time.

This approach keeps push simple — new elements always go to the back of queue1. The work is deferred to pop and top: we drain all but the last element from queue1 into queue2, then dequeue the remaining element (the stack top), and finally swap the two queues so queue1 always remains the primary queue.

Complexity Analysis

Time Complexity:

O (n) f or ‘ p u s h ‘, O (1) f or ‘ p o p ‘, ‘ t o p ‘, an d ‘ e m pt y ‘.

push moves all existing n-1 elements from queue1 to queue2, so it costs $O(n)$ . pop and top simply dequeue/peek the front of queue1, which is $O(1)$ .

Space Complexity:

O (n)

All n elements are stored across the two queues at any time.

This approach shifts the cost to push so that pop and top become $O(1)$ . On each push, the new element is added to the back of queue2, then all elements from queue1 are moved into queue2 (so the new element ends up at the front), and the two queues are swapped — making queue1 always ordered with the most recently pushed element at the front.

Complexity Analysis

Time Complexity:

O (n) f or ‘ p u s h ‘, O (1) f or ‘ p o p ‘, ‘ t o p ‘, an d ‘ e m pt y ‘.

push rotates n-1 existing elements through the queue, costing $O(n)$ . pop and top operate directly on the front element in $O(1)$ .

Space Complexity:

O (n)

A single queue holds all n elements.

This is the one-queue version of Solution 3's push-heavy strategy. On each push, after appending the new element to the back of the queue, we rotate all the previously existing elements to the back — cycling them through the front — so the newly pushed element ends up at the front. This keeps the stack top always at the head of the queue, making pop and top $O(1)$ .

Complexity Analysis

Time Complexity:

O (n) f or ‘ p o p ‘, O (1) f or ‘ p u s h ‘, ‘ t o p ‘, an d ‘ e m pt y ‘.

pop rotates n-1 elements through the queue, costing $O(n)$ . push is a single enqueue plus assignment in $O(1)$ . top simply returns the cached top_element in $O(1)$ .

Space Complexity:

O (n)

A single queue holds all n elements, plus one $O(1)$ variable for top_element.

This approach also uses a single queue but trades an $O(n)$ pop for $O(1)$ top by tracking the top element explicitly in top_element. push is $O(1)$ — just enqueue and update top_element. For pop, we rotate n-1 elements to bring the last one to the front, updating top_element along the way so it always reflects the new top after the pop.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Two queues, alternating active queue	$O(n)$ for `pop`/`top`, $O(1)$ for `push`	$O(n)$	Simple to follow; no queue swapping needed	⚠️ Requires two queues; alternating logic is error-prone
Two queues with one active queue and swapping	$O(n)$ for `pop`/`top`, $O(1)$ for `push`	$O(n)$	Cleaner than Solution 1 by always using `queue1` as primary	⚠️ Still requires two queues with $O(n)$ reads
Push-heavy approach with two queues	$O(n)$ for `push`, $O(1)$ for `pop`/`top`	$O(n)$	$O(1)$ `pop` and `top` are ideal for read-heavy workloads	⚠️ Requires two queues; every `push` is $O(n)$
Push-heavy approach with one queue	$O(n)$ for `push`, $O(1)$ for `pop`/`top`	$O(n)$	Meets the follow-up with one queue; $O(1)$ reads via front-of-queue invariant	Every `push` rotates all existing elements, costing $O(n)$
Pop-heavy approach with one queue	$O(n)$ for `pop`, $O(1)$ for `push`/`top`	$O(n)$	Meets the follow-up; $O(1)$ `push` and `top` via cached `top_element`	Every `pop` rotates all elements, costing $O(n)$

Per-operation Time Complexity

Approach	push	pop	top	empty
Standard Stack	$O(1)$	$O(1)$	$O(1)$	$O(1)$
Two queues, alternating active queue	$O(1)$	$O(n)$ ⚠️	$O(n)$ ⚠️	$O(1)$
Two queues with one active queue and swapping	$O(1)$	$O(n)$ ⚠️	$O(n)$ ⚠️	$O(1)$
Push-heavy approach with two queues	$O(n)$ ⚠️	$O(1)$	$O(1)$	$O(1)$
Push-heavy approach with one queue	$O(n)$ ⚠️	$O(1)$	$O(1)$	$O(1)$
Pop-heavy approach with one queue	$O(1)$	$O(n)$ ⚠️	$O(1)$	$O(1)$

Per-operation Space Complexity

Approach	push	pop	top	empty	Total
Standard Stack	$O(1)$	$O(1)$	$O(1)$	$O(1)$	$O(n)$
Two queues, alternating active queue	$O(1)$	$O(1)$ ℹ️	$O(1)$ ℹ️	$O(1)$	$O(n)$
Two queues with one active queue and swapping	$O(1)$	$O(1)$ ℹ️	$O(1)$ ℹ️	$O(1)$	$O(n)$
Push-heavy approach with two queues	$O(1)$ ℹ️	$O(1)$	$O(1)$	$O(1)$	$O(n)$
Push-heavy approach with one queue	$O(1)$ ℹ️	$O(1)$	$O(1)$	$O(1)$	$O(n)$
Pop-heavy approach with one queue	$O(1)$	$O(1)$ ℹ️	$O(1)$	$O(1)$	$O(n)$

The optimal approach for this problem is Solution 4: Push-heavy approach with one queue, which achieves $O(n)$ for push, $O(1)$ for pop/top time complexity and $O(n)$ space complexity. It satisfies the follow-up's single-queue constraint and keeps reads efficient by maintaining the stack top at the front of the queue via a rotation on each push. Solutions marked with ⚠️ in the first table do not meet the follow-up requirement and are not recommended.

Problem 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.

Examples

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

Solutions

52 lines
1class MyStack:
2
3    def __init__(self):
4        self.queue1 = []
5        self.queue2 = []
6
7    def push(self, x: int) -> None:
8        if not self.queue1: # If queue1 is empty, push to queue2
9            self.queue2.append(x)
10        else: # If queue1 is not empty, push to queue1
11            self.queue1.append(x)
12
13    def pop(self) -> int:
14        if not self.queue1:
15            # Move all but the last element from queue2 to queue1, then pop the last element
16            while len(self.queue2) > 1:
17                self.queue1.append(self.queue2.pop(0))
18            return self.queue2.pop(0)
19        else:
20            # Move all but the last element from queue1 to queue2, then pop the last element
21            while len(self.queue1) > 1:
22                self.queue2.append(self.queue1.pop(0))
23            return self.queue1.pop(0)
24
25    def top(self) -> int:
26        if not self.queue1:
27            # Move all but the last element from queue2 to queue1, then peek the last element
28            while len(self.queue2) > 1:
29                self.queue1.append(self.queue2.pop(0))
30
31            value = self.queue2.pop(0)
32            self.queue1.append(value) # Put it back after peeking
33        else:
34            # Move all but the last element from queue1 to queue2, then peek the last element
35            while len(self.queue1) > 1:
36                self.queue2.append(self.queue1.pop(0))
37
38            value = self.queue1.pop(0)
39            self.queue2.append(value) # Put it back after peeking
40
41        return value
42
43    def empty(self) -> bool:
44        return len(self.queue1) == 0 and len(self.queue2) == 0
45
46
47# Your MyStack object will be instantiated and called as such:
48# obj = MyStack()
49# obj.push(x)
50# param_2 = obj.pop()
51# param_3 = obj.top()
52# param_4 = obj.empty()

Complexity Analysis

Time Complexity:

O (n) f or ‘ p o p ‘ an d ‘ t o p ‘, O (1) f or ‘ p u s h ‘ an d ‘ e m pt y ‘.

The pop and top operations drain all but one element from the active queue, requiring $O(n)$ dequeue operations. push simply appends to the active queue in $O(1)$ .

Space Complexity:

O (n)

The two queues together hold all n elements at any point in time.

47 lines
1from collections import deque
2
3class MyStack:
4
5    def __init__(self):
6        # Initialize two queues
7        self.queue1 = deque()
8        self.queue2 = deque()
9
10
11    def push(self, x: int) -> None:
12        # Simply append the new element to queue1
13        self.queue1.append(x)
14
15    def pop(self) -> int:
16        # Move all elements except the last one from queue1 to queue2
17        while len(self.queue1) > 1:
18            self.queue2.append(self.queue1.popleft())
19
20        # The last element in queue1 is the top of the stack, so we pop it, then swap the queues
21        top_element = self.queue1.popleft()
22        self.queue1, self.queue2 = self.queue2, self.queue1
23
24        return top_element
25
26    def top(self) -> int:
27        while len(self.queue1) > 1:
28            self.queue2.append(self.queue1.popleft())
29
30        # The last element in queue1 is the top of the stack, so we pop it, then push it back to queue2 before swapping the queues
31        top_element = self.queue1.popleft()
32        self.queue2.append(top_element)
33        self.queue1, self.queue2 = self.queue2, self.queue1
34
35        return top_element
36
37    def empty(self) -> bool:
38        # The stack is empty if queue1 is empty (since we always swap queues after pop/top operations)
39        return not self.queue1
40
41
42# Your MyStack object will be instantiated and called as such:
43# obj = MyStack()
44# obj.push(x)
45# param_2 = obj.pop()
46# param_3 = obj.top()
47# param_4 = obj.empty()

Complexity Analysis

Time Complexity:

O (n) f or ‘ p o p ‘ an d ‘ t o p ‘, O (1) f or ‘ p u s h ‘ an d ‘ e m pt y ‘.

pop and top iterate through n-1 elements to reach the last one, giving $O(n)$ . Swapping queue references is $O(1)$ . push is a single enqueue, $O(1)$ .

Space Complexity:

O (n)

All n elements are distributed across the two queues at any time.

37 lines
1from collections import deque
2
3class MyStack:
4
5    def __init__(self):
6        self.queue1 = deque()
7        self.queue2 = deque()
8
9    def push(self, x: int) -> None:
10        self.queue2.append(x)
11
12        # Move all elements from queue1 to queue2
13        while self.queue1:
14            self.queue2.append(self.queue1.popleft())
15
16        # Swap the names of queue1 and queue2
17        self.queue1, self.queue2 = self.queue2, self.queue1
18
19    def pop(self) -> int:
20        # Since the top element is always at the front of queue1, we can pop it directly
21        return self.queue1.popleft()
22
23    def top(self) -> int:
24        # The top element is always at the front of queue1
25        return self.queue1[0]
26
27    def empty(self) -> bool:
28        # The stack is empty if queue1 is empty
29        return not self.queue1
30
31
32# Your MyStack object will be instantiated and called as such:
33# obj = MyStack()
34# obj.push(x)
35# param_2 = obj.pop()
36# param_3 = obj.top()
37# param_4 = obj.empty()

Complexity Analysis

Time Complexity:

O (n) f or ‘ p u s h ‘, O (1) f or ‘ p o p ‘, ‘ t o p ‘, an d ‘ e m pt y ‘.

push moves all existing n-1 elements from queue1 to queue2, so it costs $O(n)$ . pop and top simply dequeue/peek the front of queue1, which is $O(1)$ .

Space Complexity:

O (n)

All n elements are stored across the two queues at any time.

33 lines
1from collections import deque
2
3class MyStack:
4
5    def __init__(self):
6        self.queue = deque()
7
8    def push(self, x: int) -> None:
9        self.queue.append(x)
10
11        # Rotate the queue to move the newly added element to the front
12        for _ in range(len(self.queue) - 1):
13            self.queue.append(self.queue.popleft())
14
15    def pop(self) -> int:
16        # The front of the queue is the top of the stack
17        return self.queue.popleft()
18
19    def top(self) -> int:
20        # The front of the queue is the top of the stack
21        return self.queue[0]
22
23    def empty(self) -> bool:
24        # The stack is empty if the queue is empty
25        return not self.queue
26
27
28# Your MyStack object will be instantiated and called as such:
29# obj = MyStack()
30# obj.push(x)
31# param_2 = obj.pop()
32# param_3 = obj.top()
33# param_4 = obj.empty()

Complexity Analysis

Time Complexity:

O (n) f or ‘ p u s h ‘, O (1) f or ‘ p o p ‘, ‘ t o p ‘, an d ‘ e m pt y ‘.

push rotates n-1 existing elements through the queue, costing $O(n)$ . pop and top operate directly on the front element in $O(1)$ .

Space Complexity:

O (n)

A single queue holds all n elements.

37 lines
1from collections import deque
2
3class MyStack:
4
5    def __init__(self):
6        # We use a single queue to implement the stack. The top element of the stack is always at the back of the queue.
7        self.queue = deque()
8        self.top_element = None
9
10    def push(self, x: int) -> None:
11        # When we push an element onto the stack, we add it to the back of the queue and update the top element.
12        self.queue.append(x)
13        self.top_element = x
14
15    def pop(self) -> int:
16        # To pop the top element, we need to rotate the queue until the last element (the top of the stack) is at the front of the queue.
17        for _ in range(len(self.queue) - 1):
18            self.top_element = self.queue.popleft()
19            self.queue.append(self.top_element)
20
21        return self.queue.popleft()
22
23    def top(self) -> int:
24        # The top element is always updated during push and pop operations, so we can return it in O(1) time.
25        return self.top_element
26
27    def empty(self) -> bool:
28        # The stack is empty if the queue has no elements.
29        return not self.queue
30
31
32# Your MyStack object will be instantiated and called as such:
33# obj = MyStack()
34# obj.push(x)
35# param_2 = obj.pop()
36# param_3 = obj.top()
37# param_4 = obj.empty()

Complexity Analysis

Time Complexity:

O (n) f or ‘ p o p ‘, O (1) f or ‘ p u s h ‘, ‘ t o p ‘, an d ‘ e m pt y ‘.

pop rotates n-1 elements through the queue, costing $O(n)$ . push is a single enqueue plus assignment in $O(1)$ . top simply returns the cached top_element in $O(1)$ .

Space Complexity:

O (n)

A single queue holds all n elements, plus one $O(1)$ variable for top_element.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Two queues, alternating active queue	$O(n)$ for `pop`/`top`, $O(1)$ for `push`	$O(n)$	Simple to follow; no queue swapping needed	⚠️ Requires two queues; alternating logic is error-prone
Two queues with one active queue and swapping	$O(n)$ for `pop`/`top`, $O(1)$ for `push`	$O(n)$	Cleaner than Solution 1 by always using `queue1` as primary	⚠️ Still requires two queues with $O(n)$ reads
Push-heavy approach with two queues	$O(n)$ for `push`, $O(1)$ for `pop`/`top`	$O(n)$	$O(1)$ `pop` and `top` are ideal for read-heavy workloads	⚠️ Requires two queues; every `push` is $O(n)$
Push-heavy approach with one queue	$O(n)$ for `push`, $O(1)$ for `pop`/`top`	$O(n)$	Meets the follow-up with one queue; $O(1)$ reads via front-of-queue invariant	Every `push` rotates all existing elements, costing $O(n)$
Pop-heavy approach with one queue	$O(n)$ for `pop`, $O(1)$ for `push`/`top`	$O(n)$	Meets the follow-up; $O(1)$ `push` and `top` via cached `top_element`	Every `pop` rotates all elements, costing $O(n)$

Per-operation Time Complexity

Approach	push	pop	top	empty
Standard Stack	$O(1)$	$O(1)$	$O(1)$	$O(1)$
Two queues, alternating active queue	$O(1)$	$O(n)$ ⚠️	$O(n)$ ⚠️	$O(1)$
Two queues with one active queue and swapping	$O(1)$	$O(n)$ ⚠️	$O(n)$ ⚠️	$O(1)$
Push-heavy approach with two queues	$O(n)$ ⚠️	$O(1)$	$O(1)$	$O(1)$
Push-heavy approach with one queue	$O(n)$ ⚠️	$O(1)$	$O(1)$	$O(1)$
Pop-heavy approach with one queue	$O(1)$	$O(n)$ ⚠️	$O(1)$	$O(1)$

Per-operation Space Complexity

Approach	push	pop	top	empty	Total
Standard Stack	$O(1)$	$O(1)$	$O(1)$	$O(1)$	$O(n)$
Two queues, alternating active queue	$O(1)$	$O(1)$ ℹ️	$O(1)$ ℹ️	$O(1)$	$O(n)$
Two queues with one active queue and swapping	$O(1)$	$O(1)$ ℹ️	$O(1)$ ℹ️	$O(1)$	$O(n)$
Push-heavy approach with two queues	$O(1)$ ℹ️	$O(1)$	$O(1)$	$O(1)$	$O(n)$
Push-heavy approach with one queue	$O(1)$ ℹ️	$O(1)$	$O(1)$	$O(1)$	$O(n)$
Pop-heavy approach with one queue	$O(1)$	$O(1)$ ℹ️	$O(1)$	$O(1)$	$O(n)$

Problem Description

Examples

Example 1

Constraints

Follow-up

Solutions

Solution 1: Two queues, alternating active queue

Complexity Analysis

Explanation

Solution 2: Two queues with one active queue and swapping

Complexity Analysis

Explanation

Solution 3: Push-heavy approach with two queues

Complexity Analysis

Explanation

Solution 4: Push-heavy approach with one queue

Complexity Analysis

Explanation

Solution 5: Pop-heavy approach with one queue

Complexity Analysis

Explanation

Conclusion

Per-operation Time Complexity

Per-operation Space Complexity

Problem Description

Examples

Example 1

Constraints

Follow-up

Solutions

Solution 1: Two queues, alternating active queue

Complexity Analysis

Explanation

Solution 2: Two queues with one active queue and swapping

Complexity Analysis

Explanation

Solution 3: Push-heavy approach with two queues

Complexity Analysis

Explanation

Solution 4: Push-heavy approach with one queue

Complexity Analysis

Explanation

Solution 5: Pop-heavy approach with one queue

Complexity Analysis

Explanation

Conclusion

Per-operation Time Complexity

Per-operation Space Complexity