Queues

Overview

A queue is a dynamic data structure that follows the First In, First Out (FIFO) principle. This means the first item added to the queue is the first one to be removed. Queues are widely used in various real-world and computational scenarios, such as managing tasks in printers, handling customer service requests, and simulating real-world queues.

Characteristics of a Queue

• Dynamic Data Structure: The size of a queue can grow or shrink dynamically as items are added or removed.
• FIFO Principle: The first item added is the first item to be removed.

Key Operations

• Enqueue: Adds an item to the rear of the queue.
• Dequeue: Removes an item from the front of the queue.
• Peek/Front: Returns the item at the front without removing it.
• IsEmpty: Checks if the queue is empty.
• IsFull (optional in static implementations): Checks if the queue has reached its maximum capacity.

Use Cases for Queues

• Print Queue: Manages print jobs in the order they are received.
• Task Scheduling: Processes tasks in a first-come, first-served manner.
• Breadth-First Search (BFS): Explores nodes level by level in graph or tree traversal.
• Real-Time Systems: Handles incoming requests or events in the order they occur.

Implementation of Queues

Dynamic Implementation Using a Linked List

A queue can be implemented using a linked list, where each node contains the data and a reference to the next node.

CLASS Node
    DATA value
    POINTER next

CLASS Queue
    POINTER front
    POINTER rear

    METHOD Enqueue(value)
        NEW_NODE ← Node(value)
        IF front IS NULL
            front ← NEW_NODE
            rear ← NEW_NODE
        ELSE
            rear.next ← NEW_NODE
            rear ← NEW_NODE

    METHOD Dequeue()
        IF front IS NULL
            RETURN "Queue Underflow"
        ELSE
            value ← front.value
            front ← front.next
            IF front IS NULL
                rear ← NULL
            RETURN value

    METHOD Peek()
        IF front IS NULL
            RETURN "Queue is Empty"
        ELSE
            RETURN front.value

    METHOD IsEmpty()
        RETURN front IS NULL

Static Implementation Using an Array

A queue can also be implemented using a static array with a fixed size.

CLASS Queue
    ARRAY data[size]
    INTEGER front ← 0
    INTEGER rear ← -1
    INTEGER count ← 0

    METHOD Enqueue(value)
        IF count = size
            RETURN "Queue Overflow"
        ELSE
            rear ← (rear + 1) MOD size
            data[rear] ← value
            count ← count + 1

    METHOD Dequeue()
        IF count = 0
            RETURN "Queue Underflow"
        ELSE
            value ← data[front]
            front ← (front + 1) MOD size
            count ← count - 1
            RETURN value

    METHOD Peek()
        IF count = 0
            RETURN "Queue is Empty"
        ELSE
            RETURN data[front]

    METHOD IsEmpty()
        RETURN count = 0

    METHOD IsFull()
        RETURN count = size

Types of Queues

1. Simple Queue: Operates strictly in FIFO order.
2. Circular Queue: The rear wraps around to the front when the end of the array is reached.
3. Priority Queue: Elements are dequeued based on their priority rather than their arrival time.

Note Summary