Queues
A Queue is a linear data structure that follows the FIFO (First In, First Out) principle.
In this structure, the element inserted first is the first one to be removed. It is analogous to a real-life queue (such as a line of people at a ticket counter).
Basic Structure:
A queue consists of two primary pointers:
- Front: Indicates the first element of the queue (the next to be removed).
- Rear: Indicates the last element where a new element will be inserted.
- Operations on Queue:
Enqueue (Insertion):
Adds an element at the rear end of the queue.
Dequeue (Deletion):
Removes an element from the front end of the queue.
Peek/Front:
Retrieves the element at the front without removing it.
isEmpty:
Checks if the queue contains any elements.
isFull:
(Applicable in arrays) Checks if the queue is full.
Queue Implementation (Array-Based Example in C):
#define SIZE 5
int queue[SIZE];
int front = -1, rear = -1;
void enqueue(int value) {
if(rear == SIZE – 1)
printf(“Queue Overflow\n”);
else {
if(front == -1) front = 0;
rear++;
queue[rear] = value;
}
}
int dequeue() {
if(front == -1 || front > rear) {
printf(“Queue Underflow\n”);
return -1;
} else {
return queue[front++];
}
}
Types of Queues:
Simple (Linear) Queue:
Insertion at rear, deletion from front.
Drawback: Space wastage when elements are dequeued.
Circular Queue:
The last position is connected to the first position to form a circle.
Overcomes the limitation of the simple queue by reusing freed spaces.
Deque (Double-Ended Queue):
Insertion and deletion can be done from both ends (front and rear).
Priority Queue:
Each element is assigned a priority.
Elements with higher priority are dequeued before lower-priority ones, regardless of their insertion order.
Applications of Queue:
CPU Scheduling (Round Robin, FCFS)
Disk Scheduling
Print Spooling
Handling of Requests in Web Servers
Data Buffers (e.g., IO Buffers, Pipe Buffers)
Breadth-First Search (BFS) in Graphs
Limitations of Simple (Linear) Queue:
Fixed Size: Cannot grow beyond its predefined size (in array implementation).
Space Wastage: After multiple dequeue operations, front moves forward, leaving unused space unless a circular queue is used.
Queue Representation (Diagram):
FRONT → [10] [20] [30] [40] [50] ← REAR
After a dequeue, front moves to the next element.
Array and Linked Representation of Queue
1. Array Representation of Queue
Concept:
In the array representation, a queue is implemented using a fixed-size array along with two variables:
- Front: Points to the element at the front of the queue (for deletion).
- Rear: Points to the last element inserted in the queue.
Operations:
- Enqueue (Insertion): Insert the element at rear + 1 position.
- Dequeue (Deletion): Remove the element from the front position.
Example (Simple Array Implementation in C):
#define SIZE 5
int queue[SIZE];
int front = -1, rear = -1;
void enqueue(int value) {
if(rear == SIZE – 1)
printf(“Queue Overflow\n”);
else {
if(front == -1) front = 0;
rear++;
queue[rear] = value;
}
}
int dequeue() {
if(front == -1 || front > rear) {
printf(“Queue Underflow\n”);
return -1;
} else {
return queue[front++];
}
}
Advantages of Array Representation:
Simple and easy to implement.
Fast access time (O(1)) for front and rear operations.
Limitations of Array Representation:
Fixed Size: Cannot grow dynamically.
Space Wastage: After multiple dequeues, freed spaces are unusable unless a circular array is used.
Overflow occurs even if space is available at the front.
2. Linked List Representation of Queue
Concept:
A linked list-based queue uses nodes to store data dynamically.
Each node contains:
- Data Field: Stores the value.
- Pointer Field: Points to the next node.
The queue maintains two pointers:
- Front: Points to the first node (for deletion).
- Rear: Points to the last node (for insertion).
Node Structure (C Language):
struct Node {
int data;
struct Node* next;
};
Operations:
- Enqueue (Insertion):
- Create a new node and insert it at the rear.
- Update the rear pointer.
- Dequeue (Deletion):
- Remove the node at the front.
- Update the front pointer.
Example (Linked List Queue in C):
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* front = NULL;
struct Node* rear = NULL;
void enqueue(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if(rear == NULL) {
front = rear = newNode;
return;
}
rear->next = newNode;
rear = newNode;
}
int dequeue() {
if(front == NULL) {
printf(“Queue Underflow\n”);
return -1;
}
struct Node* temp = front;
int value = temp->data;
front = front->next;
if(front == NULL) rear = NULL;
free(temp);
return value;
}
Advantages of Linked List Representation:
Dynamic Size: Grows and shrinks as needed (no fixed size).
No Space Wastage: Utilizes memory efficiently.
No Overflow (unless memory is full).
Limitations of Linked List Representation:
Extra Memory Overhead: Each node requires additional space for a pointer.
Slightly More Complex: Requires handling of dynamic memory allocation and pointers.
Comparison Table:
| Feature | Array Representation | Linked List Representation |
| Memory Allocation | Static (fixed size) | Dynamic (can grow/shrink) |
| Space Utilization | Wastage possible | Efficient |
| Overflow | Possible (when full) | No overflow (till memory full) |
| Complexity | Simple to implement | Requires pointer handling |
| Extra Memory | No extra memory for pointers | Requires extra memory per node |
Deque (Double-Ended Queue)
Definition:
A Deque (pronounced as “deck”) stands for Double-Ended Queue.
It is a linear data structure where insertion and deletion can be performed from both the front and rear ends.
Thus, Deque is more versatile than a simple queue, which allows insertion at the rear and deletion from the front only.
Types of Deque:
Input-Restricted Deque:
Insertion is allowed only at one end (usually rear), but deletion can occur from both ends.
Output-Restricted Deque:
Deletion is allowed only at one end (usually front), but insertion can occur from both ends.
Basic Operations in Deque:
- InsertFront(): Inserts an element at the front.
- InsertRear(): Inserts an element at the rear.
- DeleteFront(): Deletes an element from the front.
- DeleteRear(): Deletes an element from the rear.
- getFront(): Returns the front element.
- getRear(): Returns the rear element.
- isFull(): Checks if the deque is full (for array-based implementation).
- isEmpty(): Checks if the deque is empty.
Deque Representations:
1. Array Representation of Deque:
Uses a fixed-size array along with two pointers:
- front: points to the starting index.
- rear: points to the ending index.
Example (conceptual):
[ _ ] [10] [20] [30] [40] [50] [ _ ]
↑ ↑
front rear
Circular arrays are commonly used to handle the wrap-around condition.
2. Linked List Representation of Deque:
A doubly linked list is ideal for implementing a deque as it allows insertion and deletion from both ends efficiently.
Node Structure in C:
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
Insertion/Deletion at both front and rear takes O(1) time complexity.
Advantages of Deque:
Flexibility: Both ends can be used for insertion/deletion.
Useful for Palindrome Checking, Sliding Window Problems, etc.
More versatile than simple queues and stacks.
Limitations of Deque:
Array Implementation: Size must be fixed beforehand.
Slightly More Complex: Requires careful handling of both front and rear pointers.
Applications of Deque:
Palindrome Checking
Sliding Window Algorithms
Job/Task Scheduling Systems
Undo/Redo Operations in Text Editors
Resource Management in Operating Systems
Deque Representation Diagram:
FRONT ↔ [Data] ↔ [Data] ↔ [Data] ↔ REAR
Insert/Delete possible at both ends.
Priority Queues
Definition:
A Priority Queue is a special type of queue in which each element is associated with a priority, and elements are served (dequeued) based on their priority rather than their order of arrival.
Higher-priority elements are dequeued before lower-priority ones, regardless of their position in the queue.
If two elements have the same priority, they are served according to their arrival order (FIFO).
Basic Characteristics:
Each element is stored as a pair of data and priority.
The element with the highest priority is removed first.
Priority queues can be implemented to work in either:
- Ascending Priority (Min-Heap): Lower value indicates higher priority.
- Descending Priority (Max-Heap): Higher value indicates higher priority.
Types of Priority Queues:
Ascending Priority Queue (Min Priority Queue):
The element with the lowest priority number is served first.
Descending Priority Queue (Max Priority Queue):
The element with the highest priority number is served first.
Operations on Priority Queue:
- Insert (Enqueue): Add an element with its associated priority.
- Delete (Dequeue): Remove the element with the highest (or lowest) priority.
- Peek/Get Highest Priority: View the element with the highest priority without removing it.
- isEmpty: Check if the priority queue is empty.
- isFull (for Array Implementation): Check if the queue is full.
Representations of Priority Queues:
1. Array-Based Representation:
Elements are inserted in such a way that they remain sorted based on priority.
Example (Sorted Ascending by Priority):
[ (Data: 30, Priority: 1) ] [ (Data: 50, Priority: 2) ] [ (Data: 10, Priority: 3) ]
Insertion may take O(n) time (to maintain order), but deletion of the highest priority element is O(1).
2. Linked List-Based Representation:
Each node contains data, priority, and a pointer to the next node.
Maintains order while inserting new nodes.
Node Structure in C:
struct Node {
int data;
int priority;
struct Node* next;
};
3. Heap-Based Representation (Efficient Method):
Priority queues are often implemented using binary heaps (Min-Heap Or Max-Heap).Allows O(log n) time complexity for both insertion and deletion.
Advantages of Priority Queue:
Prioritized Processing: Urgent tasks or important data are processed first.
Efficient Resource Allocation: Used in scheduling and real-time Systems.
Flexibility: Can be customized to serve based on varying priority schemes.
Limitations of Priority Queue:
Overhead of Maintaining Order: In array and linked list Implementations, insertion might require shifting or rearrangement.
Complexity Increases with Heap Implementation: Slightly more complex to implement using heaps.
Applications of Priority Queues:
CPU Scheduling (Multilevel Queue Scheduling)
Dijkstra’s Shortest Path Algorithm
Huffman Coding for Data Compression
Operating Systems (Task Scheduling)
Emergency Systems (Hospital or Air Traffic Control)
Diagram Representation of Priority Queue (Linked List Example):
FRONT → [Data: 30, Priority: 1] → [Data: 50, Priority: 2] → [Data: 10, Priority: 3] → NULL
The element with priority 1 will be removed first.