Implement Queue using Stack (0(1) amortized method)

Problem Overview

LeetCode Problem 232 - "Implement Queue using Stacks" challenges you to come up with a data structure design using stacks to implement a queue. The queue should support all the fundamental operations (i.e., push, pop, peek, and empty).

The twist is that you have to use stacks to achieve the queue behavior, where the data structure should follow the FIFO (First In, First Out) principle.

Understanding the Problem

To understand the problem, let's first recall the operations of a queue:

• Queue:
  • Enqueue: Add an element to the back of the queue.
  • Dequeue: Remove the element from the front of the queue.
  • Peek/Front: Retrieve the front element of the queue without removing it.
  • Empty: Check if the queue is empty.

The challenge is to implement these operations using one or more stacks. A stack is a LIFO (Last In, First Out) data structure, which is the opposite of a queue's behavior. Hence, this problem tests your understanding of both stacks and queues, as well as your ability to simulate queue operations using stack operations.

Key DSA Concepts and Theory

Before diving into the solution, let's briefly cover the key data structure concepts required:

Stack

• LIFO (Last In, First Out): The last element added to the stack will be the first one to be removed.
• Basic Operations:
  • push: Add an element to the top of the stack.
  • pop: Remove the element from the top of the stack.
  • top/peek: Retrieve the top element without removing it.
  • empty: Check if the stack is empty.

Queue

• FIFO (First In, First Out): The first element added to the queue will be the first one to be removed.
• Basic Operations:
  • enqueue (offer in Java): Add an element to the back of the queue.
  • dequeue (poll in Java): Remove the element from the front of the queue.
  • front (peek in Java): Retrieve the front element without removing it.
  • isEmpty: Check if the queue is empty.

Solution Approach

To implement the queue using two stacks, consider the following approach, which ensures efficient operations:

Two-Stack Solution

We use two stacks, inputStack and outputStack, to simulate the queue operations. The main idea is to use these stacks to reverse the element order when necessary to achieve the FIFO order required by a queue.

Steps and C++/Java Code

1. Push Operation:

   • Simply push the elements onto the inputStack.

2. Pop Operation:

   • If outputStack is empty, move all elements from inputStack to outputStack. This reverses the order of elements to simulate FIFO behavior.
   • Then pop the element from outputStack.

3. Peek Operation:

   • Similar to the pop operation, if outputStack is empty, move all elements from inputStack to outputStack.
   • Peek at the top of outputStack.

4. Empty Operation:

   • The queue is empty if both inputStack and outputStack are empty.

C++ Implementation

#include <stack>
using namespace std;

class MyQueue {
private:
    stack<int> inputStack;
    stack<int> outputStack;
    
    void transferElements() {
        while (!inputStack.empty()) {
            outputStack.push(inputStack.top());
            inputStack.pop();
        }
    }
    
public:
    MyQueue() {}
    
    void push(int x) {
        inputStack.push(x);
    }
    
    int pop() {
        if (outputStack.empty()) {
            transferElements();
        }
        int result = outputStack.top();
        outputStack.pop();
        return result;
    }
    
    int peek() {
        if (outputStack.empty()) {
            transferElements();
        }
        return outputStack.top();
    }
    
    bool empty() {
        return inputStack.empty() && outputStack.empty();
    }
};

Java Implementation

import java.util.Stack;

class MyQueue {
    private Stack<Integer> inputStack;
    private Stack<Integer> outputStack;

    public MyQueue() {
        inputStack = new Stack<>();
        outputStack = new Stack<>();
    }
    
    private void transferElements() {
        while (!inputStack.isEmpty()) {
            outputStack.push(inputStack.pop());
        }
    }

    public void push(int x) {
        inputStack.push(x);
    }
    
    public int pop() {
        if (outputStack.isEmpty()) {
            transferElements();
        }
        return outputStack.pop();
    }
    
    public int peek() {
        if (outputStack.isEmpty()) {
            transferElements();
        }
        return outputStack.peek();
    }
    
    public boolean empty() {
        return inputStack.isEmpty() && outputStack.isEmpty();
    }
}

Time and Space Complexity Analysis

• Push Operation:

  • Time Complexity: O(1) - Since we are just pushing onto a stack.
  • Space Complexity: O(n) - For storing the elements in the stack.

• Pop and Peek Operations:

  • Amortized Time Complexity: O(1) - Over a sequence of operations, each element is moved at most once from inputStack to outputStack.
  • Space Complexity: O(n) - Similar to space required in the push operation.

• Empty Operation:

  • Time Complexity: O(1) - As we're only checking the emptiness of two stacks.
  • Space Complexity: O(1) - Constant space for checking.

Common Mistakes to Avoid

• Forgetting to check if outputStack is empty: Always ensure you transfer elements from inputStack to outputStack only when outputStack is empty.
• Not transferring all elements: When moving from inputStack to outputStack, ensure all elements are transferred to maintain the correct order.

Similar Problems on LeetCode

Here are other related problems you can try on LeetCode:

• LeetCode 225: Implement Stack using Queues
• LeetCode 155: Min Stack
• LeetCode 150: Evaluate Reverse Polish Notation

Additional Resources and References

• GeeksforGeeks Stack and Queue
• LeetCode Discuss Solutions

By understanding these concepts and faithfully executing the above approach, you should be able to tackle this and similar problems confidently. Happy coding!