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.
Click to reveal answer
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.
Click to reveal answer
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.
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) always; dequeue is amortized O(1) because elements are moved between stacks only when needed.
Click to reveal answer
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.
Click to reveal answer
Which stack holds elements in reversed order to simulate queue dequeue?
✗ Incorrect
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?
✗ Incorrect
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?
✗ Incorrect
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?
✗ Incorrect
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?
✗ Incorrect
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.
You got /4 concepts.
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.
You got /4 concepts.