Definition: A queue is an Abstract Data Type (ADT) that follows the FIFO principle (First In, First Out). This means elements are added from one end, called the rear, and removed from the other end, called the front.

Characteristics of a Queue:

1. Linear Data Structure: Arranges elements in a sequential order.

2. FIFO: The first element added is the first to be removed.

3. Two Main Operations:

   • Enqueue: Add an element at the rear.

   • Dequeue: Remove an element from the front.

   • 

4. Fixed or Dynamic Size:

   • Can be implemented with arrays (fixed size).

   • Can use linked lists (dynamic size).

5. Applications:

   • Scheduling tasks (e.g., CPU Scheduling).

   • Managing resources in a printer queue.

   • Breadth-first search (BFS) in graph traversal.

Types of Queues

1. Simple Queue

• Definition: A standard queue that follows the basic FIFO principle.

• Features:

  • Elements are added to the rear and removed from the front.

  • No wrapping around; the queue grows linearly.

• Example Use Case:

  • Managing tasks in a print queue or ticket counter.

Visual Example:
Adding elements 10, 20, and 30 to a simple queue:

Queue Operations:

Eg:2

---

2. Circular Queue

• Definition: A queue where the rear wraps around to the front when the end of the queue is reached, forming a circular structure.

• Features:

  • Efficient memory utilization.

  • Uses modulo arithmetic to manage indices.

  • Prevents overflow until all positions are filled.

• Example Use Case:

  • Buffer management in streaming services.

Visual Example:
A circular queue of size 5..

Circular Queue Operations:

---

Eg2:

3. Priority Queue

• Definition: A queue where each element has a priority, and elements with the highest priority are dequeued first, regardless of the insertion order.

• Features:

  • Can be implemented using arrays, heaps, or linked lists.

  • May be max-priority (higher values dequeued first) or min-priority (lower values dequeued first).

  • Every item has a priority associated with it.

  • An element with high priority is dequeued before an element with low priority.

  • If two elements have the same priority, they are served according to their order in the queue.

• Example Use Case:

  • Task scheduling in an operating system, where high-priority tasks execute before low-priority tasks.

• How Priority is assigned

  • Priority Assignment Based on Value:

    • The value of an element is typically used to assign its priority in the queue.

  • High Value = High Priority (Common Case):

    • By default, the element with the highest value is assigned the highest priority.

    • Example: The element with the value 100 is dequeued before the one with the value 50.

  • Low Value = High Priority (Reverse Case):

    • Alternatively, the element with the lowest value can be assigned the highest priority.

    • Example: The element with the value 10 is dequeued before the one with the value 50.

  • Custom Priority Assignment:

    • Priority can also be assigned based on custom criteria such as importance, urgency, or any other factor.

    • Example: Tasks that are more urgent could be assigned a higher priority regardless of their numerical value.

  • Internal Structure:

    • The priority assignment is often managed using heaps (binary heaps, Fibonacci heaps, etc.), which help maintain the correct order efficiently.

Visual Example:

---

Types of Priority Queues

1. Ascending Priority Queue

• Description:

  • Elements are dequeued in ascending order of priority (i.e., the smallest priority value is dequeued first).

  • The element with the lowest value or least importance is removed first.

• Examples:

  • Task Scheduling: Tasks with the smallest execution time or cost are processed first.

  • Customer Support: Tickets with the oldest timestamps (lowest priority value) are handled before newer ones.

• Example Walkthrough:
  Given a priority queue: [40, 20, 10, 50]

  • After sorting by ascending priority: [10, 20, 40, 50]

  • Dequeue operations: 10 -> 20 -> 40 -> 50

---

2. Descending Priority Queue

• Description:

  • Elements are dequeued in descending order of priority (i.e., the highest priority value is dequeued first).

  • The element with the highest value or most importance is removed first.

• Examples:

  • Emergency Room: Patients with the most critical conditions are attended to first (highest priority).

  • Military Operations: Targets with the highest threat level are addressed before others.

• Example Walkthrough:
  Given a priority queue: [40, 20, 10, 50]

  • After sorting by descending priority: [50, 40, 20, 10]

  • Dequeue operations: 50 -> 40 -> 20 -> 10

---

Key Differences

