Queue data structure
You’re at a reception desk. There are four people waiting in front of you and you have to wait for your turn. That’s how queues work. The queue is a data structure where the first elements to arrive are the first to be served. First come, first served or “First In First Out”.
This data structure permits two operations:
- Enqueue - inserts an element into a queue
- Dequeue - removes an element from a queue
This is my implementation (Python) with linked lists:
class Queue: def __init__(self): self.head = None self.tail = None def Enqueue(self, obj): node = QueueNode(obj) if self.tail is None: self.head = node else: self.tail.next = node self.tail = node def Dequeue(self): if self.head is None: return None else: node = self.head if self.head.next is None: self.head = None self.tail = None else: self.head = self.head.next return node.item class QueueNode: def __init__(self, item): self.item = item self.next = None
When the queue object is created, the head and tail properties are set to None. The ‘head’ references the first item to be processed and the ‘tail’ references the last node in the queue after wich we add the new node.
When an object is enqueued (added to the queue) we create a node object. Then we have to check if the queue is empty. If it is, the ‘head’ and ‘tail’ both point to that node. If it’s not, the ‘next’ property of the last node (referenced by ‘tail’) is set to the new node.
When we want to dequeue an object, we have to check if the queue is empty. If it is, the method returns nothing. If it’s not, we get the node and the ‘head’ now points to the next node in the queue (self.head.next). If there are no more nodes in the queue, both ‘head’ and ‘tail’ are set to None. In the end, the object is returned by ‘return node.item’.
This is the basic functionality of the queue data structure.
queue = Queue() # creates the queue object queue.Enqueue(10) # enqueue queue.Enqueue(99) # enqueue print queue.Dequeue() # 10 print queue.Dequeue() # 99