A queue follows the First-In-First-Out (FIFO) principle, whereas a stack follows the Last-In-First-Out (LIFO) principle. The challenge here is to use the properties of stacks to mimic the behavior of a queue.

Problem Understanding

The challenge in implementing a queue using stacks lies in maintaining the FIFO order while using the Last-In-Last-Out (LIFO) behavior of stacks. To achieve this, we can use two stacks: one for enqueuing elements and another for dequeueing elements.

Design a queue using two stacks.

• Implement the following operations:
  • enqueue(x): Add an element x to the end of the queue.
  • dequeue(): Remove and return the element from the front of the queue.
  • peek(): Return the element at the front of the queue without removing it.
  • empty(): Return whether the queue is empty.

Approaches

1️⃣ Using Two Stacks

Intuition:

The core idea is to use two stacks (stack1 and stack2) to simulate the behavior of a queue. The two stacks help us reverse the order of elements twice, which effectively preserves the FIFO order.

1. Push Operation (enqueue):
   • Always push the new element onto stack1.
2. Pop Operation (dequeue):
   • If stack2 is empty, transfer all elements from stack1 to stack2 (this reverses the order).
   • Pop the top element from stack2.
3. Peek Operation (peek):
   • Similar to the pop operation, but instead of popping the element, just return the top of stack2.
4. Empty Operation (empty):
   • The queue is empty if both stack1 and stack2 are empty.

Approach:

To implement the queue using two stacks, we maintain the following invariants:

• stack1: Used to store the elements in the order they were enqueued.
• stack2: Used to reverse the order of elements from stack1 to maintain the FIFO order.

When an element is enqueued, it is pushed onto stack1. When an element is dequeued, if stack2 is empty, all elements from stack1 are popped and pushed onto stack2, and then the top element of stack2 is popped. This operation reverses the order of elements twice, mimicking the behavior of a queue.

Steps for Operations:

1. Enqueue (enqueue(x)):
   • Push x onto stack1.
2. Dequeue (dequeue()):
   • If stack2 is empty:
     • Transfer all elements from stack1 to stack2 by popping from stack1 and pushing onto stack2.
   • Pop the top element from stack2.
3. Peek (peek()):
   • If stack2 is empty:
     • Transfer all elements from stack1 to stack2.
   • Return the top element of stack2.
4. Empty (empty()):
   • Return true if both stack1 and stack2 are empty; otherwise, return false.

Dry Run:

Let's consider an example to understand how these operations work:

Example:

Suppose we perform the following sequence of operations:

1. enqueue(1)
2. enqueue(2)
3. enqueue(3)
4. dequeue()
5. enqueue(4)
6. dequeue()
7. peek()

Initial State:

stack1 = []
stack2 = []

enqueue(1):

stack1 = [1]
stack2 = []

enqueue(2):

stack1 = [1, 2]
stack2 = []

enqueue(3):

stack1 = [1, 2, 3]
stack2 = []

dequeue():

stack1 = [1, 2, 3]
stack2 = []

Since stack2 is empty, so move elements from stack1 to stack2.

stack1 = []
stack2 = [3, 2, 1]

Now, pop from stack2: result is 1
stack1 = []
stact2 = [3, 2]

enqueue(4):

stack1 = [4]
stack2 = [3, 2]

dequeue():

stack1 = [4]
stack2 = [3, 2]

Since the stack2 is not empty, pop from stack2: result is 2.

stack1 = [4]
stack2 = [3]

peek():

stack1 = [4]
stack2 = [3]

Since stack is not empty, top of stack2 is 3

Solution in C++:

Let's implement a queue using two stacks in C++. We will use one stack (inStack) for enqueuing elements and another stack (outStack) for dequeueing elements.

#include <iostream>
#include <stack>

class MyQueue {
private:
    std::stack<int> inStack; // Stack for enqueueing elements
    std::stack<int> outStack; // Stack for dequeueing elements

public:
    void enqueue(int x) {
        inStack.push(x); // Push element onto the inStack
    }

    int dequeue() {
        if (outStack.empty()) {
            // if inStack is also empty return -1
            if(inStack.empty()){
                return -1;
            }
            // Transfer elements from inStack to outStack
            while (!inStack.empty()) {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        int front = outStack.top(); // Get the front element
        outStack.pop(); // Remove the front element from outStack
        return front;
    }
    
    int peek() {
    	if(outStack.empty()) {
    		// transfer all elements from inStack to outStack, if outStack is empty
    		while (!inStack.empty()) {
    			outStack.push(inStack.top());
    			inStack.pop();
    		}
    	}
    	return outStack.top();
    }

    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

int main() {
    MyQueue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);

    std::cout << q.dequeue() << std::endl; // Output: 1
    std::cout << q.dequeue() << std::endl; // Output: 2
    std::cout << q.dequeue() << std::endl; // Output: 3

    return 0;
}

// Output
1
2
3

Complexity Analysis:

• Time Complexity:
  • Enqueue Operation:
    • Time Complexity: O(1)
  • Dequeue Operation:
    • Amortized Time Complexity: O(1)
    • Worst Case Time Complexity: O(n) (when outStack is empty and all elements need to be transferred from inStack to outStack)
• Space Complexity:
  • O(n): The space used by the two stack is proportional to the number of elements n in the queue.