Solution: Implement Queue Using Stacks
Let’s solve the Implement Queue Using Stacks problem.
Statement
Design a queue data structure using only two stacks and implement the following functions:
enqueue(int x): Inserts a value to the back of the queue.dequeue(): Removes and returns the value from the front of the queue.
Constraints:
-
x
Solution 1: Queue with efficient dequeue()
A queue is a first in, first out (FIFO) data structure, while a stack is a last in, first out (LIFO) data structure. To implement queue functionality with a stack, we need to reverse the order of the stack so that the oldest value is at the top of the stack and the newly inserted value is at the bottom.
In this solution, we are using two stacks: a main stack and a temporary stack. The main stack stores all the queue elements, whereas the temporary stack is a temporary buffer to provide queue functionality.
In every enqueue() operation, we first transfer all the elements from the main stack to the temporary stack and then push the new value to the empty main stack so that the newly inserted value is at the bottom of the main stack. Then, we transfer all the elements from the temporary stack to the main stack, reversing the order of the values in the main stack.
The dequeue() operation is very efficient since the main stack is already reversed. Therefore, we just pop the oldest value from the top of the main stack.
Here are the detailed steps of this solution:
-
Initialize two stacks,
main_stackandtemp_stack, with empty lists. -
enqueue(): Whenever a new value is to be inserted, we pop all values frommain_stackand push them intotemp_stackso that the new value is pushed to the bottom ofmain_stack. We then pop the elements fromtemp_stack...