^✨The Min-Priority Queue and Max-Priority Queue are variations of the two main types of priority queues: Ascending Priority Queue and Descending Priority Queue.

Min-Priority Queue

• Dequeues: Smallest value first.

• Structure: Min-Heap (smallest value at root).

• Applications: Shortest path (Dijkstra's Algorithm), minimum cost tasks.

• Example: [10, 20, 30, 40, 50] → Dequeue order: 10 → 20 → 30 → 40 → 50.

---

Max-Priority Queue

• Dequeues: Largest value first.

• Structure: Max-Heap (largest value at root).

• Applications: Job scheduling, urgency-based systems.

• Example: [50, 40, 30, 20, 10] → Dequeue order: 50 → 40 → 30 → 20 → 10.

Design Options for Priority Queue

In a Priority Queue, elements are processed based on priority, where each element has an associated priority. Priority queues can be designed using different data structures, and each has its own advantages and trade-offs. Here are the common design options for a priority queue:

1. Binary Heap (Min-Heap or Max-Heap)

2. Binary Search Tree (BST)

3. Unsorted List

4. Sorted List

5. Fibonacci Heap

6. Pairing Heap

7. Treap

1.Unsorted List

• Description: A simple approach where elements are inserted into an unsorted list, and the priority is determined during extraction.

• How it works: Insertion is done at the end of the list. To remove the highest-priority element, the list is scanned to find the element with the highest priority.

• Operations:

  • Insertion: O(1)

  • Extraction: O(n)

  • Peek: O(n)

Visual Representation:

[3, 10, 5, 7]

Advantages:

• Insertion is very fast, O(1).

• Simple to implement.

Disadvantages:

• Extraction (finding the highest priority) is slow, O(n).

• Inefficient for large data sets.

---

2.Sorted List

• Description: In this approach, the elements are stored in a sorted list based on priority. The highest-priority element is always at the front (or back) of the list.

• How it works: When a new element is inserted, the list is traversed to place the element in the correct position based on its priority.

• Operations:

  • Insertion: O(n) (due to traversal to insert in the correct position).

  • Extraction: O(1) (removal from the front/back).

  • Peek: O(1) (since the highest or lowest priority is always at the front).

Visual Representation:

[1, 3, 5, 7, 10]

Advantages:

• Quick extraction (O(1)).

• The elements are always in sorted order.

Disadvantages:

• Insertion is slow (O(n)).

• Not efficient for large data sets when insertion operations are frequent.

3. Binary Search Tree (BST)

• Description: A binary search tree can be used to implement a priority queue. The priority of each element corresponds to the element's value, and the tree maintains the sorted order of elements.

• How it works: Insertion and deletion are based on binary search, with the priority determining where to insert or remove elements.

• Operations:

  • Insertion: O(log n)

  • Extraction: O(log n)

  • Peek (get maximum or minimum): O(log n)

Visual Representation of a BST:

        10
      /    \
     5     15
    / \   /   \
   2   7 12    18

Advantages:

• Supports priority updates more efficiently.

• Can store more complex data structures beyond just integers.

• Sorted order allows fast searching and traversal.

• Easier to implement dynamic priority updates.

Disadvantages:

• The tree may become unbalanced, leading to O(n) operations in the worst case.

4. Binary Heap (Min-Heap or Max-Heap)

• Description: A binary heap is a complete binary tree where each node is smaller (Min-Heap) or larger (Max-Heap) than its children.

• How it works: Elements are inserted and removed according to the heap property. The root always contains the highest or lowest priority element.

• Operations:

  • Insertion: O(log n)

  • Extraction: O(log n)

  • Peek (get maximum or minimum): O(1)

• Example:

  • Min-Heap: The smallest element has the highest priority.

  • Max-Heap: The largest element has the highest priority.

Visual Representation of a Min-Heap:

        1
      /   \
     3     5
    / \   / \
   8  10 7   6

Advantages:

• Simple and efficient.

• Insertion and extraction are logarithmic in time complexity.

• Widely used in algorithms like Dijkstra's shortest path.

Disadvantages:

• Not efficient for priority updates.

• Deleting or changing priority requires re-heapifying.

---

Comparison of Queue Types

---

PYQ ( MAKAUT University )