Interchanging Stacks and Queues and Why it Might be Useful
Continuing with the discussion on queues, this is a good opportunity to talk about the key differences between stacks and queues since they have similar operations. In fact, you can implement a stack using queues, and you can implement a queue using stacks. Let’s walk through this in more detail.
To summarize the differences between stacks and queues:
Coding questions like implementing a stack using queues and implementing a queue using stacks can be done with one or two queues, or stacks, respectively.
Learning Data Structures and Algorithms with Music is a reader-supported publication. To receive new posts and support my work, consider becoming a free or paid subscriber.
Let’s start by implementing a stack using one queue.
We can use Python’s deque class like before to take advantage of it’s efficient properties. For the push() operation, we need to implement three steps:
Store the current size of the queue
Append the new item to the rear of the queue
Rotate that many times so that the newest item is at the front of the queue
We rotate the queue by popping the front of the queue and appending to the rear of the queue until we get the order that we want (Last-In First-out or LIFO) for the stack.
# Implement Stack with One Queue
from collections import deque
class MyStack:
def __init__(self):
self.queue = deque()
def push(self, x: int) -> None:
current_size = len(self.queue)
self.queue.append(x) # add the new element to the back of the queue
# Rotate the queue so the newest item ends up at the front.
for i in range(current_size):
self.queue.append(self.queue.popleft()) # move the existing elements to the back of the queue
The pop() operation is easy since we have the deque class because we can simply use the popleft() method, which is O(1), instead of using pop(0) which is O(n).
def pop(self) -> int:
if self.empty():
raise IndexError("Sorry, your stack is empty")
else:
return self.queue.popleft() # removes the item from the front of the queue
For the top() (aka peek()) method, we just want the first item of the queue. Since the push() operation already rotates the newest item to the front of the queue, we just need to reference the first item of the queue by its index 0.
def top(self) -> int: # this is the top for a stack
if self.empty():
raise IndexError("Sorry, your stack is empty")
else:
return self.queue[0] # return the first item of the queue
So the complete implementation of a stack with one queue is:
# Implement Stack with One Queue
from collections import deque
class MyStack:
def __init__(self):
self.queue = deque()
def push(self, x: int) -> None:
current_size = len(self.queue)
self.queue.append(x) # add the new element to the back of the queue
# Rotate the queue so the newest item ends up at the front.
for i in range(current_size):
self.queue.append(self.queue.popleft()) # move the existing elements to the back of the queue
def pop(self) -> int:
if self.empty():
raise IndexError("Sorry, your stack is empty")
else:
return self.queue.popleft() # removes the item from the front of the queue
def top(self) -> int: # this is the top for a stack
if self.empty():
raise IndexError("Sorry, your stack is empty")
else:
return self.queue[0] # return the first item of the queue
def empty(self) -> bool:
return len(self.queue) == 0
Now, let’s implement a stack using two queues.
With two queues, instead of rotating during push(), you make pop() do the work. The key approach is to maintain two queues, a main queue and a helper queue. We keep all elements in the main queue and when we need to pop, we remove all elements except the last one to the helper queue, pop the last one, then swap which queue is the “main” queue. This ensures that the pop() and top() operations return the last added element which is at the front of the main queue.
Beginning with the push() operation, it’s simple, we just append to the main queue. In this code, I call the main queue, queue1, and the helper queue, queue2.
# Implement Stack with Two Queues
from collections import deque
class MyStack:
def __init__(self):
self.queue1 = deque()
self.queue2 = deque()
def push(self, item):
self.queue1.append(item)
Now the pop() operation is where the work begins. We have to implement three steps:
Move all elements except the last one from queue1 to queue2
Pop and return the last element from queue1
Swap queue1 and queue2 , so queue2 becomes the new main queue
The “last element” of queue1 is the element at the back of the queue, which is the last item that was pushed. Since queues are FIFO, when you push items, like 1, 2, 3, 4, the queue looks like [1, 2, 3, 4] where 1 is at the front and 4 is at the back. For a stack, we want to pop 4, the most recently pushed item. So in this case, we need to pop 1, then pop 2, etc until we pop the second to last element. We append those popped elements to the helper queue, queue2. We use popleft() once again since it’s an efficient queue operation that removes from the front. After swapping queue1 and queue2 , we need to clear queue2 and create a new deque object so that we can use it again.
def pop(self):
if self.is_empty():
raise IndexError("Sorry, your stack is empty")
else:
for i in range(len(self.queue1) - 1):
self.queue2.append(self.queue1.popleft())
last_element = self.queue1.popleft()
self.queue1 = self.queue2
self.queue2 = deque()
return last_element
Lastly, the top() operation, we just need the last element that was pushed to the main queue.
def top(self):
if self.is_empty():
raise IndexError("Sorry, your stack is empty")
else:
return self.queue1[-1] # return the last pushed to the queue
Here the the complete implementation:
# Implement Stack with Two Queues
from collections import deque
class MyStack:
def __init__(self):
self.queue1 = deque()
self.queue2 = deque()
def push(self, item):
self.queue1.append(item)
def pop(self):
if self.is_empty():
raise IndexError("Sorry, your stack is empty")
else:
for i in range(len(self.queue1) - 1):
self.queue2.append(self.queue1.popleft())
last_element = self.queue1.popleft()
self.queue1 = self.queue2
self.queue2 = deque()
return last_element
def top(self):
if self.is_empty():
raise IndexError("Sorry, your stack is empty")
else:
return self.queue1[-1] # return the last pushed to the queue
def is_empty(self) -> bool:
return len(self.queue1) == 0
When would you implement a stack using one queue or two queues? The one queue approach has a push() operation that is O(n) and the two queue approach as a pop() operation that is O(n). All of the other operations are basically O(1). So if your code is doing very push-heavy operations, you will want to use the two queue approach and if your code is doing pop-heavy operations, you will want to use the one queue approach.
Let’s implement a queue using two stacks
Implementing a queue with two stacks is a classic coding problem. With two stacks, the key idea is that reversing twice gets you back to the original order. One stack handles input, the other handles output. It’s basically the reverse of implementing a stack with two queues. We will call the main stack, stack1 , and the helper stack, stack2.
So for enqueue() (aka push() or adding items to the queue), you simply push onto stack1.
# Implement a Queue with Two Stacks
class myQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def enqueue(self, item):
self.stack1.append(item)
Now the dequeue() operation is more involved, similar to the pop() operation for the stack with two queues. We need to remove the item from the front of the queue. Say we enqueue 1, 2, 3 into stack1 , they’re stored bottom-to-top as [1, 2, 3]. But a queue should dequeue 1 first (FIFO).
Notice that when you pop everything from stack1 and push onto stack2 , the order reverses : stack2 becomes [3, 2, 1] (bottom-to-top). Now popping from stack2 gives you 1, then 2, then 3 - exactly queue order!
So the steps are:
If stack2 has items, pop from it
If stack2 is empty, transfer all items from stack1 to stack2, then pop
def dequeue(self): # using dequeue instead of pop to differentiate
if self.is_empty():
raise IndexError("Sorry, your queue is empty")
else:
if len(self.stack2) == 0:
for i in range (len(self.stack1)):
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
return self.stack2.pop()
Lastly, the peek() method that returns the front element without removing it by following the same logic as dequeue() - transfer items to stack2 if needed, then look at the top element without removing it.
def peek(self):
if self.is_empty():
raise IndexError("Sorry, your queue is empty")
else:
if len(self.stack2) == 0:
for i in range (len(self.stack1)):
self.stack2.append(self.stack1.pop())
return self.stack2[-1]
return self.stack2[-1]
Here is the complete implementation:
# Implement a Queue with Two Stacks
class myQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def enqueue(self, item): # using enqueue instead of push to differentiate
self.stack1.append(item)
def is_empty(self) -> bool: # only checking if the main stack is empty
return len(self.stack1) == 0 and len(self.stack2) == 0
def dequeue(self): # using dequeue instead of pop to differentiate
if self.is_empty():
raise IndexError("Sorry, your queue is empty")
else:
if len(self.stack2) == 0:
for i in range (len(self.stack1)):
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
return self.stack2.pop()
def peek(self):
if self.is_empty():
raise IndexError("Sorry, your queue is empty")
else:
if len(self.stack2) == 0:
for i in range (len(self.stack1)):
self.stack2.append(self.stack1.pop())
return self.stack2[-1]
return self.stack2[-1]
Implement a queue with one stack
Implementing a queue with one stack is trickier than all of the implementations so far. The reason is we have to introduce a new concept: recursions! Implementing a queue with one stack is not more efficient than using two stacks due to the recursions, but it’s an interesting solution!
Stay tuned for the next post where we go into recursions, how to implement a queue with one stack, and generating recursive fractal melodies using stacks and queues!
Learning Data Structures and Algorithms with Music is a reader-supported publication. To receive new posts and support my work, consider becoming a free or paid subscriber