Cue the queues
Queues are data structures that follow the same principle as joining a line, which is “First-in, First-out,” or FIFO. Just like waiting in line, the first item in the queue is the first to leave the queue. It is the data structure that ensures fairness. We have the same three operations for queues that we use for stacks but what’s different are the locations of these operations:
push : add an item to the end of the queue. This is also known as enqueue.
pop : remove the first item of the queue and return it. This is also known as dequeue.
peek: look at the first item in the queue without removing it.
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.
You can implement queues using arrays or linked lists. Similar to stacks implemented with linked lists, you can overcome memory issues when you implement queues with linked lists. Here is an implementation with arrays (i.e. lists):
class Queue:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if self.is_empty():
raise IndexError("Sorry, your queue is empty")
else:
return self.items.pop(0) # removes the item from the beginning of the list
def peek(self):
if self.is_empty():
raise IndexError("Sorry, your queue is empty")
else:
return self.items[0] # return the first item of the list
def is_empty(self):
return self.items == []
The only issue with this implementation is the pop(0) function. It actually is O(n) because it shifts all remaining elements. To run O(1) and have better performance with large queues, we could use the Python class deque (pronounced “deck”) instead of a list. Deques are a generalization of stacks and queues and the name short for “Double-Ended QUEue”. Deques support memory efficient appends and pops from each end with approximately O(1) performance in either direction. Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) operations. Fixed-length operations are operations that don’t change the list’s size. The memory movement cost is from shifting all remaining elements one position to the left. We can use popleft() to remove an item from the front of the list.
# Queue with popleft
from collections import deque
class Queue_v2:
def __init__(self):
self.items = deque() # initialize the deque
def push(self, item):
self.items.append(item) # add an item to the end of the list
def pop(self):
if self.is_empty():
raise IndexError("Sorry, your queue is empty")
else:
return self.items.popleft() # removes the item from the beginning of the list
def peek(self):
if self.is_empty():
raise IndexError("Sorry, your queue is empty")
else:
return self.items[0] # return the first item of the list
def is_empty(self):
return len(self.items) == 0 # if there are no items in the list, it's empty.
Because queues move from the front to the end, e.g. first item → second item → - - - → last item, if we use arrays to implement the queues, then we may encounter the same memory issues that occur with array-based stacks. We can use dynamic memory using linked lists that don’t have a fixed size limit. Technically, my array-based implementation is dynamic because Python’s lists are dynamic lists, meaning that they grow automatically as needed.
There are a few nuances to discuss with the linked-list implementation of queues. The biggest difference between implementing linked-lists for stacks versus queues is that queues have two pointers, one for the front of the queue and one for the end of the queue, while stacks only need one pointer. We first create our Node class, similar to the stack implementation. We update the initializer init with the front and end of the queue as Node objects or None.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue_v3:
def __init__(self):
self.front: Node | None = None
self.end: Node | None = None
The push() method needs some updates. First, we need to check if the queue is empty before we attempt to push an item. If the queue is empty, then we point the front and end of the queue to the same node. If it’s not empty, then we point the old end to the new node and we set the end to the new node, in that order.
def push(self, data):
node = Node(data)
if self.is_empty():
self.front = node
self.end = node
else:
self.end.next = node # old end points to the new node
self.end = node # the end becomes the new node. Note that the order matters
The pop() method also has an edge case. If we pop an item from the queue and the queue becomes empty, we have to figure out what happens to the pointers, now that we have two pointers. The front node will become None, but we need to set the end node to be None too. So we need to add a check after we pop an item to see if the queue is empty and if so, set the end node to None. That way, if we use the queue in the future, all of the pointers point to None since it’s empty.
def pop(self):
if self.is_empty():
raise IndexError("Sorry, your queue is empty")
else:
element = self.front.data # remove item from the front of the list
self.front = self.front.next
if self.front == None: # if the queue becomes empty after popping the front item, then set end to be None too
self.end = None
return element
Here is the full implementation of a queue with linked lists:
# Linked list implementation of Queues
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue_v3:
def __init__(self):
self.front: Node | None = None
self.end: Node | None = None
def push(self, data):
node = Node(data)
if self.is_empty():
self.front = node
self.end = node
else:
self.end.next = node # old end points to the new node
self.end = node # the end becomes the new node. Note that the order matters
def pop(self):
if self.is_empty():
raise IndexError("Sorry, your queue is empty")
else:
element = self.front.data # remove item from the front of the list
self.front = self.front.next
if self.front == None: # if the queue becomes empty after popping the front item, then set end to be None too
self.end = None
return element
def peek(self):
if self.is_empty():
raise IndexError("Sorry, your queue is empty")
return self.front.data # look at the first item
def is_empty(self):
return self.front == None
Wonderful! Queues have many applications in tasks related to the order of arrival, such as scheduling, printing, and call centers. For music, one useful application of queues is for creating playlists, where you play music in the order of the songs in the list (i.e. first song, then second song, to the last song).
In the next posts, I’ll write about how we can use stacks to implement queues and vice versa, and I’ll explore how we can use queues to create a music player. Stay tuned!
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