232. Implement Queue using Stacks

Problem Description

The task is to implement a queue with the FIFO (first in, first out) principle using two stacks. In a typical queue, elements are added, or 'pushed', to the back and removed, or 'popped', from the front. Additionally, you should be able to 'peek' at the element at the front without removing it and test if the queue is 'empty'. This should be done using only the standard operations of a stack: 'push to top', 'peek/pop from top', 'size', and 'is empty'.

Intuition

The key to solving this problem is to use two stacks, stk1 and stk2, to invert the order of elements twice so that they come out in the same order that they went in. Initially, all new elements are pushed onto stk1. However, we can't directly pop from stk1 for the queue's pop operation because stacks follow LIFO order. So, to get the FIFO order of a queue, we reverse stk1 by popping all its elements and pushing them onto stk2. The first element pushed into stk1 (and therefore the first in queue order) is now at the top of stk2, allowing us to perform the FIFO pop correctly.

The move method is our helper that handles this transfer if stk2 is empty. It is lazily called only when necessary (when popping or peeking). This efficiency is important as it minimizes the number of operations. Once all elements are transferred to stk2, they can be popped or peeked in the correct FIFO order.

The empty method simply checks both stacks. If both are empty, the queue is empty.

The elegance of this solution arises from the delayed transfer of elements until necessary (amortized analysis), which minimizes the number of total operations needed.

Learn more about Stack and Queue patterns.

Solution Approach

The implementation consists of the following steps, utilizing two stacks, stk1 and stk2, which are simply represented as Python lists:

Constructor (__init__): Two empty stacks are initialized. stk1 is for adding new elements (push operation), and stk2 is used for FIFO retrieval (pop and peek operations).
```
self.stk1 = []
self.stk2 = []
```

Push Operation (push): Elements are added to stk1. Each new element is simply appended to the end of stk1, which is the top of the stack.

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

Pop Operation (pop): To remove an element from the front of the queue, we need to get it from the bottom of stk1. The move method is called to transfer elements from stk1 to stk2, if stk2 is empty, effectively reversing the stack order. The element at the top of stk2 (the front of the queue) is then popped.
```
def pop(self) -> int:
    self.move()
    return self.stk2.pop()
```

Peek Operation (peek): Similar to pop, but instead of removing the element at the front of the queue, we only retrieve it. move ensures the element is moved to stk2 so that it can be peeked at.

def peek(self) -> int:
    self.move()
    return self.stk2[-1]

Empty Operation (empty): This operation checks if both stk1 and stk2 are empty. The queue is empty if and only if both stacks are empty.

def empty(self) -> bool:
    return not self.stk1 and not self.stk2

Move Helper Method (move): This is an essential method that transfers elements from stk1 to stk2 when stk2 is empty. It's called only before a pop or peek operation and only when necessary (i.e., when stk2 is empty and the next front of the queue needs to be accessed).

def move(self):
    if not self.stk2:
        while self.stk1:
            self.stk2.append(self.stk1.pop())

At its core, this approach leverages the fact that the stack data structure (using append and pop in Python lists) can be reversed by transferring elements from one stack to another. By having two stacks, we can ensure elements are in the correct FIFO order for queue operations by handling elements in the 'lazy' manner - that is, by only moving elements when absolutely necessary.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate how the queue implementation using two stacks—stk1 and stk2—works.

Consider the following sequence of operations:

push(1) - Add the element '1' to the queue.
push(2) - Add the element '2' to the queue after '1'.
peek() - Get the element at the front of the queue without removing it.
pop() - Remove the element from the front of the queue.
empty() - Check if the queue is empty.

Now let's examine how each operation is handled:

push(1): stk1 receives the element as [1]. stk2 remains [].
push(2): stk1 grows to [1, 2]. stk2 is still [].
peek(): We want to see the front element of the queue, which is '1'. However, since stk1 is LIFO, we need to move elements to stk2 to access '1'. move() is called, transferring all elements from stk1 to stk2, resulting in stk1 as [] and stk2 as [2, 1]. Now we can peek the top of stk2 which is '1', the first element.
pop(): We need to pop the front element, which is '1'. Since stk2 already has the correct order, we simply pop from stk2. stk2 becomes [2] after popping '1', and stk1 is still [].
empty(): To determine if the queue is empty, we check if both stk1 and stk2 are empty. Since stk2 has an element '2', the method returns False, indicating the queue is not empty.

