What will we cover in this tutorial?
We will cover what a Queue is. A Queue is a data structure used by computers. It resembles a queue as we know it.
The key things a Queue should have are efficient operations for insertion (enqueue) and removal (dequeue) of the queue. In this tutorial we will understand what a is, how to represent it, and how to implement the efficient operations.
Step 1: Understand a Queue
A Queue is like a queue in real life.
A Queue is used in computer science in many scenarios. One scenario is when a resource is shared among multiple consumers, then a Queue is set in front.
This resembles the real world, where we use queues in the grocery store, pharmacy, you name it. In all stores, where we have more consumers than registers (the resource) to serve.
A Queue serves the principle, First-in-first-out or FIFO.
A simple diagram shows the operations of a Queue.
The above queue shows the direction of the Queue and the order they have been added symbolized with the numbers 1 to 8, where 8 is about to be added.
The operations on the Queue are as follows.
- enqueue Adds an element to the back of the Queue.
- dequeue Removes the element of the front of the Queue.
Normally, a Queue would also have a function is_empty, which checks whether the Queue is empty.
Step 2: How to represent a Queue item with an element
How do you represent the above items of the Queue?
Well, we need to be able to keep an order of the Queue. Let’s try to draw it and see what we can figure out.
Surprised? Well, the Queue goest from left to right, while the arrows between the items go from right to left.
Actually, the items of the Queue can be represented by a simple Node class.
class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
This simple Node class has an element and the pointer to next_node. Hence, the next_node are the arrows in the diagram above. And the element are representing the numbers in the above diagram. Obviously, the element can contain anything.
Step 3: Create a Queue class to represent the enqueue and dequeue operations
Let’s start in the simple.
The above suggest that if we have head and tail pointer, we can have what we need to implement a Queue data structure.
The enqueue function has the special case where the Queue is empty, otherwise it will do as follows.
- enqueue Create a new Node with the element. Point tails next_node at created Node. Then update tail to point at created Node.
Here we can implement it as follows.
class Queue:
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, element):
if self.head is None:
self.head = self.tail = Node(element)
else:
node = Node(element)
self.tail.next_node = node
self.tail = node
The dequeue is a bit more involved.
- dequeue Get the element from the Node that head points at. If head Node and tail Node is the same (that is if it is the last Node in the Queue), then point tail and head at None. Otherwise, set the head to point at the the next_node head points at.
class Queue:
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, element):
if self.head is None:
self.head = self.tail = Node(element)
else:
node = Node(element)
self.tail.next_node = node
self.tail = node
def dequeue(self):
element = self.head.element
if self.tail == self.head:
self.tail = self.head = None
else:
self.head = self.head.next_node
return element
Notice that the dequeue does fail if the Queue is empty. This is dealt with by creating a is_empty function, which returns whether the Queue is empty.
class Queue:
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, element):
if self.head is None:
self.head = self.tail = Node(element)
else:
node = Node(element)
self.tail.next_node = node
self.tail = node
def dequeue(self):
element = self.head.element
if self.tail == self.head:
self.tail = self.head = None
else:
self.head = self.head.next_node
return element
def is_empty(self):
return self.head is None
That is it.
The full code including a string representation to enable it to be printed
See the full code below. It also contains the __str__(…) function, witch enables it to be printed. Also, how to use it.
class Queue:
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, element):
if self.head is None:
self.head = self.tail = Node(element)
else:
node = Node(element)
self.tail.next_node = node
self.tail = node
def dequeue(self):
element = self.head.element
if self.tail == self.head:
self.tail = self.head = None
else:
self.head = self.head.next_node
return element
def is_empty(self):
return self.head is None
def __str__(self):
if self.head is None:
return None
node = self.head
result = "["
while node is not None:
result += str(node.element) + " "
node = node.next_node
return result[:-1] + "]"
q = Queue()
for i in range(10):
q.enqueue(i)
while not q.is_empty():
print(q.dequeue(), '', end='')
The above code will result in the following output.
[0 1 2 3 4 5 6 7 8 9] 0 1 2 3 4 5 6 7 8 9
