Solution Explanation: Implementing a Stack using Queues

This problem challenges us to implement a stack data structure using only queues. A stack follows the Last-In-First-Out (LIFO) principle, while a queue follows the First-In-First-Out (FIFO) principle. The solution leverages the properties of queues to mimic stack behavior.

Approach: Using Two Queues

The most straightforward approach involves using two queues, q1 and q2. q1 primarily holds the stack's elements. q2 acts as a temporary queue to assist in performing stack operations efficiently.

Operations:

• push(x): To add an element x to the stack (top), we enqueue x into q2. Then, we dequeue all elements from q1 and enqueue them into q2. Finally, we swap the references of q1 and q2 so that q1 now contains all elements with x at the end (top of the stack). This ensures the LIFO order.

• pop(): We simply dequeue and return the front element of q1 (the top of the stack).

• top(): We return the front element of q1 (the top of the stack) without removing it.

• empty(): We check if q1 is empty to determine if the stack is empty.

Time and Space Complexity Analysis

• Time Complexity:

  • push(x): O(n), where n is the number of elements in the stack. This is due to the potential need to move all elements from one queue to another.
  • pop(), top(), empty(): O(1). These operations involve only accessing or removing the front element of a queue, which is a constant-time operation.

• Space Complexity: O(n). We use two queues, and in the worst case, both queues will hold all the stack elements.

Code Examples (Python and Java)

The code examples below demonstrate the implementation using Python and Java. The logic remains consistent across different languages, with minor syntactic differences.

Python:

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

Java:

import java.util.ArrayDeque;
import java.util.Deque;
 
class MyStack {
    private Deque<Integer> q1 = new ArrayDeque<>();
    private Deque<Integer> q2 = new ArrayDeque<>();
 
    public MyStack() {}
 
    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        Deque<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
 
    public int pop() {
        return q1.poll();
    }
 
    public int top() {
        return q1.peek();
    }
 
    public boolean empty() {
        return q1.isEmpty();
    }
}

Other languages (C++, Go, TypeScript, Rust) follow a very similar structure, adapting to the specific language's queue implementation and syntax. The core logic of using two queues to simulate a stack remains consistent across all implementations.