We’ve talked about stacks, so now let’s talk about queues. As a brief recap, a queue is just an order where the first item in an order is the first one to be taken care of.
And as you can probably imagine, they’re the opposite of stacks.
Queue Implementation using Lists
Let’s jump into a queue implementation using a Python list:
class Queue:
"""
Queue Python class using a list.
"""
def __init__(self): # Construct Queue object.
self.queue = [] # Initialize an empty list to make the queue.
def size(self): # Get the size of the queue.
return len(self.queue)
def enqueue(self, value): # Add an item to the queue.
self.queue.append(value)
def dequeue(self): # Remove first item from the queue.
if self.queue: # Check if the queue has at least one element.
return self.queue.pop(0)
def peek(self): # Peek the first item of the queue.
if self.queue: # Check if the queue has at least one element.
return self.queue[0]
def print(self): # Print out the queue.
print(self.queue)
It should be pretty straight-forward from the code, but basically the functions are:
- enqueue() – add an element to queue
- dequeue() – return and pop the first element from the queue
- peek() – view the first element in the queue
- print() – print out the queue
Now, let’s try simulating a queue in a bank.
>>> queue = Queue() # Assume this is a queue at some bank.
>>> queue.enqueue("Bob") # Add Bob to the queue.
>>> queue.enqueue("Alex") # Alex Alex to the queue.
>>> queue.enqueue("Sarah") # Add Sarah to the queue.
>>> queue.enqueue("Daniel") # Add Daniel to the queue.
>>> queue.peek() # Peek the first person to be taken care of.
'Bob'
>>> queue.print() # Print the queue.
['Bob', 'Alex', 'Sarah', 'Daniel']
>>> queue.dequeue() # Take care of Bob as he's first in line.
'Bob'
>>> queue.dequeue() # Take care of Alex as he's first in line.
'Alex'
>>> queue.dequeue() # Take care of Sarah as she's first in line.
'Sarah'
>>> queue.peek() # View first in line. Only Daniel is left, so he'll be the first.
'Daniel'
>>> queue.dequeue() # Take care of Daniel as well.
'Daniel'
>>> queue.dequeue() # There is no one left, so nothing to dequeue.
>>> queue.peek() # There is no one left, so nothing to peek.
>>> queue.print() # It's an empty queue, so the collection is empty.
[]
Pretty straightforward stuff. Let’s implement it using a linked list now.
Queue Implementation using a Linked List
If you don’t know what a linked list is, I’d recommend looking them up before continuing. As a super brief summary, a linked list consists of nodes that contain a value and a pointer to the next node.
So, say we have our first node with a value of 5 and it pointing to nothing. It’d look like:
[5] -> Nothing.
Now, let’s add another node with a value of 6 and have our previous node refer to it.
[5] -> [6] -> Nothing.
Our node with a value of 6 doesn’t point to anything. We can have it point to a node with a value of 1 that points to nothing finally.
[5] -> [6] -> [1] -> Nothing.
So, with this intuition in mind, we can create a queue using a linked list in a similar fashion. The first node in the linked list will be the first one to taken care of. The ones after it will be processed in their place of order.
Here’s the code:
class Node: # Base node class to use for our linked list.
def __init__(self, value): # Node constructor.
self.value = value # Set the value to the one passed.
self.next = None # Initially, the next pointer is set to None.
class QueueLinkedList:
"""
Queue Implementation using a Linked List
"""
def __init__(self): # Initial Constructor
self.front = None # This is our pointer to the front of the queue. Used to dequeue.
self.end = None # This is our pointer to the end of the queue. Used to enqueue.
self.length = 0 # Length of our queue.
def size(self): # Get the size of the queue.
return self.length
def peek(self): # Peek the beginning of the queue if exists.
if self.front: # If the queue exists, return the value of the front of the queue.
return self.front.value
def enqueue(self, value): # Enqueue (add) to end of queue.
if not self.end: # If there isn't an end of the queue, that must mean there is no queue.
self.front = Node(value) # Set front of the queue to what we want to enqueue.
self.end = self.front # Set end of the queue equal to the front as there's only one item in the queue.
else: # If there is an end of the queue, create a node and set the end equal to the new node.
node = Node(value) # Create a new node.
self.end.next = node # Set previous end's next pointer to this new node.
self.end = node # Point the end to our new node.
self.length += 1 # Increment the length by 1.
def dequeue(self): # Dequeue (remove) an item from the queue.
if self.front: # If the front exists, then dequeue.
temp = self.front # Save a temporary reference to the front variable, so we can return its value.
self.front = self.front.next # Set the front reference now to what is next in line.
if not self.front: # If the front is now empty, this means the queue is empty.
self.end = None # Let's also reset the end to be None.
self.length -= 1 # Decrement the length by 1.
return temp.value # Return the value of the dequeued item.
def print(self): # Print out a visual representation of how the queue looks.
print("[", end="") # Print '[' initially.
front = self.front
while front: # Iterate through the front until it is empty.
if front.next: # If there is a next pointer, print a comma.
print(front.value, end=", ")
else: # If there is no next pointer, don't print a comma.
print(f'{front.value}', end="")
front = front.next # Set the front to its next node.
print("]") # Print the closing ']'.
The comments on the code should make it pretty self-explanatory what is happening. However, I’ll admit I was a bit confused when I wrote the dequeue and enqueue logic with the self.front and self.end references. But basically, note how the only logical way the queue can start is by enqueueing to it.
When we first enqueue to it, our self.end reference is None, so we create a new node and set it equal to the self.front reference. We then also set the self.end reference equal to the self.front reference.
Visually, it looks like this:
node = Node(5) # Let's say 5 is our initial node. self.front = node # Point the front to the new node. self.end = self.front # Point the end to self.front.
Now, let’s enqueue. Our self.end exists now, so we follow the logic in the else statement.
def enqueue(self, value): # Enqueue (add) to end of queue.
if not self.end: # If there isn't an end of the queue, that must mean there is no queue.
self.front = Node(value) # Set front of the queue to what we want to enqueue.
self.end = self.front # Set end of the queue equal to the front as there's only one item in the queue.
else: # If there is an end of the queue, create a node and set the end equal to the new node.
node = Node(value) # Create a new node.
self.end.next = node # Set previous end's next pointer to this new node.
self.end = node # Point the end to our new node.
So, we create a new node with the value specified. We then set the end’s next reference to the new node then re-reference self.end to the new node. This may sound confusing. But, remember how self.end was pointing to the self.front in our very first enqueue? This way, the self.front pointer also has its next reference updated with this logic.
No matter what, self.end is a just a reference to self.front’s next (or self.front’s next’s next’s next…), so we can enqueue continuously and have it update self.front as well. Basically, self.end is just the last reference of self.front’s next pointers.
I was confused here too, so if you still don’t understand, just try to re-look over the code logic.
Moving on, let’s simulate the same bank queue using this linked list implementation.
>>> queue = QueueLinkedList() # Initialize our queue using a linked list.
>>> queue.enqueue("Bob") # Add Bob to the queue.
>>> queue.enqueue("Alex") # Add Alex to the queue.
>>> queue.enqueue("Sarah") # Add Sarah to the queue.
>>> queue.enqueue("Daniel") # Add Daniel to the queue.
>>> queue.peek() # Peek the first person in the queue. It's Bob, as he was the first.
'Bob'
>>> queue.print() # Print out a visual representation of the queue.
[Bob, Alex, Sarah, Daniel]
>>> queue.dequeue() # Remove the first person in line from the queue. It's Bob as he is the first.
'Bob'
>>> queue.dequeue() # Remove the next person in line from the queue.
'Alex'
>>> queue.dequeue() # Again, remove the next person in line from the queue.
'Sarah'
>>> queue.peek() # Since we are done up to Sarah, the next person in the line is Daniel.
'Daniel'
>>> queue.dequeue() # Remove Daniel from the line.
'Daniel'
>>> queue.dequeue() # We now have no one left in the line.
>>> queue.peek() # Peek the first person in the line. There's no one left.
>>> queue.print() # Print the queue. It's empty, so the list is empty.
[]
>>> queue.size() # We've removed everyone from the queue, so the queue's size is 0.
0
Not too shabby, huh? Let’s run a benchmark to see which one is faster.
def benchmark(size): # Run a benchmark test with the size provided.
import time # We will need to import time to see the elapsed time.
from collections import deque # We'll finally compare with Python's built in deque.
listQueue = Queue() # Create a Queue object made from a list.
linkedListQueue = QueueLinkedList() # Create a Queue object made from a linked list.
pythonQueue = deque() # Create a Queue object from Python's built-in deque.
elements = [x for x in range(size)] # Get numbers from 0 up to size - 1 provided.
time1 = time.time() # Let's test the list implementation first.
for element in elements: # Add all the elements to the list queue.
listQueue.enqueue(element)
while listQueue.size() != 0: # Remove all the elements from the list queue.
listQueue.dequeue()
print(f'It took {time.time() - time1} seconds for the queue implemented using a list.')
time1 = time.time() # Now, let's test the linked list implementation.
for element in elements: # Add all the elements to the linked list queue.
linkedListQueue.enqueue(element)
while linkedListQueue.size() != 0: # Remove all the elements from the linked list queue.
linkedListQueue.dequeue()
print(f'It took {time.time() - time1} seconds for the queue implemented using a linked list.')
time1 = time.time() # Now, let's test using a deque.
for element in elements: # Add all the elements to the deque.
pythonQueue.append(element)
while len(pythonQueue) != 0: # Remove all the elements from the deque.
pythonQueue.popleft()
print(f'It took {time.time() - time1} seconds for the queue implemented using a deque.')
Results when you benchmark the queues with 50,000 elements:
>>> benchmark(50000) It took 0.3847627639770508 seconds for the queue implemented using a list. It took 0.07395482063293457 seconds for the queue implemented using a linked list. It took 0.007994890213012695 seconds for the queue implemented using a deque.
Results when you benchmark the queues with 500,000 elements:
>>> benchmark(500000) It took 43.67021727561951 seconds for the queue implemented using a list. It took 0.9469020366668701 seconds for the queue implemented using a linked list. It took 0.12399506568908691 seconds for the queue implemented using a deque.
The list implementation is incredibly slow. This is not surprising as Python has to remove the first element from the array then shift all the remaining elements of the array one step to the left of the array.
Here’s an example.
array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] array.pop(0) # All the elements now have to be shifted one to the left. array = [2, 3, 4, 5, 6, 7, 8, 9] array.pop(0) array = [3, 4, 5, 6, 7, 8, 9] # Basically, all the indices have to shift one to the left on each pop(0). # For example, the value 3 was at index 2 (index 2 because we start from index 0). # In our third iteration, the value 3 was at index 0. # So, basically, Python has to shift everything in each pop(0) leading to horrible performance.
The time complexity is O(N) to remove using a list with N being the amount of elements in the list. The time complexity is O(1) using a linked list or deque, because all they have to do is one operation: re-assign the head pointer. So that is why they are much faster. And in terms of comparing deques and our implementation using a linked list, the deque is faster as it is implemented in C.
All in all, if you’re working with a queue of some sort in Python, always use a deque, and try to refrain from using Python’s built-in list.
Well, that was a long article, and this pretty much sums up our discussion of queues. If you made it this far, thanks for reading. Hope you learned something new. If I made a mistake or if you need clarification on something, feel free to let me know through the comments down below.