225. Implement Stack using Queues

Problem Description

The goal of this problem is to design a stack data structure with a Last-In-First-Out (LIFO) behavior using only two queues to store the data. This means that we need to implement the usual stack operations (push, top, pop, and empty) but with a constraint that only the standard queue operations (enqueue/push to back, dequeue/pop from front, check size, and check if empty) are allowed. We're essentially required to emulate the behavior of one data structure (stack) with another (queue).

A stack traditionally allows adding (pushing) an item on top, removing (popping) the top item, inspecting (top) the item at the top, and checking if the stack is empty. Instead of using the stack's native methods, we have to use the properties of two queues to achieve the same outcomes.

Here's the specific contract for the MyStack class:

void push(int x) - Adds the element x to the top of the stack.
int pop() - Removes and returns the element from the top of the stack.
int top() - Returns the element from the top of the stack without removing it.
boolean empty() - Returns true if the stack is empty, otherwise returns false.

Intuition

The major challenge is that the queue is a First-In-First-Out (FIFO) structure, whereas a stack is a Last-In-First-Out (LIFO) structure. So, our solution must invert the order of queue elements with each push operation to maintain the LIFO order of a stack.

To implement a stack using queues, the push operation will involve adding the new element to an empty auxiliary queue, and then dequeuing all elements from the primary queue and enqueueing them to the auxiliary queue, which effectively places the new element at the beginning of the queue that represents our stack. Next, we swap the roles of the two queues: the auxiliary queue becomes the primary queue (our stack), and the old primary queue becomes empty and hence becomes the new auxiliary queue. The pop operation simply dequeues from the primary queue.

By doing this, the front of the primary queue always has the last pushed element, which enables us to do a pop and top operation as if it were a stack.

The empty operation checks whether the primary queue is empty, which indicates whether the stack is empty.

It's important to note that the key to this solution is the swapping mechanism after each push - it ensures the primary queue always has the last pushed element ready to be popped, thus fulfilling the stack's LIFO property using the queue's FIFO order.

Learn more about Stack and Queue patterns.

Solution Approach

In the reference solution approach, we see the implementation of a stack using two double-ended queues (deque() in Python), which allows us to achieve our goal of simulating a stack using queue operations. Here is how each method of the MyStack class works under the hood:

`push(int x)`

Create a temporary queue q2 and enqueue the new element x into q2.
Dequeue all elements from the existing queue q1 and enqueue them into q2. This ensures that the new element x ends up at the front of q2, maintaining the stack's LIFO order.
Now, swap q1 and q2, so that q1 becomes the queue with the new element at the front (acting as the "top" of the stack) and q2 becomes empty, ready to be used for the next push operation.

`pop()`

Directly dequeue from q1, which removes and returns the front element of q1, the element that was most recently pushed and thus on the "top" of the stack.

`top()`

Access the front element of q1 directly, which is the element on the "top" of the stack, and return it. This operation does not remove the element from the queue.

`empty()`

Return a boolean value indicating whether q1 is empty. If q1 is empty, that means there are no elements in the stack.

Let's break down the core algorithm pattern used here:

Two Queue Stack Simulation: We simulate stack operations using two queues by inverting the queue each time we push an element onto the "stack". The reversal of the queue order with every push operation is critical to simulate the stack's LIFO property.
Swap Mechanism: We make use of two queues and consistently keep one queue empty by swapping them after each push operation. This effectively ensures a fresh auxiliary queue for the next push operation and maintains the stack order in the primary queue.
Queue Operations: Standard queue operations are enqueue (to add elements), dequeue (to remove elements), and checking if the queue is empty. We use these operations in our solution to emulate the corresponding stack operations push, pop, and empty.

In summary, the stack is simulated using two queues by ensuring the most recently pushed element is always at the front of the primary queue. This is done by reversing the order of elements with every push operation, which is achieved by moving all elements from one queue to the other, followed by a swap.

The algorithms and patterns used in this approach are straightforward, yet clever, leveraging the basic queue operations to fulfill the requirements of a completely different abstract data type, the stack.

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 illustrate the solution with a small example:

Suppose we perform the following operations on an initially empty MyStack object:

push(1)
push(2)
top()
pop()
empty()

Now let's walk through these operations step by step using the described algorithm:

