232. Implement Queue using Stacks
Problem Description
The task is to implement a queue with the FIFO (first in, first out) principle using two stacks. In a typical queue, elements are added, or 'pushed', to the back and removed, or 'popped', from the front. Additionally, you should be able to 'peek' at the element at the front without removing it and test if the queue is 'empty'. This should be done using only the standard operations of a stack: 'push to top', 'peek/pop from top', 'size', and 'is empty'.
Intuition
The key to solving this problem is to use two stacks, stk1
and stk2
, to invert the order of elements twice so that they come out in the same order that they went in. Initially, all new elements are pushed onto stk1
. However, we can't directly pop from stk1
for the queue's pop
operation because stacks follow LIFO order. So, to get the FIFO order of a queue, we reverse stk1
by popping all its elements and pushing them onto stk2
. The first element pushed into stk1
(and therefore the first in queue order) is now at the top of stk2
, allowing us to perform the FIFO pop
correctly.
The move
method is our helper that handles this transfer if stk2
is empty. It is lazily called only when necessary (when popping or peeking). This efficiency is important as it minimizes the number of operations. Once all elements are transferred to stk2
, they can be popped or peeked in the correct FIFO order.
The empty
method simply checks both stacks. If both are empty, the queue is empty.
The elegance of this solution arises from the delayed transfer of elements until necessary (amortized analysis), which minimizes the number of total operations needed.
Solution Approach
The implementation consists of the following steps, utilizing two stacks, stk1
and stk2
, which are simply represented as Python lists:
-
Constructor (
__init__
): Two empty stacks are initialized.stk1
is for adding new elements (push operation), andstk2
is used for FIFO retrieval (pop and peek operations).self.stk1 = [] self.stk2 = []
-
Push Operation (
push
): Elements are added tostk1
. Each new element is simply appended to the end ofstk1
, which is the top of the stack.def push(self, x: int) -> None: self.stk1.append(x)
-
Pop Operation (
pop
): To remove an element from the front of the queue, we need to get it from the bottom ofstk1
. Themove
method is called to transfer elements fromstk1
tostk2
, ifstk2
is empty, effectively reversing the stack order. The element at the top ofstk2
(the front of the queue) is then popped.def pop(self) -> int: self.move() return self.stk2.pop()
-
Peek Operation (
peek
): Similar to pop, but instead of removing the element at the front of the queue, we only retrieve it.move
ensures the element is moved tostk2
so that it can be peeked at.def peek(self) -> int: self.move() return self.stk2[-1]
-
Empty Operation (
empty
): This operation checks if bothstk1
andstk2
are empty. The queue is empty if and only if both stacks are empty.def empty(self) -> bool: return not self.stk1 and not self.stk2
-
Move Helper Method (
move
): This is an essential method that transfers elements fromstk1
tostk2
whenstk2
is empty. It's called only before a pop or peek operation and only when necessary (i.e., whenstk2
is empty and the next front of the queue needs to be accessed).def move(self): if not self.stk2: while self.stk1: self.stk2.append(self.stk1.pop())
At its core, this approach leverages the fact that the stack data structure (using append
and pop
in Python lists) can be reversed by transferring elements from one stack to another. By having two stacks, we can ensure elements are in the correct FIFO order for queue operations by handling elements in the 'lazy' manner - that is, by only moving elements when absolutely necessary.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate how the queue implementation using two stacksāstk1
and stk2
āworks.
Consider the following sequence of operations:
push(1)
- Add the element '1' to the queue.push(2)
- Add the element '2' to the queue after '1'.peek()
- Get the element at the front of the queue without removing it.pop()
- Remove the element from the front of the queue.empty()
- Check if the queue is empty.
Now let's examine how each operation is handled:
- push(1):
stk1
receives the element as[1]
.stk2
remains[]
. - push(2):
stk1
grows to[1, 2]
.stk2
is still[]
. - peek(): We want to see the front element of the queue, which is '1'. However, since
stk1
is LIFO, we need to move elements tostk2
to access '1'.move()
is called, transferring all elements fromstk1
tostk2
, resulting instk1
as[]
andstk2
as[2, 1]
. Now we can peek the top ofstk2
which is '1', the first element. - pop(): We need to pop the front element, which is '1'. Since
stk2
already has the correct order, we simply pop fromstk2
.stk2
becomes[2]
after popping '1', andstk1
is still[]
. - empty(): To determine if the queue is empty, we check if both
stk1
andstk2
are empty. Sincestk2
has an element '2', the method returnsFalse
, indicating the queue is not empty.
The sequence of stk1
and stk2
after each operation is shown below:
- After
push(1)
:stk1: [1], stk2: []
- After
push(2)
:stk1: [1, 2], stk2: []
- After
peek()
:stk1: [], stk2: [2, 1]
- After
pop()
:stk1: [], stk2: [2]
- After
empty()
: No change in stacks,stk1: [], stk2: [2]
The queue is operational, demonstrating that two stacks used in this manner can effectively implement a FIFO queue.
Solution Implementation
1class MyQueue:
2 def __init__(self):
3 # Initialize two stacks
4 self.in_stack = []
5 self.out_stack = []
6
7 def push(self, x: int) -> None:
8 # Push an element onto the end of the queue
9 self.in_stack.append(x)
10
11 def pop(self) -> int:
12 # Pop an element from the start of the queue
13 self._shift_stacks()
14 return self.out_stack.pop()
15
16 def peek(self) -> int:
17 # Get the front element
18 self._shift_stacks()
19 return self.out_stack[-1]
20
21 def empty(self) -> bool:
22 # Return True if the queue is empty, False otherwise
23 return not self.in_stack and not self.out_stack
24
25 def _shift_stacks(self):
26 # Move elements from in_stack to out_stack if out_stack is empty
27 if not self.out_stack:
28 while self.in_stack:
29 self.out_stack.append(self.in_stack.pop())
30
31# The MyQueue object will be instantiated and called as following:
32# obj = MyQueue()
33# obj.push(x)
34# param_2 = obj.pop()
35# param_3 = obj.peek()
36# param_4 = obj.empty()
37
1class MyQueue {
2 // Use two stacks to simulate a queue:
3 // stkInput is used for input operations (push)
4 // stkOutput is used for output operations (pop and peek)
5 private Deque<Integer> stkInput = new ArrayDeque<>();
6 private Deque<Integer> stkOutput = new ArrayDeque<>();
7
8 // Constructor for MyQueue. No initialization needed as
9 // member variables are already initialized.
10 public MyQueue() {
11 }
12
13 // Push element x to the back of the queue. Since a stack is LIFO (last-in, first-out),
14 // pushing to stkInput will reverse the order when transferred to stkOutput.
15 public void push(int x) {
16 stkInput.push(x);
17 }
18
19 // Pop the element from the front of the queue.
20 // If stkOutput is empty, refill it by popping all elements
21 // from stkInput and pushing them into stkOutput.
22 public int pop() {
23 move();
24 return stkOutput.pop();
25 }
26
27 // Get the front element.
28 // Similar to pop, ensure stkOutput contains elements by moving
29 // them from stkInput if necessary and then return the top element.
30 public int peek() {
31 move();
32 return stkOutput.peek();
33 }
34
35 // Return true if the queue is empty, which is when both stacks are empty.
36 public boolean empty() {
37 return stkInput.isEmpty() && stkOutput.isEmpty();
38 }
39
40 // Helper method to move elements from stkInput to stkOutput. It ensures that
41 // stkOutput contains elements in correct queue order for peeking or popping.
42 private void move() {
43 // Only move elements if stkOutput is empty.
44 if (stkOutput.isEmpty()) {
45 // Move all elements from stkInput to stkOutput.
46 while (!stkInput.isEmpty()) {
47 stkOutput.push(stkInput.pop());
48 }
49 }
50 }
51}
52
53/**
54 * The following operations demonstrate how to instantiate and operate on the MyQueue object:
55 *
56 * MyQueue obj = new MyQueue(); // Creates an instance of MyQueue
57 * obj.push(x); // Pushes element x to the back of the queue
58 * int param_2 = obj.pop(); // Retrieves and removes the front element of the queue
59 * int param_3 = obj.peek(); // Retrieves but does not remove the front element of the queue
60 * boolean param_4 = obj.empty(); // Checks whether the queue is empty
61 */
62
1#include <stack>
2using std::stack;
3
4class MyQueue {
5public:
6 // Constructor for MyQueue doesn't need to do anything since
7 // the standard library stack initializes itself
8 MyQueue() {}
9
10 // Adds an element to the back of the queue
11 void push(int x) {
12 inputStack.push(x);
13 }
14
15 // Removes the element from the front of the queue and returns it
16 int pop() {
17 prepareOutputStack();
18 int element = outputStack.top(); // Save the top element
19 outputStack.pop(); // Remove element from stack
20 return element; // Return the saved element
21 }
22
23 // Returns the element at the front of the queue without removing it
24 int peek() {
25 prepareOutputStack();
26 return outputStack.top(); // Return the top element
27 }
28
29 // Checks if the queue is empty
30 bool empty() {
31 // The queue is empty only if both stacks are empty
32 return inputStack.empty() && outputStack.empty();
33 }
34
35private:
36 stack<int> inputStack; // Stack for enqueuing elements
37 stack<int> outputStack; // Stack for dequeuing elements
38
39 // Helper function to move elements from inputStack to outputStack
40 void prepareOutputStack() {
41 // Only move elements if outputStack is empty
42 if (outputStack.empty()) {
43 while (!inputStack.empty()) {
44 outputStack.push(inputStack.top()); // Move element to outputStack
45 inputStack.pop(); // Remove it from inputStack
46 }
47 }
48 }
49};
50
51/**
52 * Example usage:
53 * MyQueue* queue = new MyQueue();
54 * queue->push(1);
55 * queue->push(2);
56 * int elem1 = queue->pop(); // returns 1
57 * int elem2 = queue->peek(); // returns 2, the new front after popping 1
58 * bool empty = queue->empty(); // returns false since there's still 2 in the queue
59 * delete queue; // Don't forget to free memory
60 */
61
1// These arrays will act as the stack containers for the queue.
2let stack1: number[] = [];
3let stack2: number[] = [];
4
5// This function simulates the push operation of a queue, where 'x' is the element to be added to the queue.
6function push(x: number): void {
7 stack1.push(x);
8}
9
10// This function simulates the pop operation of a queue, by moving elements from the first stack to the second if necessary.
11function pop(): number {
12 moveStacks();
13 return stack2.pop();
14}
15
16// This function simulates the peek operation of a queue, returning the element at the front without removing it.
17function peek(): number {
18 moveStacks();
19 return stack2[stack2.length - 1];
20}
21
22// This function checks whether the queue is empty.
23function empty(): boolean {
24 return stack1.length === 0 && stack2.length === 0;
25}
26
27// This helper function moves elements from stack1 to stack2 if stack2 is empty, effectively reversing the order to simulate queue behavior.
28function moveStacks(): void {
29 if (stack2.length === 0) {
30 while (stack1.length !== 0) {
31 stack2.push(stack1.pop());
32 }
33 }
34}
35
36// Usage
37// Instead of creating an instance of MyQueue, you would directly call the functions:
38push(1);
39let val1 = pop();
40let val2 = peek();
41let isEmpty = empty();
42
Time and Space Complexity
Time Complexity:
__init__()
: O(1) - Initializing two empty stacks takes constant time.push(x)
: O(1) - Append operation on a list (stack) is an amortized constant time operation.pop()
: Amortized O(1) - In the worst case, this operation can be O(n), where n is the number of elements instk1
, because it has to move all elements fromstk1
tostk2
ifstk2
is empty. However, each element is only moved once due to the two-stack arrangement, and, across a series ofm
operations, this gives an average (or amortized) time complexity of O(1).peek()
: Amortized O(1) - Similar topop()
, it may involve moving all elements fromstk1
tostk2
in the worst case, but due to the amortized analysis, it averages to constant time.empty()
: O(1) - Checking if two lists are empty is a constant time operation.move()
: Amortized O(1) - Although it can be O(n) in the worst case when moving all elements fromstk1
tostk2
, it is part of thepop()
andpeek()
operations and contributes to their amortized time complexity.
Space Complexity:
- Overall space complexity for the
MyQueue
class is O(n), where n is the number of elements in the queue at a given time. This is because all elements are stored in two stacks (stk1
andstk2
). No additional space is used that is proportional to the number of elements in the queue except for these two stacks.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!