Queue Using Two Stacks in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of enqueue and dequeue operations

What is the output of the following code that uses two stacks to implement a queue?

DSA C++

class QueueUsingStacks {
private:
    std::stack<int> s1, s2;
public:
    void enqueue(int x) {
        s1.push(x);
    }
    int dequeue() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int val = s2.top();
        s2.pop();
        return val;
    }
};

int main() {
    QueueUsingStacks q;
    q.enqueue(10);
    q.enqueue(20);
    int a = q.dequeue();
    q.enqueue(30);
    int b = q.dequeue();
    int c = q.dequeue();
    std::cout << a << " " << b << " " << c << std::endl;
    return 0;
}

A 10 20 30

B 10 30 20

C 30 20 10

D 20 10 30

💡 Hint

Remember that dequeue transfers elements from s1 to s2 only when s2 is empty.

The queue enqueues 10 and 20. The first dequeue moves 10 and 20 to s2 and pops 10. Then 30 is enqueued to s1. The second dequeue pops 20 from s2. The third dequeue moves 30 from s1 to s2 and pops 30.

🧠 Conceptual

intermediate

Time complexity of dequeue operation

What is the amortized time complexity of the dequeue operation in a queue implemented using two stacks?

A O(n)

B O(1)

C O(log n)

D O(n^2)

💡 Hint

Consider how often elements are moved between stacks.

Each element is moved at most twice: once when pushed to s1 and once when moved to s2. So amortized dequeue is O(1).

🔧 Debug

advanced

Identify the error in dequeue method

What error will occur when running this dequeue method if both stacks are empty?

DSA C++

int dequeue() {
    if (s2.empty()) {
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
    }
    int val = s2.top();
    s2.pop();
    return val;
}

A Segmentation fault

B std::underflow_error exception

C std::out_of_range exception

D No error, returns garbage value

💡 Hint

What happens if s2.top() is called when s2 is empty?

Calling top() on an empty stack causes undefined behavior, often a segmentation fault.

❓ Predict Output

advanced

State of stacks after operations

After executing the following operations on a queue implemented with two stacks, what is the content of s1 and s2 (top to bottom)?

DSA C++

QueueUsingStacks q;
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.dequeue();
q.enqueue(4);
// What are s1 and s2 now?

A

s1: empty
s2: 3 (top)
    2
    1

B

s1: 4 (top)
    3
s2: 2 (top)

C

s1: 3 (top)
    4
s2: 2 (top)

D

s1: 4 (top)
s2: 2 (top)
    3

💡 Hint

Dequeue moves elements from s1 to s2 only if s2 is empty.

Enqueues 1,2,3 put 3 (top), 2, 1 (bottom) in s1. Dequeue transfers to s2: push 3 (bottom), push 2, push 1 (top), then pops 1, leaving s2: 2 (top), 3. Enqueue 4 puts 4 (top) in s1.

🧠 Conceptual

expert

Why use two stacks to implement a queue?

Which of the following best explains why two stacks can be used to implement a queue?

A Because stacks automatically sort elements which queues need.

B Because stacks support random access which queues require.

C Because reversing the order twice restores the original order, enabling FIFO behavior.

D Because stacks use less memory than queues.

💡 Hint

Think about how stack order is reversed.

Two stacks reverse the order of elements twice, so the first element enqueued is the first dequeued, mimicking a queue.

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