Queue

Definition

Stores a collection of elements that can only be modified by adding elements at one end of the sequence and removing at the other end - FIFO

Main operations

• enqueue and dequeue
• front, isFull, isEmpty

Implementation

Singly vs. doubly linked lists for queues

Since nodes in a normal singly linked list don’t have a previous reference, when enqueuing, it takes $O(n)$ time to traverse to and update the the second-last node’s next reference to the added node (Presuming the head points to the front of the queue)

Doubly-linked list

Python doubly-linked list implementation

class Node:
    def __init__(self, value=None):
        self.value = value
        self.prev = None
        self.next = None
 
class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
 
    def enqueue(self, value):
        new_node = Node(value)
        if self.size == 0:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1
 
    def dequeue(self):
        if self.size == 0:
            return None
        elif self.size == 1:
            value = self.head.value
            self.head = None
            self.tail = None
        else:
            value = self.head.value
            self.head = self.head.next
            self.head.prev = None
        self.size -= 1
        return value
 
    def __len__(self):
        return self.size
 
    def is_empty(self):
        return self.size == 0
 

Modified singly-linked list

Python modified singly-linked list implementation

class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None
 
class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
 
    def enqueue(self, value):
        new_node = Node(value)
        if self.size == 0:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1
 
    def dequeue(self):
        if self.size == 0:
            return None
        value = self.head.value
        self.head = self.head.next
        self.size -= 1
        if self.size == 0:
            self.tail = None
        return value
 
    def __len__(self):
        return self.size
 
    def is_empty(self):
        return self.size == 0
 

This implementation is efficient because adding elements to the tail of the list and removing elements from the head of the list can be done in constant time.

Circular array

Use a dynamically resizing array with front/back pointers and modulo operations for when the queue wraps around

Python resizable array implementation

class Queue:
    def __init__(self, capacity=10):
        self.front = 0 # Initialize front pointer to 0
        self.rear = 0 # Initialize rear pointer to 0
        self.capacity = capacity # Set maximum capacity of the queue
        self.queue = [None] * capacity # Create an array of None values with length capacity
    
    def is_empty(self):
        return self.front == self.rear
    
    def is_full(self):
        return (self.rear + 1) % len(self.queue) == self.front
    
    def enqueue(self, item):
        if self.is_full():
            self._resize()
        self.queue[self.rear] = item # Add item to the rear of the queue
        self.rear = (self.rear + 1) % len(self.queue) # Increment rear pointer
    
    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        item = self.queue[self.front] # Get the item at the front of the queue
        self.queue[self.front] = None # Remove the item from the queue by setting it to None
        self.front = (self.front + 1) % len(self.queue) # Increment front pointer
        if len(self.queue) > self.capacity and len(self.queue) // 4 == self.capacity:
            self._resize()
        return item
    
    def _resize(self):
        old_queue = self.queue
        self.capacity = len(old_queue) * 2
        self.queue = [None] * self.capacity
        i = 0
        while not self.is_empty():
            self.queue[i] = self.dequeue()
            i += 1
        self.front = 0
        self.rear = i

Circular queue

a data structure that uses a fixed-size array to implement a queue where the front and rear of the queue are connected.

start with a fixed-size array to store the elements of the queue.

We’ll need to keep track of the front and rear of the queue, which will initially both be set to zero.

Restricted deque

Use a deque but impose the restriction that elements can only be inserted at the back of the deque and removed from the front of the deque.

Algorithms using queues

• Breadth first search

---

• task Add implementation time complexity details