Queues

Queue Overview

• Queue: A linear data structure that operates in a FIFO (First In, First Out) manner. Items are added at the rear (tail) and removed from the front (head).

Objectives

• Understand the Queue data structure.

• Learn to implement Queues in Python including bounded and circular Queues.

Key Operations in Queue

• Enqueue: Add an item to the rear of the queue.

• Dequeue: Remove an item from the front of the queue.

• isEmpty: Check if the queue is empty.

• size: Get the current number of items in the queue.

• Example Visualization:

  • Front and Rear representation with data elements.

Use Cases for Queues

• Printing Queue: Manage jobs waiting to be printed.

• Process Scheduling: Manage tasks for CPU processing.

• Keyboard Buffering: Handle keystroke inputs.

• Maze Traversal: Store paths while seeking a solution.

Queue Implementations

Basic Queue Implementation

• Implemented using lists in Python:

  • Queue Class:

    • Initializes empty list to hold items.

    • Methods: enqueue, dequeue, isEmpty, size, clear.

Example Code for a Basic Queue

class Queue:
    def __init__(self):
        self._items = []

    def enqueue(self, item):
        self._items.insert(0,item)

    def dequeue(self):
        return self._items.pop()

    def isEmpty(self):
        return self._items == []

    def size(self):
        return len(self._items)

    def clear(self):
        self._items = []

Performance Characteristics

1. List Implementation:

   • Rear at position 0:

     • Enqueue O(n), Dequeue O(1)

   • Rear at the end:

     • Enqueue O(1), Dequeue O(n)

2. Doubly Linked List offers O(1) for both enqueue and dequeue operations.

Bounded Queue

• Bounded Queue: A queue with a fixed capacity. You know the maximum number of items it can hold.

• Bounded Queue ADT:

  • Constructor: Creates an empty bounded queue.

  • enqueue(item): Adds an item at the rear if there is room.

  • dequeue(): Removes and returns the front item.

  • isFull(): Checks if the queue has reached its capacity.

  • size(): Returns the current number of items in the queue.

Example Code for a Bounded Queue

class BoundedQueue:
    def __init__(self, capacity):
        assert capacity > 0
        self._items = []
        self._capacity = capacity

    def enqueue(self, item):
        if len(self._items) >= self._capacity:
            raise Exception('Error: Queue is full')
        self._items.append(item)

Circular Queue

• Circular Queue: A bounded queue where the rear and front indices move through the list, making it circular.

• Key Feature: Both indices wrap around when the end of the array is reached.

Use of Modulus

• Modulus Operation: Used to handle wrapping around the array for enqueueing and dequeueing operations.

  • index = (index + 1) % capacity

Example Code for Circular Queue

class CircularQueue:
    def __init__(self, capacity):
        if type(capacity) != int or capacity <= 0:
            raise Exception('Capacity Error')
        self._items = [None] * capacity
        self._capacity = capacity
        self._count = 0
        self._head = 0
        self._tail = 0

    def enqueue(self, item):
        if self._count == self._capacity:
            raise Exception('Error: Queue is full')
        self._items[self._tail] = item
        self._tail = (self._tail + 1) % self._capacity
        self._count += 1

Comparison of Queue Types

• Regular Queue: Simple direct line addition/removal.

• Bounded Queue: Fixed size; raises exceptions at capacity limits.

• Circular Queue: Efficient space utilization; no need for resizing.