Implement Stack using Queues

Difficulty: Easy | Acceptance: 69.90% | Paid: No Topics: Stack, Design, Queue

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 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
• Constraints
• Two Queues - O(1) Push
• Two Queues - O(1) Pop
• Single Queue

Examples

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.

Two Queues - O(1) Push

Intuition Use two queues where push is simple (O(1)) and pop requires moving elements between queues to access the last element (O(n)).

Steps

• Push: Add element directly to the primary queue
• Pop: Move all elements except the last from primary to secondary queue, pop the last element, then swap queues
• Top: Similar to pop but return the last element without removing it
• Empty: Check if primary queue is empty

from collections import deque

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())
        val = self.q1[0]
        self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1
        return val

    def empty(self) -> bool:
        return len(self.q1) == 0

Complexity

• Time: O(1) for push, O(n) for pop and top
• Space: O(n) for storing elements
• Notes: Fast push operation but slower pop/top operations

Two Queues - O(1) Pop

Intuition Use two queues where push does the heavy lifting by rotating elements (O(n)), making pop and top operations simple (O(1)).

Steps

• Push: Add to secondary queue, move all elements from primary to secondary, then swap queues
• Pop: Simply remove and return from front of primary queue
• Top: Return the front element of primary queue
• Empty: Check if primary queue is empty

from collections import deque

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

    def push(self, x: int) -> None:
        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:
        return self.q1.popleft()

    def top(self) -> int:
        return self.q1[0]

    def empty(self) -> bool:
        return len(self.q1) == 0

Complexity

• Time: O(n) for push, O(1) for pop and top
• Space: O(n) for storing elements
• Notes: Slower push but faster pop/top operations, often preferred for stack usage patterns

Single Queue

Intuition Use only one queue by rotating elements after each push, ensuring the most recently added element is always at the front.

Steps

• Push: Add element to back, then rotate by moving front elements to back (size-1 times)
• Pop: Simply remove and return from front of queue
• Top: Return the front element of queue
• Empty: Check if queue is empty

from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q) == 0

Complexity

• Time: O(n) for push, O(1) for pop and top
• Space: O(n) for storing elements
• Notes: Most space-efficient approach with same time complexity as two-queue O(1) pop method