Queue Using Two Stacks in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind implementing a queue using two stacks?

Use one stack to handle incoming elements (enqueue) and another stack to reverse order for outgoing elements (dequeue), simulating FIFO behavior.

intermediate

How does the dequeue operation work in a queue implemented with two stacks?

If the second stack is empty, pop all elements from the first stack and push them into the second stack, then pop from the second stack to get the front element.

beginner

Why do we need two stacks to implement a queue instead of just one?

One stack alone cannot maintain the FIFO order needed for a queue; two stacks allow reversing the order twice to achieve FIFO.

intermediate

What is the time complexity of enqueue and dequeue operations in a queue using two stacks?

Enqueue is O(1) always; dequeue is amortized O(1) because elements are moved between stacks only when needed.

intermediate

Show the state of two stacks after enqueueing 1, 2, 3 and then dequeueing one element.

After enqueue 1,2,3: stack1 = [1,2,3], stack2 = []. After dequeue: stack1 = [], stack2 = [3,2], dequeued element = 1.

Which stack holds elements in reversed order to simulate queue dequeue?

A The second stack

B The first stack

C Both stacks hold elements in normal order

D Neither stack holds reversed elements

The second stack holds elements popped from the first stack, reversing their order to simulate FIFO.

What happens when the second stack is empty during a dequeue operation?

A The queue is empty

B Dequeue operation fails

C Elements are pushed into the first stack

D Elements are popped from the first stack and pushed into the second stack

To get the front element, all elements from the first stack are moved to the second stack to reverse their order.

What is the time complexity of enqueue operation in a queue using two stacks?

A O(log n)

B O(1)

C O(n)

D O(n^2)

Enqueue simply pushes an element onto the first stack, which is a constant time operation.

Why is the dequeue operation considered amortized O(1) in this implementation?

A Because elements are moved only once between stacks per enqueue

B Because dequeue always takes constant time

C Because elements are moved only once between stacks per dequeue batch

D Because enqueue and dequeue happen simultaneously

Elements are moved from the first to the second stack only when the second stack is empty, spreading the cost over multiple dequeues.

What data structure property does a queue follow?

A First In First Out (FIFO)

B Sorted Order

C Random Access

D Last In First Out (LIFO)

A queue processes elements in the order they arrive, which is FIFO.

Explain how two stacks can be used to implement a queue with enqueue and dequeue operations.

Think about reversing the order of elements using stacks.

Describe the time complexity of enqueue and dequeue operations in a queue implemented with two stacks and why.

Consider when elements are moved between 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 two stacks to reverse the order twice to maintain queue order

C. Use one stack for enqueue and another for dequeue operations

D. Use two stacks to perform only enqueue operations

Solution

1. Step 1: Understand queue order

   A queue follows FIFO (First In First Out) order, meaning the first element added is the first to be removed.

2. Step 2: Use two stacks to reverse order twice

   One stack reverses the order when pushing elements, and the second stack reverses it again when popping, restoring FIFO order.

3. Final Answer:

   Use two stacks to reverse the order twice to maintain queue order -> Option B

4. Quick Check:

   Two reversals keep FIFO order [OK]

Hint: Two stacks reverse order twice to simulate queue [OK]

Common Mistakes:

• Thinking both stacks store elements in sorted order
• Using stacks only for enqueue or dequeue, not both
• Confusing stack order with queue order

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

easy

A. push(stack1, x);

B. stack1.push(x); // C syntax

C. stack1.push(x);

D. push(x, stack1);

Solution

1. Step 1: Recall stack push function in C

   In C, stacks are usually implemented with functions like push(stack, element).

2. Step 2: Identify correct argument order

   The stack is passed first, then the element to push, so push(stack1, x) is correct.

3. Final Answer:

   push(stack1, x); -> Option A

4. Quick Check:

   Function call with stack first, element second [OK]

Hint: In C, push(stack, element) is standard [OK]

Common Mistakes:

