Code Implementation

from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()
        
    def push(self, x: int) -> None:
        self.q.append(x)
        # Rotate the queue to put the new element at the front
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
        
    def pop(self) -> int:
        return self.q.popleft()
    
    def top(self) -> int:
        return self.q[0]
    
    def empty(self) -> bool:
        return not self.q
      

#include <queue>

class MyStack {
    std::queue<int> q;
public:
    MyStack() {}
    
    void push(int x) {
        q.push(x);
        int n = q.size();
        for(int i = 1; i < n; ++i) {
            q.push(q.front());
            q.pop();
        }
    }
    
    int pop() {
        int val = q.front();
        q.pop();
        return val;
    }
    
    int top() {
        return q.front();
    }
    
    bool empty() {
        return q.empty();
    }
};
      

import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    private Queue<Integer> q;

    public MyStack() {
        q = new LinkedList<>();
    }
    
    public void push(int x) {
        q.offer(x);
        int n = q.size();
        for(int i = 1; i < n; ++i) {
            q.offer(q.poll());
        }
    }
    
    public int pop() {
        return q.poll();
    }
    
    public int top() {
        return q.peek();
    }
    
    public boolean empty() {
        return q.isEmpty();
    }
}
      

var MyStack = function() {
    this.q = [];
};

MyStack.prototype.push = function(x) {
    this.q.push(x);
    for (let i = 0; i < this.q.length - 1; i++) {
        this.q.push(this.q.shift());
    }
};

MyStack.prototype.pop = function() {
    return this.q.shift();
};

MyStack.prototype.top = function() {
    return this.q[0];
};

MyStack.prototype.empty = function() {
    return this.q.length === 0;
};
      

Problem Description

You are asked to implement a stack using only standard queue operations. Specifically, you must create a class that supports the usual stack operations—push(x), pop(), top(), and empty()—but you can only use the operations provided by a queue, such as enqueue (add to back), dequeue (remove from front), peek (view front), size, and isEmpty. You may use one or two queues.

The key constraints are:

• Only use standard queue operations. Direct access to elements (like indexing) is not allowed unless the language's queue implementation provides it.
• Implement the stack so that it behaves correctly for all operations, matching the Last-In-First-Out (LIFO) principle.
• Your implementation should support multiple calls to each method in any order.

Thought Process

At first glance, this problem seems tricky because stacks and queues are fundamentally different data structures. A stack is Last-In-First-Out (LIFO), while a queue is First-In-First-Out (FIFO). If we naively try to use a queue to mimic a stack, we'll quickly notice that elements come out in the wrong order.

A brute-force approach might involve transferring all elements between two queues for every operation, but that's inefficient. To optimize, we need to think about how to rearrange the queue's elements so that the newest element is always at the front, making pop and top operations efficient.

The key insight is that after each push, we can rotate the queue so that the most recently pushed element moves to the front, effectively making the queue behave like a stack.

Solution Approach

To simulate a stack using a queue, we follow these steps:

• Use a single queue: We maintain all stack elements in one queue.
• Push operation:
  • Enqueue the new element at the back of the queue.
  • Then, rotate the queue by dequeuing each of the previous elements and enqueuing them back, one by one, until the new element is at the front.
  • This ensures that the most recently pushed element is always at the front of the queue.
• Pop operation:
  • Simply dequeue the front element of the queue, which is the top of the stack.
• Top operation:
  • Peek at the front of the queue to get the current top of the stack.
• Empty operation:
  • Check if the queue is empty.

This approach guarantees that all stack operations behave correctly and efficiently, using only permitted queue operations.

Example Walkthrough

Let's trace the following sequence of operations:

• push(1)
• push(2)
• top() → should return 2
• pop() → should remove and return 2
• empty() → should return False

Step by step:

1. After push(1): Queue = [1]
2. After push(2):
   • Enqueue 2: [1, 2]
   • Rotate: dequeue 1 and enqueue it: [2, 1]
3. top(): The front is 2.
4. pop(): Dequeue front (2). Queue = [1]
5. empty(): Queue is not empty (contains 1), so returns False.

This demonstrates that the stack operations are correctly simulated using a queue.

Time and Space Complexity

Brute-force approach: Using two queues and transferring all elements on every pop or top operation can lead to O(n) time for those operations, where n is the number of elements.

Optimized approach (as above):

• Push: O(n) time, because we rotate the queue after each push.
• Pop: O(1) time, as we simply dequeue the front.
• Top: O(1) time, as we peek at the front.
• Empty: O(1) time.
• Space: O(n), as we store all elements in the queue.

Summary

By cleverly rotating the queue after each push, we can use a single queue to implement a stack with correct LIFO behavior. This approach leverages the allowed queue operations to simulate stack operations efficiently, making pop and top constant time at the cost of a linear-time push. The solution is elegant because it reuses a fundamental data structure in a non-obvious way, reinforcing the power of understanding data structure properties and operation costs.