Operation 1: `push(1)`

Start with two empty queues, q1 and q2.
q1: []
q2: []
Enqueue 1 to q2.
q2: [1]
Since q1 is empty, no elements are dequeued from q1 and enqueued to q2.
Swap the roles of q1 and q2. Now q1 is our stack with 1 in it.
q1: [1]
q2: []

Operation 2: `push(2)`

Enqueue 2 to q2.
q2: [2]
Dequeue 1 from q1 and enqueue it to q2. This will put 2 in front of 1, which maintains our stack's LIFO order.
q2: [2, 1]
q1: []
Swap the roles of q1 and q2 again. q1 is now effectively the stack.
q1: [2, 1]
q2: []

Operation 3: `top()`

Return the front element of q1, which is 2. This does not alter the queue.

Operation 4: `pop()`

Dequeue from q1, removing the front element 2, which is the "top" of the stack.
q1: [1]

Operation 5: `empty()`

Check if q1 is empty. It's not, as it contains 1, so return false.

At the end of these operations, our MyStack object has successfully emulated standard stack behavior with the help of two queues, demonstrating the key principles of this problem's solution approach.

Solution Implementation

1from collections import deque
2
3class MyStack:
4    def __init__(self):
5        # Use two queues to implement the stack behavior
6        self.main_queue = deque()
7        self.helper_queue = deque()
8
9    def push(self, x: int) -> None:
10        # Always push the new element to the helper_queue
11        self.helper_queue.append(x)
12        # Transfer all existing elements from the main_queue to the helper_queue
13        while self.main_queue:
14            self.helper_queue.append(self.main_queue.popleft())
15        # Swap the references of the two queues to make helper_queue the new main_queue
16        self.main_queue, self.helper_queue = self.helper_queue, self.main_queue
17
18    def pop(self) -> int:
19        # Remove and return the last pushed element which is at the start of the main_queue
20        return self.main_queue.popleft()
21
22    def top(self) -> int:
23        # Return the last pushed element without removing it, which is at the start of the main_queue
24        return self.main_queue[0]
25
26    def empty(self) -> bool:
27        # Check whether the main_queue is empty or not
28        return len(self.main_queue) == 0
29
30# Usage example
31# stack = MyStack()
32# stack.push(1)
33# stack.push(2)
34# print(stack.top())    # Returns 2
35# print(stack.pop())    # Returns 2
36# print(stack.empty())  # Returns False
37

1import java.util.ArrayDeque;
2import java.util.Deque;
3
4class MyStack {
5    private Deque<Integer> mainQueue = new ArrayDeque<>();
6    private Deque<Integer> auxQueue = new ArrayDeque<>();
7
8    // Constructor for the stack
9    public MyStack() {
10        // No initialization needed as Java Deque is initialized by default
11    }
12
13    // Method to push an element into the stack
14    public void push(int x) {
15        // Add the element to the auxiliary queue
16        auxQueue.offer(x);
17      
18        // Move all elements from the main queue to the auxiliary queue, reversing the order
19        while (!mainQueue.isEmpty()) {
20            auxQueue.offer(mainQueue.poll());
21        }
22      
23        // Swap the main and auxiliary queues
24        Deque<Integer> temp = mainQueue;
25        mainQueue = auxQueue;
26        auxQueue = temp;
27    }
28
29    // Method to pop an element from the top of the stack
30    public int pop() {
31        // Remove and return the front element from the main queue
32        return mainQueue.poll();
33    }
34
35    // Method to get the top element of the stack
36    public int top() {
37        // Get the front element from the main queue without removing it
38        return mainQueue.peek();
39    }
40
41    // Method to check if the stack is empty
42    public boolean empty() {
43        // Return true if the main queue is empty
44        return mainQueue.isEmpty();
45    }
46}
47
48// Class usage:
49// MyStack stack = new MyStack();
50// stack.push(1);
51// int popped = stack.pop();
52// int topElement = stack.top();
53// boolean isEmpty = stack.empty();
54

