Domain 1EasyCORE

Implement Stack using Queues

The problem requires implementing a stack using only two queues. A stack operates on a Last In First Out (LIFO) principle, meaning the last element added is the first one to be removed. The operations that need to be supported are `push`, `pop`, `top`, and `empty`. We must use only standard queue operations: `push to back`, `peek/pop from front`, `size`, and `is empty`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Stack#Design

225. Implement Stack using Queues

Model: qwen2.5-coder:14b
Topics: Stack,Design
FAANG asked: 1
Acceptance rate: 47.9%


Problem Breakdown

The problem requires implementing a stack using only two queues. A stack operates on a Last In First Out (LIFO) principle, meaning the last element added is the first one to be removed. The operations that need to be supported are push, pop, top, and empty. We must use only standard queue operations: push to back, peek/pop from front, size, and is empty.

Inputs/Outputs:

  • Input: A series of stack operations (push, pop, top, empty).
  • Output: The result of the operations, such as the value popped or whether the stack is empty.

Implicit Constraints/Edge Cases:

  • The stack should support all standard stack operations.
  • The implementation must use only queue operations.
  • Edge cases include pushing and popping elements, checking if the stack is empty, and retrieving the top element.

Intuition

A brute-force approach would involve using two queues to simulate a stack. However, this could lead to inefficient operations, especially for pop and top, which might require moving all elements between queues. The key insight is to maintain one queue as the primary storage and use the second queue only during the push operation to ensure LIFO behavior.

Approach

  1. Data Structure Choice: Use two queues (queue1 and queue2). queue1 will store the main stack elements, while queue2 is used temporarily during the push operation.
  2. Push Operation:
    • Enqueue the new element into queue2.
    • Dequeue all elements from queue1 and enqueue them into queue2. This ensures that the newly added element is at the front of queue2, maintaining LIFO order.
    • Swap the roles of queue1 and queue2.
  3. Pop Operation: Simply dequeue the front element from queue1.
  4. Top Operation: Return the front element of queue1 without removing it.
  5. Empty Operation: Check if queue1 is empty.

Complexity Analysis

  • Time Complexity:
    • push: O(n) because all elements in queue1 are moved to queue2.
    • pop, top, empty: O(1).
    • Overall, each operation is amortized O(1) due to the nature of queue operations.
  • Space Complexity: O(n), where n is the number of elements in the stack. This is because we use two queues to store the elements.

Solution

from collections import deque

class MyStack:
    def __init__(self):
        self.queue1 = deque()
        self.queue2 = deque()

    def push(self, x: int) -> None:
        # Push element x onto stack.
        self.queue2.append(x)
        while self.queue1:
            self.queue2.append(self.queue1.popleft())
        self.queue1, self.queue2 = self.queue2, self.queue1

    def pop(self) -> int:
        # Removes the element on top of the stack and returns that element.
        return self.queue1.popleft()

    def top(self) -> int:
        # Get the top element.
        return self.queue1[0]

    def empty(self) -> bool:
        # Returns whether the stack is empty.
        return not self.queue1

Edge Cases Handled

  • Empty Stack: The pop and top operations handle an empty stack by checking if queue1 is empty before proceeding.
  • Single Element: Operations work correctly even when there’s only one element in the stack.
  • Multiple Elements: The LIFO order is maintained for any number of elements pushed onto the stack.