• Using object.method() syntax which is not valid in C
• Swapping argument order in push function
• Assuming push is a built-in method

3. Consider the following code snippet implementing a queue using two stacks s1 and s2. What will be the output after the operations?

push(s1, 10);
push(s1, 20);
pop(s2);
if (isEmpty(s2)) {
  while (!isEmpty(s1)) {
    push(s2, top(s1));
pop(s1);
  }
}
pop(s2);
printQueue(s1, s2);

medium

A. Queue elements: 10 -> null

B. Queue elements: null

C. Queue elements: 20 -> null

D. Queue elements: 10 -> 20 -> null

Solution

1. Step 1: Push 10 and 20 onto s1

   s1 = [10 (bottom), 20 (top)], s2 = []

2. Step 2: Pop from s2 (empty), then transfer all from s1 to s2

   Transfer reverses order: s2 = [20 (bottom), 10 (top)], s1 = []

3. Step 3: Pop from s2 removes 10 (top)

   s2 = [20]

4. Step 4: printQueue shows elements in queue order

   Queue order is s2 top to bottom then s1 bottom to top, so only 20 remains.

5. Final Answer:

   Queue elements: 20 -> null -> Option C

6. Quick Check:

   First popped element was 10, next is 20 [OK]

Hint: Transfer reverses stack order to simulate queue dequeue [OK]

Common Mistakes:

• Not transferring elements from s1 to s2 when s2 is empty
• Confusing top and bottom elements during transfer
• Assuming pop removes from s1 directly

4. The following code attempts to implement dequeue operation in a queue using two stacks s1 and s2. What is the bug?

int dequeue() {
  if (isEmpty(s2)) {
    while (!isEmpty(s1)) {
      push(s2, top(s1));
      pop(s1);
    }
  }
  return pop(s2);
}

medium

A. Missing check if both stacks are empty before dequeue

B. pop(s2) returns void, should use top(s2) before pop

C. Should push from s2 to s1 instead of s1 to s2

D. pop(s1) should be called after push(s2, top(s1))

Solution

1. Step 1: Check for empty queue condition

   The code does not check if both s1 and s2 are empty before dequeue, which can cause errors.

2. Step 2: Identify missing empty check

   Without this check, pop(s2) may be called on empty stack causing runtime error.

3. Final Answer:

   Missing check if both stacks are empty before dequeue -> Option A

4. Quick Check:

   Empty queue must be handled before popping [OK]

Hint: Always check if queue is empty before dequeue [OK]

Common Mistakes:

• Assuming pop returns the popped value in C without checking
• Ignoring empty queue condition
• Confusing push direction between stacks

5. You want to implement a queue using two stacks s1 and s2. You perform the following operations:

enqueue(1);
enqueue(2);
dequeue();
enqueue(3);
dequeue();
dequeue();

What will be the output sequence of the dequeued elements?

hard

A. [3, 2, 1]

B. [1, 3, 2]

C. [2, 1, 3]

D. [1, 2, 3]

Solution

1. Step 1: Enqueue 1 and 2

   s1 = [1 (bottom), 2 (top)], s2 = []

2. Step 2: Dequeue first element

   s2 empty, transfer all from s1 to s2: s2 = [2 (bottom), 1 (top)], s1 = []
   Pop from s2 removes 1

3. Step 3: Enqueue 3

   Push 3 to s1: s1 = [3], s2 = [2]

4. Step 4: Dequeue second element

   s2 not empty, pop from s2 removes 2

5. Step 5: Dequeue third element

   s2 empty, transfer s1 to s2: s2 = [3], s1 = []
   Pop from s2 removes 3

6. Final Answer:

   [1, 2, 3] -> Option D

7. Quick Check:

   FIFO order maintained by two stacks [OK]

Hint: Dequeue triggers transfer only if second stack empty [OK]

Common Mistakes:

• Not transferring elements when s2 is empty
• Assuming enqueue adds to s2 instead of s1
• Mixing order of popped elements