Queues

Just like queuing for a bus, a queue, in computer science, is a first in first out (FIFO) data structure.

OK so you’re all waiting in a queue for the bus and as more people arrive they join the back of the queue. When the bus arrives the person at the front of the queue hops on, and then the next and the next until the bus is full or the queue is empty. This is how a queue data structure operates.

The only real difference is that in a bus queue the people shuffle forward each time someone gets on the bus. This shuffling doesn’t necessarily happen in a queue data structure.

A queue uses the following operations:

• Enqueue – add an item to the BACK of the queue
• Dequeue – remove an item from the FRONT of the queue

In order to carry out these operations you’ll need two pointers:

• Front – points to the first item in the queue i.e. the next item to be dequeued
• Rear – points to the back of the queue i.e. the last item in the queue

You’ll also need to know about these possible error states:

• Queue is empty – what happens when you try and dequeue (remove) an item from an empty queue
• Queue is full – what happens when you try and enqueue (add) an item when the queue is full

Linear Queue

This is the just like the bus queue. A major problem with this queue is that, if our queue has a finite size then, as we dequeue and enqueue items we will eventually run out of space. We can get around this by shuffling the items in the queue forward every time we enqueue an item but the shuffling operation is hugely inefficient.

Circular Queue

The circular queue overcomes the limitations of the linear queue. It’s like joining the end of the linear queue to its front to make a circle. There’s a more comprehensive explanation with diagrams here. I’ve included a example program for a circular queue below.

Priority Queue

A priority queue just means that, as well as their position in the queue, items are given a priority. A good example of this would be a print queue where print jobs can have high, normal and low priorities. A print job with a high priority would be dealt with before one with normal or low priority even it it was behind it in the queue.

Useful links

• Isaac Computer Science – Queues
• Craig ‘n Dave – Stacks and Queues Part 1
• Craig ‘n Dave – Stacks and Queues Part 2

Example Python Program

class Circular_queue():
    def __init__(self, max_size):
        self.max_size = max_size
        self.queue = [None] * max_size
        self.front = 0
        self.rear = -1
        self.item_count = 0

    def is_full(self):
        return self.item_count == self.max_size

    def is_empty(self):
        return self.item_count == 0

    def enqueue(self, item):
        if self.is_full():
            return None
        self.rear = (self.rear + 1) % self.max_size
        self.queue[self.rear] = item
        self.item_count += 1

    def dequeue(self):
        if self.is_empty():
            return None
        item = self.queue[self.front]
        self.front = (self.front + 1) % self.max_size
        self.item_count -= 1
        return item
        
    def contents(self):
        for i in range(self.front, self.item_count + self.front):
            print(self.queue[i % self.max_size], end=" ")
        print()

Program Notes

This program uses a list to hold the data in the queue initially setting each element in the list to None. It shows how the dequeue and enqueue operations work. Note that if you were to implement a queue in Python then ‘deque’ in the collections library would be a much better choice – see here.

__init__()

• this is the constructor and is run every time a Circular_Queue object is created (instantiated)
• sets the max_size of queue
• creates a blank queue using a list and sets each element to None
• sets a pointer to the front of the queue – this will be zero as soon as we add the first item so we can safely set it to zero now
• sets a pointer to the rear of the queue – we set this to -1 so that as soon as the first item is added both the rear and front pointer will point to the first element in the list

is_full()

• if the number of items in the queue is the same as the max size of the queue then we know it is full

is_empty()

• if the number of items in the queue is 0 then we know the queue is empty

enqueue()

• if there is no space in the queue
  • return None
• else
  • increment the rear pointer – note that we mod this by the max size of the queue so that if adding 1 takes the pointer past the end of the list it will point at the first element in the list (circular!)
  • add the item to the list at element the rear pointer now points to
  • increment the count of the number of items in the queue

dequeue()

• if the queue is empty ie there is nothing to dequeue
  • return None
• else
  • store the item to dequeue (the item at the frnt of the queue)
  • increment the front pointer – see note above about incrementing rear pointer
  • decrement the count of the number of items in the queue
  • return the item we took off the queue

contents()

• this isn’t part of the circular queue implementation but is a useful method for displaying the contents of the queue