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 the order for outgoing elements (dequeue), simulating the FIFO behavior of a queue.
Click to reveal answer
beginner
Why do we need two stacks to implement a queue instead of just one?
A single stack follows LIFO (last-in, first-out), but a queue needs FIFO (first-in, first-out). Two stacks together can reverse the order twice, achieving FIFO behavior.
Click to reveal answer
intermediate
What happens during the dequeue operation in a queue implemented with two stacks?
If the output stack is empty, all elements from the input stack are popped and pushed into the output stack, reversing their order. Then the top of the output stack is popped as the dequeued element.
Click to reveal answer
intermediate
What is the time complexity of enqueue and dequeue operations in a queue using two stacks?
Enqueue is O(1) because it just pushes onto the input stack. Dequeue is amortized O(1) because elements are moved between stacks only when the output stack is empty.
Click to reveal answer
intermediate
Show the state of the two stacks after enqueueing 1, 2, 3 and then dequeueing one element.
Input stack: [ ] (empty)<br>Output stack: [3, 2] (top is 3)<br>Explanation: After dequeue, 1 is removed. 2 and 3 remain in output stack ready for next dequeue.
Click to reveal answer
What data structure is used internally to implement a queue using two stacks?
✗ Incorrect
The queue is implemented using two stacks to simulate FIFO behavior.
During dequeue, if the output stack is empty, what is done?
✗ Incorrect
Elements are transferred from input stack to output stack to reverse order for dequeue.
What is the time complexity of enqueue operation in a queue using two stacks?
✗ Incorrect
Enqueue just pushes onto the input stack, which is O(1).
What is the main reason to use two stacks for a queue?
✗ Incorrect
Two stacks reverse the order twice, achieving FIFO order needed for a queue.
If input stack has [1, 2, 3] (3 on top) and output stack is empty, what will output stack be after one dequeue?
✗ Incorrect
Elements move to output stack reversed: [3, 2, 1], then pop 1, output stack left with [2, 3].
Explain how enqueue and dequeue operations work in a queue implemented using two stacks.
Think about how stacks reverse order to simulate queue behavior.
You got /3 concepts.
Describe the advantages of using two stacks to implement a queue compared to using a single stack.
Focus on order and efficiency.
You got /3 concepts.