Queue Using Two Stacks in DSA C++

Mental Model

Use two stacks to mimic the behavior of a queue by reversing the order twice.

Analogy: Imagine you have two trays of plates. You put plates on the first tray (stack1). When you want to serve the oldest plate, you flip all plates onto the second tray (stack2), reversing their order, so the oldest plate is now on top and ready to serve.

stack1: top -> [] [] []
stack2: top -> [] [] []
Queue front is at the top of stack2 if not empty; otherwise, transfer from stack1.

Dry Run Walkthrough

Input: enqueue 1, enqueue 2, dequeue, enqueue 3, dequeue

Goal: Simulate queue operations using two stacks and show the queue state after each operation

Step 1: enqueue 1: push 1 onto stack1

stack1: top -> [1]
stack2: top -> null

Why: New elements go to stack1 to keep insertion order

Step 2: enqueue 2: push 2 onto stack1

stack1: top -> [2] -> [1]
stack2: top -> null

Why: Keep adding new elements on top of stack1

Step 3: dequeue: stack2 empty, transfer all from stack1 to stack2 reversing order, pop top of stack2 (1)

stack1: top -> null
stack2: top -> [2]

Why: Transfer reverses order so oldest element (1) is on top of stack2, then pop it to simulate dequeue

Step 4: enqueue 3: push 3 onto stack1

stack1: top -> [3]
stack2: top -> [2]

Why: New elements always go to stack1

Step 5: dequeue: stack2 not empty, pop top of stack2 (2)

stack1: top -> [3]
stack2: top -> null

Why: Pop from stack2 if not empty to get oldest element

Result:

stack1: top -> [3]
stack2: top -> null
Queue state: front is 3

Annotated Code

DSA C++

#include <iostream>
#include <stack>
#include <stdexcept>
using namespace std;

class QueueUsingTwoStacks {
private:
    stack<int> stack1, stack2;

    void transferStack1ToStack2() {
        while (!stack1.empty()) {
            stack2.push(stack1.top());
            stack1.pop();
        }
    }

public:
    void enqueue(int x) {
        stack1.push(x); // push new element onto stack1
    }

    int dequeue() {
        if (stack2.empty()) {
            if (stack1.empty()) {
                throw runtime_error("Queue is empty");
            }
            transferStack1ToStack2(); // reverse order by moving all from stack1 to stack2
        }
        int topVal = stack2.top();
        stack2.pop(); // pop oldest element
        return topVal;
    }

    bool empty() {
        return stack1.empty() && stack2.empty();
    }
};

int main() {
    QueueUsingTwoStacks q;
    q.enqueue(1);
    q.enqueue(2);
    cout << q.dequeue() << "\n"; // should print 1
    q.enqueue(3);
    cout << q.dequeue() << "\n"; // should print 2
    return 0;
}

stack1.push(x); // push new element onto stack1

Add new element to stack1 to keep insertion order

if (stack2.empty()) { if (stack1.empty()) { throw runtime_error("Queue is empty"); } transferStack1ToStack2(); }

If stack2 is empty, move all elements from stack1 to stack2 to reverse order

int topVal = stack2.top(); stack2.pop();

Pop the oldest element from stack2 to simulate dequeue

Output

1

2

Complexity Analysis

Time: O(1) amortized because each element is pushed and popped at most twice

Space: O(n) because we store all elements in two stacks combined

vs Alternative: Compared to a normal queue with O(1) enqueue and dequeue, this uses two stacks but still achieves amortized O(1) dequeue by reversing order only when needed

Edge Cases

dequeue from empty queue

throws runtime_error exception

DSA C++

if (stack1.empty()) { throw runtime_error("Queue is empty"); }

enqueue then dequeue single element

element is returned correctly

DSA C++

stack1.push(x);

multiple enqueues before any dequeue

all elements stored in stack1 until first dequeue triggers transfer

DSA C++

transferStack1ToStack2()

When to Use This Pattern

When you need a queue but only have stacks, use two stacks to reverse order twice and simulate FIFO behavior.

Common Mistakes

Mistake: Transferring elements from stack1 to stack2 on every dequeue instead of only when stack2 is empty
Fix: Only transfer when stack2 is empty to maintain amortized O(1) complexity

Summary

Implements a queue using two stacks by reversing element order twice.

Use when only stack data structures are available but queue behavior is needed.

The key insight is that reversing twice restores the original order, enabling FIFO with LIFO stacks.

Practice

1. What is the main idea behind implementing a Queue Using Two Stacks?

easy

A. Use two stacks to store elements in sorted order

B. Use one stack for enqueue and another for dequeue to reverse order

C. Use two stacks to store elements in parallel for faster access

D. Use one stack to store elements and another to count them

Solution

1. Step 1: Understand queue behavior

   A queue follows FIFO (First In First Out), so the first element added should be the first removed.

