Implement Stack using Queue

Problem Statement

Implement a Stack using two Queues. The stack should support the following operations:

• push(x): Push element x onto the stack
• pop(): Remove and return the top element
• top(): Return the top element without removing it
• empty(): Return whether the stack is empty

Example:

Approach 1: Brute Force (Costly Push)

Intuition

Make push operation costly. When we push an element, we move all elements from the main queue to an auxiliary queue, add the new element to the main queue, and then move all elements back. This ensures the newest element is always at the front.

Algorithm

1. For push(x):
   • Move all elements from q1 to q2
   • Add x to q1
   • Move all elements back from q2 to q1
2. For pop(): Simply dequeue from q1
3. For top(): Return front of q1
4. For empty(): Check if q1 is empty

import java.util.*;

class MyStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;
    
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    
    // O(n) - Costly push
    public void push(int x) {
        // Move all elements from q1 to q2
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        
        // Add new element to q1
        q1.offer(x);
        
        // Move all elements back to q1
        while (!q2.isEmpty()) {
            q1.offer(q2.poll());
        }
    }
    
    // O(1)
    public int pop() {
        return q1.poll();
    }
    
    // O(1)
    public int top() {
        return q1.peek();
    }
    
    // O(1)
    public boolean empty() {
        return q1.isEmpty();
    }
}

Complexity Analysis

• Time Complexity: O(n) for push, O(1) for pop, top, empty
• Space Complexity: O(n) - storing n elements across queues

Approach 2: Optimal (Costly Pop - Using Single Queue)

Intuition

Use a single queue. For push, simply add to the queue. For pop, we rotate the queue by removing and re-adding n-1 elements, then remove the last element (which was the most recently pushed).

Algorithm

1. For push(x): Simply enqueue x - O(1)
2. For pop():
   • Rotate queue n-1 times (remove from front, add to back)
   • Remove and return the front element
3. For top(): Same as pop but add the element back
4. For empty(): Check if queue is empty

import java.util.*;

class MyStack {
    private Queue<Integer> q;
    
    public MyStack() {
        q = new LinkedList<>();
    }
    
    // O(1)
    public void push(int x) {
        q.offer(x);
    }
    
    // O(n)
    public int pop() {
        int size = q.size();
        
        // Rotate n-1 elements
        for (int i = 0; i < size - 1; i++) {
            q.offer(q.poll());
        }
        
        return q.poll();
    }
    
    // O(n)
    public int top() {
        int size = q.size();
        
        // Rotate n-1 elements
        for (int i = 0; i < size - 1; i++) {
            q.offer(q.poll());
        }
        
        int topElement = q.peek();
        q.offer(q.poll());
        
        return topElement;
    }
    
    // O(1)
    public boolean empty() {
        return q.isEmpty();
    }
}

Complexity Analysis

• Time Complexity: O(1) for push, O(n) for pop and top
• Space Complexity: O(n) - storing n elements

Approach 3: Optimal (Costly Push - Using Single Queue)

Intuition

After pushing an element, rotate the queue so that the newly pushed element comes to the front. This makes pop and top O(1).

Algorithm

1. For push(x):
   • Get current size of queue
   • Add x to queue
   • Rotate queue size times to bring x to front
2. For pop(): Simply dequeue
3. For top(): Return front element
4. For empty(): Check if queue is empty

import java.util.*;

class MyStack {
    private Queue<Integer> q;
    
    public MyStack() {
        q = new LinkedList<>();
    }
    
    // O(n)
    public void push(int x) {
        int size = q.size();
        q.offer(x);
        
        // Rotate all previous elements after x
        for (int i = 0; i < size; i++) {
            q.offer(q.poll());
        }
    }
    
    // O(1)
    public int pop() {
        return q.poll();
    }
    
    // O(1)
    public int top() {
        return q.peek();
    }
    
    // O(1)
    public boolean empty() {
        return q.isEmpty();
    }
}

Complexity Analysis

• Time Complexity: O(n) for push, O(1) for pop, top, empty
• Space Complexity: O(n) - storing n elements

Key Takeaways

1. LIFO vs FIFO: Stack is LIFO, Queue is FIFO - we need to reverse the order
2. Trade-off: Either push or pop must be O(n), not both can be O(1)
3. Single Queue: Using rotation technique eliminates need for second queue
4. Use Case Choice: Choose costly push if pops are frequent, costly pop if pushes are frequent
5. This is LeetCode #225 - Implement Stack using Queues
6. Understanding this helps in scenarios where only queue operations are available