Implement a FIFO queue using only two stacks. Support push, pop (remove front), peek (get front), and empty.
Output the result of pop, peek, and empty operations.
Example
Input
push,1;push,2;peek;pop;empty
Output
1
1
False
Reasoning
The input is a sequence of operations separated by semicolons. push,1 means push the value 1; peek, pop and empty take no argument. Only peek, pop and empty produce a line of output, so three operations give three lines.
After push,1 and push,2 the queue holds [1,2] from front to back: 1 arrived first, so it is at the front.
peek reports the front without removing it: 1. The queue is still [1,2].
pop removes and reports the front: 1 again. The queue is now [2].
empty asks whether nothing is left. One element (2) remains, so it prints False.
Notice that a plain stack would have answered 2 to the first peek, because a stack serves the most recent arrival first. The two stacks together must reverse that order so the oldest element always comes out first.
The problem requires implementing a FIFO (First-In-First-Out) queue using only two stacks. A queue is a data structure that follows the FIFO principle, meaning the first element added to the queue will be the first one to be removed. On the other hand, a stack is a LIFO (Last-In-First-Out) data structure, where the last element added to the stack will be the first one to be removed. To implement a queue using stacks, we need to understand how to utilize the LIFO nature of stacks to achieve the FIFO behavior of a queue.
The key concept here is to use two stacks to decouple the enqueuing (adding elements to the queue) and dequeuing (removing elements from the queue) operations. We can use one stack for enqueuing and the other stack for dequeuing. By doing so, we can ensure that the elements are added and removed in the correct order, following the FIFO principle. Understanding the push and pop operations on a stack is crucial, as these operations will be used to implement the queue operations.
To support the push, pop, peek, and empty operations, we need to consider how to handle the elements in the stacks. The push operation will add an element to the end of the queue, the pop operation will remove the element from the front of the queue, the peek operation will return the element at the front of the queue without removing it, and the empty operation will check if the queue is empty. We need to think about how to use the two stacks to implement these operations efficiently.
Algorithm/Approach
The general approach to solve this problem is to use two stacks to implement the queue. One stack will be used to store the new elements added to the queue (enqueuing), and the other stack will be used to store the elements in the correct order for removal (dequeuing). We can use the LIFO nature of the stacks to our advantage by reversing the order of the elements when moving them from one stack to the other. This approach will allow us to achieve the FIFO behavior required by the queue.
PRO
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
PRO
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.