Solution: Implement Queue Using Stacks
Explore how to design a queue with two stacks by implementing enqueue and dequeue functions efficiently. This lesson helps you understand the mechanics of using stacks to simulate queue behavior, analyze time and space complexity, and compare two common solutions to optimize either enqueue or dequeue operations.
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...