Implement Queue Using Two Stacks

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 new elements
    std::stack<int> outStack; // Stack used for dequeuing elements (reversed order)

public:
    // Function to enqueue (add) an element to the back of the queue
    void enqueue(int x) {
        // Step 1: Simply push the element into inStack
        inStack.push(x); 
    }

    // Function to dequeue (remove) an element from the front of the queue
    int dequeue() {
        // Step 1: If outStack is empty, we need to move elements from inStack
        if (outStack.empty()) {
            // Step 1.1: If inStack is also empty, the queue is empty
            if (inStack.empty()) {
                return -1; // Indicating underflow or empty queue
            }

            // Step 1.2: Transfer all elements from inStack to outStack
            while (!inStack.empty()) {
                outStack.push(inStack.top()); // Reverse the order
                inStack.pop();                // Remove from inStack
            }
        }

        // Step 2: Now outStack has the oldest elements at the top (FIFO)
        int front = outStack.top(); // Get the front element of the queue
        outStack.pop();             // Remove the front element
        return front;               // Return the dequeued value
    }
    
    // Function to get the front element of the queue without removing it
    int peek() {
        // Step 1: If outStack is empty, transfer elements from inStack
        if (outStack.empty()) {
            while (!inStack.empty()) {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }

        // Step 2: Return the front element (top of outStack)
        return outStack.top();
    }

    // Function to check if the queue is empty
    bool empty() {
        // Queue is empty only when both stacks are empty
        return inStack.empty() && outStack.empty();
    }
};

int main() {
    MyQueue q;

    // Enqueue operations
    q.enqueue(1); // Queue: [1]
    q.enqueue(2); // Queue: [1, 2]
    q.enqueue(3); // Queue: [1, 2, 3]

    // Dequeue operations
    std::cout << q.dequeue() << std::endl; // Output: 1 (front of queue)
    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.

2️⃣ Other Approach

#include <bits/stdc++.h>
using namespace std;

// Queue implementation using two stacks
class StackQueue {
private:
    stack<int> st1, st2; // Two stacks used to simulate a queue

public:
    // Constructor to initialize an empty StackQueue
    StackQueue() {
        // Nothing to initialize explicitly
    }
    
    // Method to push an element to the back of the queue
    void push(int x) {
        // Step 1: Move all elements from st1 to st2
        while (!st1.empty()) {
            st2.push(st1.top()); // Move top of st1 to st2
            st1.pop();           // Remove from st1
        }

        // Step 2: Push the new element to st1 (now it's empty)
        st1.push(x); // This becomes the bottom-most element of the queue

        // Step 3: Move everything back from st2 to st1
        while (!st2.empty()) {
            st1.push(st2.top()); // Restore original order
            st2.pop();
        }
    }

    // Method to remove and return the front element of the queue
    int pop() {
        // Step 1: Check for empty queue
        if (st1.empty()) {
            cout << "Stack is empty";
            return -1; // Return -1 if queue is empty
        }

        // Step 2: Front of queue is at the top of st1
        int topElement = st1.top(); // Get the front
        st1.pop();                  // Remove the front element

        // Step 3: Return popped element
        return topElement;
    }

    // Method to get the front element of the queue without removing it
    int peek() {
        // Step 1: Check for empty queue
        if (st1.empty()) {
            cout << "Stack is empty";
            return -1;
        }

        // Step 2: Return the top element (which is front of queue)
        return st1.top();
    }

    // Method to check if the queue is empty
    bool isEmpty() {
        return st1.empty(); // If st1 is empty, the queue is empty
    }
};

int main() {
    StackQueue q;

    // Simulated list of commands and their inputs
    vector<string> commands = {"StackQueue", "push", "push", "pop", "peek", "isEmpty"};
    vector<vector<int>> inputs = {{}, {4}, {8}, {}, {}, {}};

    // Simulate each command one by one
    for (int i = 0; i < commands.size(); ++i) {
        if (commands[i] == "push") {
            q.push(inputs[i][0]);     // Push the provided input
            cout << "null ";          // Output 'null' to match typical API return
        } else if (commands[i] == "pop") {
            cout << q.pop() << " ";   // Output popped value
        } else if (commands[i] == "peek") {
            cout << q.peek() << " ";  // Output front value
        } else if (commands[i] == "isEmpty") {
            cout << (q.isEmpty() ? "true" : "false") << " "; // Output empty status
        } else if (commands[i] == "StackQueue") {
            cout << "null ";          // Constructor call simulated as 'null'
        }
    }

    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) where N is the number of elements.
• Space Complexity:O(2N) because, in the worst case, both the input and output stacks can each hold up to N elements, totaling 2N elements. Here N is the size of the stack.