{x}
blog image

Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

  • void push(int x) Pushes element x to the back of the queue.
  • int pop() Removes the element from the front of the queue and returns it.
  • int peek() Returns the element at the front of the queue.
  • boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

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

 

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

 

Constraints:

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

 

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

Solution Explanation: Implementing a Queue using Stacks

This problem requires implementing a queue data structure using only two stacks. A queue follows the FIFO (First-In, First-Out) principle, while stacks follow LIFO (Last-In, First-Out). The challenge lies in efficiently simulating FIFO behavior using LIFO structures.

Approach: Double Stack Method

The most efficient approach uses two stacks:

  • stk1 (input stack): Elements are pushed onto this stack.
  • stk2 (output stack): Elements are popped from this stack.

Operations:

  1. push(x): Simply push the element x onto stk1. This is O(1) time complexity.

  2. pop():

    • If stk2 is empty, move all elements from stk1 to stk2. This ensures that the elements are in the correct order for popping (oldest first).
    • Pop the top element from stk2 and return it.

  3. peek():

    • If stk2 is empty, move all elements from stk1 to stk2.
    • Return the top element of stk2 (without removing it).

  4. empty(): Check if both stk1 and stk2 are empty. This is O(1).

Time and Space Complexity Analysis

  • Time Complexity:

    • push(x): O(1)
    • pop(): Amortized O(1). In the worst case, all elements from stk1 are moved to stk2, resulting in O(n) time. However, this only happens once for each element. The amortized complexity accounts for the overall time taken across multiple operations. On average, the cost is spread out over multiple operations, making it effectively O(1) per operation.
    • peek(): Amortized O(1). Similar to pop(), the initial transfer of elements from stk1 to stk2 contributes to the worst-case O(n), but the amortized complexity remains O(1).
    • empty(): O(1)

  • Space Complexity: O(n), where n is the number of elements in the queue. We use two stacks, and in the worst case, both stacks can hold up to n elements.

Code Examples (Python, Java, C++, Go, TypeScript, Rust)

The code examples in the provided markdown illustrate the implementation of this double-stack approach in several programming languages. The core logic remains the same across all languages: using a helper function (move) to transfer elements between stacks when needed for pop and peek operations to maintain the FIFO order. Each language example shows how to handle stack operations using appropriate data structures (lists, Deque, std::stack, slices/arrays, etc.). The comments in the code explain the specific steps involved.