[Data Structure] Circular Queue (ADT)

Circular Queue

A queue is an ADT in which items are inserted at the end of the queue and removed from the front of the queue.

The queue enqueue oepration inserts an item at the end of the queue.

The queue dequeue operation removes and returns the item at the front of the queue.

 

A queue is reffered to as a first-in first-out (FIFO) ADT. 

Remembering queue = FIFO and stack = LIFO can make your life easier. 

 

Some Common Operations for a Queue ADT

 

 

Basically, the implementation of queue is very intuitive and is a slight variation of that of stack. 

 

If we use linked list data type for Queue ADT:

• If the head pointer is null, the queue is empty
• If we Enqueue an item, the tail node's next pointer changes.
• If we Dequeue an item, the head node changes. 

 

Python: Array-Based Queue

 

Array-Based Queue is a queue implemented using an array data type. 

Two variables are required in addition to the array:

1. length: an integer for the queue's length.
2. front_index: an integer for the queue's front item index. 

 

This image will help your understanding on the meaning of front_index variable. 

 

Similar to the Stack, we can either choose the queue to be bounded or unbounded, by introducing an additional object variable max_length. 

A bounded queue (or a bounded stack) with a length equal to the maximum length is said to be full. 

 

Again, similar to Stack we can use a flexible approach by using max_length for both bounded and unbounded queues, but differentiate based on its sign. 

Negative max_length will tell that the queue is unbounded, so we will set the default value as -1 for max_length.

 

 

Next, we will take a look into resize algorithm that's needed when we are tyring to Enqueue when length = max_length. 

def resize(self):
    new_size = len(self.queue_list) * 2
    if self.max_length >= 0 and new_size > self.max_length:
        new_size = max_length
    
    new_list = [0] * new_size
    for i in range(self.length):
        item_index = (self.front_index + i) % len(self.queue_list)
        new_list[i] = self.queue_list[item_index]


    self.queue_list = new_list
    self.front_index = 0

 

enqueue and dequeue methods are as following: 

def enqueue(self, item):
    if self.length == self.max_length:
        return False
  
    if self.length == len(self.queue_list):
        self.resize()
  
    item_index = (self.front_index + self.length) % len(self.queue_list)
    self.queue_list[item_index] = item
    self.length += 1
    return True

def dequeue(self):
    to_return = self.queue_list[self.front_index]
    self.length -= 1
    self.front_index = (self.front_index + 1) % len(self.queue_list)
    return to_return