1#include <queue>
2using namespace std;
3
4class MyStack {
5public:
6    // Constructor
7    MyStack() {
8        // No initialization required as we're using STL queue
9    }
10
11    // Push element x onto stack
12    void push(int x) {
13        temporaryQueue.push(x);
14      
15        // Reverse the order of elements by moving everything from mainQueue to temporaryQueue
16        while (!mainQueue.empty()) {
17            temporaryQueue.push(mainQueue.front());
18            mainQueue.pop();
19        }
20
21        // Swap the names of mainQueue and temporaryQueue to reflect the change
22        swap(mainQueue, temporaryQueue);
23    }
24
25    // Removes the element on top of the stack and returns that element
26    int pop() {
27        int topElement = mainQueue.front(); // Get the top element
28        mainQueue.pop(); // Remove the top element from the queue
29        return topElement; // Return the popped element
30    }
31
32    // Get the top element of the stack
33    int top() {
34        return mainQueue.front(); // The front of mainQueue is the top of stack
35    }
36
37    // Returns true if the stack is empty, false otherwise
38    bool empty() {
39        return mainQueue.empty(); // Check if the mainQueue is empty
40    }
41
42private:
43    queue<int> mainQueue;     // This will act as the stack
44    queue<int> temporaryQueue; // Used to reverse the order of elements in push operation
45};
46
47/**
48 * Your MyStack object will be instantiated and called as such:
49 * MyStack* obj = new MyStack();
50 * obj->push(x);
51 * int param_2 = obj->pop();
52 * int param_3 = obj->top();
53 * bool param_4 = obj->empty();
54 */
55

1// Initialization of two queues to simulate a stack
2let primaryQueue: number[] = [];
3let secondaryQueue: number[] = [];
4
5/**
6 * Simulates pushing an element onto stack using queues.
7 * @param {number} x - The element to push onto the stack.
8 */
9function push(x: number): void {
10    // Push the element into the secondary queue
11    secondaryQueue.push(x);
12  
13    // Move all elements from the primary queue to the secondary queue
14    while (primaryQueue.length) {
15        secondaryQueue.push(primaryQueue.shift()!);
16    }
17  
18    // Swap the names of the queues, making the secondary queue the new primary queue
19    [primaryQueue, secondaryQueue] = [secondaryQueue, primaryQueue];
20}
21
22/**
23 * Simulates popping an element from the stack.
24 * @return {number} - The element popped from the stack.
25 */
26function pop(): number {
27    // Remove the element from the front of the primary queue
28    return primaryQueue.shift()!;
29}
30
31/**
32 * Retrieves the element at the top of the stack without removing it.
33 * @return {number} - The element at the top of the stack.
34 */
35function top(): number {
36    // Return the front element of the primary queue
37    return primaryQueue[0];
38}
39
40/**
41 * Checks if the stack is empty.
42 * @return {boolean} - True if the stack is empty, false otherwise.
43 */
44function empty(): boolean {
45    // Check if the primary queue is empty
46    return primaryQueue.length === 0;
47}
48
49// Example usage:
50// push(1);
51// const elementPopped = pop();
52// const elementAtTop = top();
53// const isStackEmpty = empty();
54

Time and Space Complexity

The given Python code defines a class MyStack which implements a stack using two deques (self.q1 and self.q2). Here's the complexity analysis for each method in the MyStack class:

Time Complexity:

push method:
- Each push operation requires moving all elements from q1 to q2 and then swapping the names of q1 and q2.
- If n is the number of elements in the stack, the while loop runs for n iterations as it moves n elements from q1 to q2.
- Therefore, the time complexity for push is O(n).
pop method:
- The pop operation removes an element from the front of q1.
- Since deque operations for popping from the front are O(1), the time complexity for pop is O(1).
top method:
- The top operation retrieves an element from the front of q1 without removing it.
- Accessing the front element is O(1) for a deque, so the time complexity for top is O(1).
empty method:
- The empty operation checks whether q1 is empty by comparing its length to 0.
- Checking if the deque is empty is O(1), hence the time complexity for empty is O(1).

Space Complexity:

The class uses two deques to store the elements of the stack.
The space complexity is dependent on the number of elements present in the stack.
If the stack contains n elements, the space complexity is O(n) since we need to store all n elements.

In conclusion, the push method has a time complexity of O(n), while pop, top, and empty methods have a constant time complexity of O(1). The space complexity for the entire MyStack class is O(n).

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:

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don't know

225. Implement Stack using Queues

Problem Description

Intuition

Solution Approach

push(int x)

pop()

top()

empty()