Queue from Stacks: Implementation and Amortized Analysis

1. The Challenge: Simulating FIFO with LIFO

At first, this seems counterintuitive. Stacks are the opposite of queues. If you push elements 1, 2, 3 into a stack, they come out as 3, 2, 1. A queue must return them as 1, 2, 3. How can we resolve this?

The key insight is that using two stacks allows us to reverse the order of elements.

Imagine you push elements into stack1. They are in LIFO order. If you then pop every element from stack1 and push it onto stack2, the order gets reversed! The element at the bottom of stack1 is now at the top of stack2, ready to be popped in FIFO order.

2. Developing an Efficient Algorithm

While you could transfer elements back and forth for every operation, it would be very inefficient. A much smarter approach, often called the "lazy" or "amortized" approach, optimizes this process. We'll use two stacks, which we can call inputStack and outputStack.

To understand the intuition behind this optimized method, let's first see why a single stack is not enough and then how two stacks solve the problem elegantly.

As the video explained, the logic is as follows:

• inputStack: This stack acts as the entry point. All new elements are enqueued here.
• outputStack: This stack is used for dequeuing. It holds elements in the correct FIFO order.

The operations are defined like this:

1. push(int x) / enqueue(int x):

   • Always push the new element x onto inputStack.
   • This is a simple stack push, so it's always an O(1) operation.

2. pop() / dequeue():

   • First, check outputStack. If it is not empty, it means we already have elements in the correct FIFO order. Simply pop from outputStack and return the value. This is O(1).
   • If outputStack is empty, we need to "refill" it. We do this by transferring all elements from inputStack to outputStack. As each element is popped from inputStack and pushed to outputStack, the order is reversed.
   • Once the transfer is complete, pop from outputStack. This transfer step is O(N), where N is the number of elements in inputStack.

3. peek(): The logic is identical to pop(), but instead of popping from outputStack, we just peek at its top element.

4. empty(): The queue is empty only if both inputStack and outputStack are empty.

3. Amortized Time Complexity

You might look at the pop operation and think, "The worst-case is O(N), so it's an O(N) operation." While the worst-case for a single pop call is indeed O(N), this is where amortized analysis becomes crucial, especially in interview discussions.

Amortized analysis considers the total cost of a sequence of operations and averages it out.

Let's think about the "journey" of a single element:

1. It is pushed onto inputStack (1 operation).
2. It is popped from inputStack and pushed onto outputStack (2 operations). This happens only once in its lifetime.
3. It is popped from outputStack (1 operation).

Each element goes through a constant number of operations (at most 4). If we perform M operations in total, the total time taken will be proportional to M, not M*N. Therefore, the average cost per operation is constant.

This means the amortized time complexity of pop and peek is O(1).

For a detailed written explanation of the logic and complexity, the following resource is very clear.

4. Java Implementation

Now let's translate this logic into Java code. For interview preparation, it's essential to be able to write this from scratch. We will use Java's Stack class for this implementation.

Here is the complete Java code, based on the resources, which you should be prepared to write in an interview.

import java.util.Stack;

class MyQueue {
    // Stack for enqueue operations.
    private Stack<Integer> inputStack;
    // Stack for dequeue operations. Holds elements in FIFO order.
    private Stack<Integer> outputStack;

    public MyQueue() {
        inputStack = new Stack<>();
        outputStack = new Stack<>();
    }
    
    // Pushes element x to the back of the queue.
    // Time Complexity: O(1)
    public void push(int x) {
        inputStack.push(x);
    }
    
    // Removes the element from the front of the queue and returns it.
    // Time Complexity: Amortized O(1)
    public int pop() {
        // Ensure outputStack has elements before popping.
        peek(); 
        return outputStack.pop();
    }
    
    // Gets the front element.
    // Time Complexity: Amortized O(1)
    public int peek() {
        // If outputStack is empty, transfer elements from inputStack.
        if (outputStack.isEmpty()) {
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }
        return outputStack.peek();
    }
    
    // Returns true if the queue is empty, false otherwise.
    // Time Complexity: O(1)
    public boolean empty() {
        return inputStack.isEmpty() && outputStack.isEmpty();
    }
}

Note: In modern Java, it's recommended to use the Deque interface with an ArrayDeque implementation to represent a stack (Deque<Integer> stack = new ArrayDeque<>();). However, using the Stack class is simple, direct, and common in interview contexts for this specific problem.

Conclusion

Excellent work! You've successfully implemented a queue using two stacks and, more importantly, analyzed its performance using the concept of amortized complexity. This is a powerful idea that separates a good developer from a great one.

Key Takeaways:

• A queue's FIFO behavior can be simulated by two LIFO stacks by using one for input and one for output.
• The transfer of elements from the input stack to the output stack effectively reverses their order.
• The most efficient implementation is the "lazy" approach: only transfer elements when the output stack is empty.
• While a single pop or peek can be O(N) in the worst case, the amortized time complexity is O(1) because each element is moved a constant number of times over its lifecycle.

Preview of the next lesson:
We have now covered stacks and queues in depth. Next, we will explore the Deque (Double-Ended Queue), a versatile data structure that combines the functionalities of both. You will learn to implement a deque using a doubly linked list, giving you efficient O(1) insertion and deletion at both the front and the back.