2. Step 2: Use two stacks to reverse order

   One stack stores elements as they come (enqueue). The second stack reverses the order to allow dequeue in FIFO order.

3. Final Answer:

   Use one stack for enqueue and another for dequeue to reverse order -> Option B

4. Quick Check:

   Two stacks reverse order to simulate queue FIFO [OK]

Hint: Remember: two stacks reverse order to mimic queue [OK]

Common Mistakes:

• Thinking both stacks store elements in the same order
• Assuming stacks keep elements sorted
• Using one stack only for all operations

2. Which of the following is the correct syntax to push an element x into a stack named stack1 in C++?

easy

A. stack1.push(x);

B. stack1.add(x);

C. stack1.insert(x);

D. stack1.enqueue(x);

Solution

1. Step 1: Recall C++ stack push syntax

   The standard C++ stack uses the method push() to add elements.

2. Step 2: Match correct method name

   Only push is the correct method; others like add, insert, or enqueue are invalid for stack.

3. Final Answer:

   stack1.push(x); -> Option A

4. Quick Check:

   Stack push method = push() [OK]

Hint: Stack insertion uses push() method in C++ [OK]

Common Mistakes:

• Using enqueue() which is for queues
• Using add() or insert() which are not stack methods
• Confusing stack with vector methods

3. Consider the following C++ code implementing a queue using two stacks:

std::stack<int> s1, s2;

// Enqueue 1, 2, 3
s1.push(1);
s1.push(2);
s1.push(3);

// Dequeue operation
while (!s1.empty()) {
  s2.push(s1.top());
  s1.pop();
}
int front = s2.top();
s2.pop();

// What is the value of front?

medium

A. 2

B. 3

C. 1

D. Stack empty error

Solution

1. Step 1: Trace enqueue operations

   Elements pushed into s1 in order: 1 (bottom), 2, 3 (top).

2. Step 2: Transfer elements to s2 to reverse order

   Moving all from s1 to s2 reverses order: s2 top is 1, bottom is 3.

3. Step 3: Identify front element

   Front of queue is s2.top() which is 1, then popped.

4. Final Answer:

   1 -> Option C

5. Quick Check:

   Queue front after transfer = 1 [OK]

Hint: Transfer stacks reverses order; front is bottom of first stack [OK]

Common Mistakes:

• Assuming top of s1 is front (3 instead of 1)
• Not reversing stack order before dequeue
• Confusing stack top with queue front

4. The following code snippet is intended to implement dequeue operation in a queue using two stacks. Identify the error:

void dequeue() {
  if (s2.empty()) {
    while (!s1.empty()) {
      s2.push(s1.top());
      s1.pop();
    }
  }
  s1.pop();
}

medium

A. Should pop twice from s1

B. Should push elements from s2 to s1 instead

C. Missing check if both stacks are empty

D. Should pop from s2, not s1, after transfer

Solution

1. Step 1: Understand dequeue logic

   Dequeue removes front element, which is on top of s2 after transfer.

2. Step 2: Identify incorrect pop

   Code pops from s1 after transfer, but front is on s2, so s2.pop() is correct.

3. Final Answer:

   Should pop from s2, not s1, after transfer -> Option D

4. Quick Check:

   Dequeue pops from s2 top [OK]

Hint: Pop from s2 after transfer, not s1 [OK]

Common Mistakes:

• Popping from wrong stack after transfer
• Not checking if both stacks are empty before dequeue
• Confusing enqueue and dequeue stacks

5. You want to implement a queue using two stacks with the following operations:

enqueue(x): Push element x to the queue.
dequeue(): Remove and return the front element.

Which approach ensures amortized O(1) time per operation?

hard

A. Push all elements to s1 on enqueue; transfer to s2 only when s2 is empty during dequeue

B. Push elements alternately to s1 and s2; pop from both stacks on dequeue

C. Transfer all elements from s1 to s2 on every enqueue operation

D. Use s1 for enqueue and s2 for dequeue but transfer elements on every dequeue regardless

Solution

1. Step 1: Understand amortized O(1) goal

   We want to minimize costly transfers by doing them only when necessary.

2. Step 2: Analyze each approach

   Push all elements to s1 on enqueue; transfer to s2 only when s2 is empty during dequeue transfers elements from s1 to s2 only when s2 is empty during dequeue, spreading cost over many operations.

3. Step 3: Reject other options

   Options B, C, and D cause frequent or unnecessary transfers increasing time per operation.

4. Final Answer:

   Push all elements to s1 on enqueue; transfer to s2 only when s2 is empty during dequeue -> Option A

5. Quick Check:

   Transfer only when s2 empty = amortized O(1) [OK]

Hint: Transfer stacks only when dequeue stack is empty [OK]

Common Mistakes:

• Transferring elements on every enqueue or dequeue
• Pushing alternately causing imbalance
• Ignoring amortized cost analysis