The sequence of stk1 and stk2 after each operation is shown below:

After push(1): stk1: [1], stk2: []
After push(2): stk1: [1, 2], stk2: []
After peek(): stk1: [], stk2: [2, 1]
After pop(): stk1: [], stk2: [2]
After empty(): No change in stacks, stk1: [], stk2: [2]

The queue is operational, demonstrating that two stacks used in this manner can effectively implement a FIFO queue.

Solution Implementation

1class MyQueue:
2    def __init__(self):
3        # Initialize two stacks
4        self.in_stack = []
5        self.out_stack = []
6
7    def push(self, x: int) -> None:
8        # Push an element onto the end of the queue
9        self.in_stack.append(x)
10
11    def pop(self) -> int:
12        # Pop an element from the start of the queue
13        self._shift_stacks()
14        return self.out_stack.pop()
15
16    def peek(self) -> int:
17        # Get the front element
18        self._shift_stacks()
19        return self.out_stack[-1]
20
21    def empty(self) -> bool:
22        # Return True if the queue is empty, False otherwise
23        return not self.in_stack and not self.out_stack
24
25    def _shift_stacks(self):
26        # Move elements from in_stack to out_stack if out_stack is empty
27        if not self.out_stack:
28            while self.in_stack:
29                self.out_stack.append(self.in_stack.pop())
30
31# The MyQueue object will be instantiated and called as following:
32# obj = MyQueue()
33# obj.push(x)
34# param_2 = obj.pop()
35# param_3 = obj.peek()
36# param_4 = obj.empty()
37

1class MyQueue {
2    // Use two stacks to simulate a queue:
3    // stkInput is used for input operations (push)
4    // stkOutput is used for output operations (pop and peek)
5    private Deque<Integer> stkInput = new ArrayDeque<>();
6    private Deque<Integer> stkOutput = new ArrayDeque<>();
7
8    // Constructor for MyQueue. No initialization needed as 
9    // member variables are already initialized.
10    public MyQueue() {
11    }
12
13    // Push element x to the back of the queue. Since a stack is LIFO (last-in, first-out),
14    // pushing to stkInput will reverse the order when transferred to stkOutput.
15    public void push(int x) {
16        stkInput.push(x);
17    }
18
19    // Pop the element from the front of the queue.
20    // If stkOutput is empty, refill it by popping all elements
21    // from stkInput and pushing them into stkOutput.
22    public int pop() {
23        move();
24        return stkOutput.pop();
25    }
26
27    // Get the front element.
28    // Similar to pop, ensure stkOutput contains elements by moving
29    // them from stkInput if necessary and then return the top element.
30    public int peek() {
31        move();
32        return stkOutput.peek();
33    }
34
35    // Return true if the queue is empty, which is when both stacks are empty.
36    public boolean empty() {
37        return stkInput.isEmpty() && stkOutput.isEmpty();
38    }
39
40    // Helper method to move elements from stkInput to stkOutput. It ensures that
41    // stkOutput contains elements in correct queue order for peeking or popping.
42    private void move() {
43        // Only move elements if stkOutput is empty.
44        if (stkOutput.isEmpty()) {
45            // Move all elements from stkInput to stkOutput.
46            while (!stkInput.isEmpty()) {
47                stkOutput.push(stkInput.pop());
48            }
49        }
50    }
51}
52
53/**
54 * The following operations demonstrate how to instantiate and operate on the MyQueue object:
55 * 
56 * MyQueue obj = new MyQueue();   // Creates an instance of MyQueue
57 * obj.push(x);                   // Pushes element x to the back of the queue
58 * int param_2 = obj.pop();       // Retrieves and removes the front element of the queue
59 * int param_3 = obj.peek();      // Retrieves but does not remove the front element of the queue
60 * boolean param_4 = obj.empty(); // Checks whether the queue is empty
61 */
62

