Chapter 8: Queues
Welcome to Chapter 8! In this chapter, we’ll explore Queues, another fundamental data structure that follows the First-In-First-Out (FIFO) principle. Queues are widely used in various computing scenarios like task scheduling, resource management, and buffering.
What is a Queue?
A Queue is a linear data structure where elements are inserted at the rear (also called the back) and removed from the front. This follows the First-In-First-Out (FIFO) principle, which means the first element added to the queue will be the first one to be removed, much like a line of people waiting at a ticket counter.
Here’s a basic diagram of a queue:
Front -> [1] -> [2] -> [3] -> [4] <- Rear
In this queue, 1 is the front element and will be removed first, while 4 is at the rear and will be removed last.
Why Use Queues?
Queues are especially useful in situations where you need to manage tasks or resources in the order they arrive. They are widely applied in various domains:
- CPU Scheduling: Operating systems use queues to manage processes waiting for execution.
- Network Traffic Management: Queues are used to buffer incoming network packets before processing.
- Printer Job Management: When multiple print jobs are sent to a printer, they are queued and printed in the order they were received.
At Emancipation Edutech Private Limited, queues may be used to manage student requests or service multiple learning queries simultaneously, ensuring that tasks are handled in the order they arrive.
Basic Operations on Queues
Queues support four essential operations:
- Enqueue: Add an element to the rear of the queue.
- Dequeue: Remove an element from the front of the queue.
- Front: Get the front element of the queue.
- IsEmpty: Check if the queue is empty.
Let’s see how to implement these operations using both array-based and linked-list-based queues.
Queue Implementation Using an Array
An array-based queue is implemented using a fixed-size array to store the elements. However, managing the front and rear pointers becomes essential to keep track of the queue.
Define the Queue Structure
#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // Maximum size of the queue
// Define the queue structure
struct Queue {
int front, rear;
int arr[MAX];
};
front: Index of the front element.rear: Index of the rear element.arr: Array to hold the elements.
Initialize the Queue
void initialize(struct Queue* q) {
q->front = -1;
q->rear = -1; // Queue is empty initially
}
Enqueue Operation
void enqueue(struct Queue* q, int value) {
if (q->rear == MAX - 1) { // Check for overflow
printf("Queue Overflow\n");
return;
}
if (q->front == -1) // If queue is initially empty
q->front = 0;
q->arr[++(q->rear)] = value; // Increment rear and add value
}
Dequeue Operation
int dequeue(struct Queue* q) {
if (q->front == -1 || q->front > q->rear) { // Check for underflow
printf("Queue Underflow\n");
return -1; // Return -1 to indicate an error
}
return q->arr[q->front++]; // Return front value and increment front
}
Front Operation
int front(struct Queue* q) {
if (q->front == -1 || q->front > q->rear) { // Check if queue is empty
printf("Queue is Empty\n");
return -1;
}
return q->arr[q->front]; // Return front value
}
Example Usage
int main() {
struct Queue queue;
initialize(&queue);
// Enqueue elements
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
// Get the front element
printf("Front element is %d\n", front(&queue));
// Dequeue elements
printf("Dequeued element is %d\n", dequeue(&queue));
printf("Dequeued element is %d\n", dequeue(&queue));
return 0;
}
Output:
Front element is 10
Dequeued element is 10
Dequeued element is 20
Queue Implementation Using a Linked List
In a linked-list-based queue, we dynamically allocate memory for each element, allowing the queue to grow as needed without a fixed size limit.
Define the Node Structure
#include <stdio.h>
#include <stdlib.h>
// Define the node structure
struct Node {
int data;
struct Node* next;
};
// Define the queue structure
struct Queue {
struct Node* front;
struct Node* rear;
};
Initialize the Queue
void initialize(struct Queue* q) {
q->front = q->rear = NULL; // Queue is empty initially
}
Enqueue Operation
void enqueue(struct Queue* q, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (q->rear == NULL) { // If queue is empty
q->front = q->rear = newNode;
return;
}
q->rear->next = newNode;
q->rear = newNode;
}
Dequeue Operation
int dequeue(struct Queue* q) {
if (q->front == NULL) { // Check if queue is empty
printf("Queue Underflow\n");
return -1; // Return -1 to indicate an error
}
struct Node* temp = q->front;
int value = temp->data;
q->front = q->front->next;
if (q->front == NULL) { // If queue becomes empty
q->rear = NULL;
}
free(temp);
return value;
}
Front Operation
int front(struct Queue* q) {
if (q->front == NULL) { // Check if queue is empty
printf("Queue is Empty\n");
return -1;
}
return q->front->data; // Return front value
}
Example Usage
int main() {
struct Queue queue;
initialize(&queue);
// Enqueue elements
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
// Get the front element
printf("Front element is %d\n", front(&queue));
// Dequeue elements
printf("Dequeued element is %d\n", dequeue(&queue));
printf("Dequeued element is %d\n", dequeue(&queue));
return 0;
}
Output:
Front element is 10
Dequeued element is 10
Dequeued element is 20
Types of Queues
There are several variations of the basic queue that serve different purposes in computer science:
1. Simple Queue:
- The basic queue structure we have seen so far.
- Elements are inserted at the rear and removed from the front.
2. Circular Queue:
- In a circular queue, the rear of the queue wraps around to the front when the end of the array is reached. This allows for efficient use of space by reusing positions that are freed when elements are dequeued.
if (rear == MAX - 1) {
rear = 0;
}
Circular queues are often used in resource management systems like printer spoolers or traffic management software.
3. Priority Queue:
- In a priority queue, each element is assigned a priority, and the element with the highest priority is dequeued first, regardless of its position in the queue. This type of queue is widely used in algorithms like Dijkstra’s shortest path.
4. Double-Ended Queue (Deque):
- In a deque, elements can be added or removed from both ends, making it more flexible than a simple queue. Deques are useful in scenarios where you need to manage elements from both ends of the queue.
Applications of Queues
Queues are extensively used in real-world applications:
- Operating Systems: Manage tasks waiting for execution (CPU scheduling).
- Networking: Buffer incoming packets before processing them.
- Printing Jobs: Manage multiple print jobs in the order they are submitted.
- Breadth-First Search (BFS): A fundamental graph traversal algorithm that uses a queue to explore nodes level by level.
At Emancipation Edutech Private Limited, a queue might be used to manage learning modules and allocate tasks to students based on their arrival times. For more real-world examples and in-depth explanations, be sure to check out digilearn.cloud, where you can read the book for free.
Advantages and Disadvantages of Queues
Advantages:
- FIFO Ordering: Ensures that
tasks are completed in the order they are received.
- Efficient Memory Usage: Dynamic implementations like linked lists make better use of memory by allocating only the required space.
Disadvantages:
- Fixed Size: Array-based queues have a fixed size, which can limit flexibility unless managed carefully.
- No Random Access: You cannot directly access an element in the middle of the queue without dequeuing all the preceding elements.
Conclusion
Queues are an essential data structure for managing tasks in a sequential order. Whether you’re scheduling processes, managing print jobs, or traversing graphs, queues provide an efficient way to handle sequential data. By mastering queues, you’re well on your way to solving many real-world computing problems.
In the next chapter, we will dive into Circular Queues and explore how they optimize space utilization in various applications.
Stay curious, keep learning, and remember—your queue for knowledge has just begun!
Next Chapter: Circular Queues