1#include <stack>
2using std::stack;
3
4class MyQueue {
5public:
6    // Constructor for MyQueue doesn't need to do anything since
7    // the standard library stack initializes itself
8    MyQueue() {}
9
10    // Adds an element to the back of the queue
11    void push(int x) {
12        inputStack.push(x);
13    }
14
15    // Removes the element from the front of the queue and returns it
16    int pop() {
17        prepareOutputStack();
18        int element = outputStack.top(); // Save the top element
19        outputStack.pop();               // Remove element from stack
20        return element;                  // Return the saved element
21    }
22
23    // Returns the element at the front of the queue without removing it
24    int peek() {
25        prepareOutputStack();
26        return outputStack.top(); // Return the top element
27    }
28
29    // Checks if the queue is empty
30    bool empty() {
31        // The queue is empty only if both stacks are empty
32        return inputStack.empty() && outputStack.empty();
33    }
34
35private:
36    stack<int> inputStack;  // Stack for enqueuing elements
37    stack<int> outputStack; // Stack for dequeuing elements
38
39    // Helper function to move elements from inputStack to outputStack
40    void prepareOutputStack() {
41        // Only move elements if outputStack is empty
42        if (outputStack.empty()) {
43            while (!inputStack.empty()) {
44                outputStack.push(inputStack.top()); // Move element to outputStack
45                inputStack.pop();                   // Remove it from inputStack
46            }
47        }
48    }
49};
50
51/**
52 * Example usage:
53 * MyQueue* queue = new MyQueue();
54 * queue->push(1);
55 * queue->push(2);
56 * int elem1 = queue->pop(); // returns 1
57 * int elem2 = queue->peek(); // returns 2, the new front after popping 1
58 * bool empty = queue->empty(); // returns false since there's still 2 in the queue
59 * delete queue; // Don't forget to free memory
60 */
61

1// These arrays will act as the stack containers for the queue.
2let stack1: number[] = [];
3let stack2: number[] = [];
4
5// This function simulates the push operation of a queue, where 'x' is the element to be added to the queue.
6function push(x: number): void {
7    stack1.push(x);
8}
9
10// This function simulates the pop operation of a queue, by moving elements from the first stack to the second if necessary.
11function pop(): number {
12    moveStacks();
13    return stack2.pop();
14}
15
16// This function simulates the peek operation of a queue, returning the element at the front without removing it.
17function peek(): number {
18    moveStacks();
19    return stack2[stack2.length - 1];
20}
21
22// This function checks whether the queue is empty.
23function empty(): boolean {
24    return stack1.length === 0 && stack2.length === 0;
25}
26
27// This helper function moves elements from stack1 to stack2 if stack2 is empty, effectively reversing the order to simulate queue behavior.
28function moveStacks(): void {
29    if (stack2.length === 0) {
30        while (stack1.length !== 0) {
31            stack2.push(stack1.pop());
32        }
33    }
34}
35
36// Usage
37// Instead of creating an instance of MyQueue, you would directly call the functions:
38push(1);
39let val1 = pop();
40let val2 = peek();
41let isEmpty = empty();
42

Time and Space Complexity

Time Complexity:

__init__(): O(1) - Initializing two empty stacks takes constant time.
push(x): O(1) - Append operation on a list (stack) is an amortized constant time operation.
pop(): Amortized O(1) - In the worst case, this operation can be O(n), where n is the number of elements in stk1, because it has to move all elements from stk1 to stk2 if stk2 is empty. However, each element is only moved once due to the two-stack arrangement, and, across a series of m operations, this gives an average (or amortized) time complexity of O(1).
peek(): Amortized O(1) - Similar to pop(), it may involve moving all elements from stk1 to stk2 in the worst case, but due to the amortized analysis, it averages to constant time.
empty(): O(1) - Checking if two lists are empty is a constant time operation.
move(): Amortized O(1) - Although it can be O(n) in the worst case when moving all elements from stk1 to stk2, it is part of the pop() and peek() operations and contributes to their amortized time complexity.

Space Complexity:

Overall space complexity for the MyQueue class is O(n), where n is the number of elements in the queue at a given time. This is because all elements are stored in two stacks (stk1 and stk2). No additional space is used that is proportional to the number of elements in the queue except for these two stacks.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: