A queue is a linear data structure that follows the First In, First Out (FIFO) principle, meaning the element inserted first is removed first. It is analogous to a real-world queue, like a line of people waiting at a ticket counter.
Characteristics of a Queue
- FIFO Structure:
- Elements are added at one end (rear) and removed from the other end (front).
- Dynamic Size: The size of a queue can grow or shrink dynamically, depending on the type of implementation.
- Restricted Operations:
- Enqueue: Insert an element at the rear.
- Dequeue: Remove an element from the front.
Queue Representation
A queue can be visualized as:
css
Copy code
Front -> [10, 20, 30, 40] <- Rear
- The element 10 will be the first to leave the queue when dequeued.
- New elements are added at the rear.
Types of Queues
- Simple Queue:
- Standard FIFO behavior.
- Elements are added at the rear and removed from the front.
- Circular Queue:
- The last position is connected back to the first position to make the queue circular.
- Overcomes the limitation of unused spaces in a simple queue.
- Priority Queue:
- Elements are dequeued based on priority rather than their order in the queue.
- Double-Ended Queue (Deque):
- Elements can be added or removed from both ends.
Queue Operations
- Enqueue (Insert): Adds an element at the rear of the queue.
- Dequeue (Delete): Removes the element from the front of the queue.
- Peek/Front: Retrieves the front element without removing it.
- isEmpty: Checks if the queue is empty.
- isFull: Checks if the queue is full (for fixed-size queues).
Queue Implementation
Queues can be implemented in two ways:
- Array-Based Implementation:
- Uses a fixed-size array.
- Simple but limited by the array size.
- Linked List-Based Implementation:
- Dynamically resizable.
- More flexible than arrays.
Applications of Queues
- Task Scheduling:
- Used in operating systems to manage processes and threads.
- Data Transmission:
- Managing packets in network communication.
- Customer Service:
- Handling customer requests in order of arrival.
- Breadth-First Search (BFS):
- Queue is used to traverse graphs or trees in BFS.
- Printer Spooling:
- Queues manage print jobs in order of arrival.
Example Code for Queue Implementation (Array-Based)
C Implementation
c
Copy code
#include <stdio.h>
#define MAX 5
typedef struct {
int arr[MAX];
int front;
int rear;
} Queue;
// Initialize the queue
void initQueue(Queue *q) {
q->front = -1;
q->rear = -1;
}
// Check if the queue is empty
int isEmpty(Queue *q) {
return q->front == -1;
}
// Check if the queue is full
int isFull(Queue *q) {
return q->rear == MAX – 1;
}
// Enqueue operation
void enqueue(Queue *q, int value) {
if (isFull(q)) {
printf(“Queue Overflow\n”);
return;
}
if (isEmpty(q)) {
q->front = 0;
}
q->arr[++(q->rear)] = value;
printf(“Enqueued: %d\n”, value);
}
// Dequeue operation
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf(“Queue Underflow\n”);
return -1;
}
int value = q->arr[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1; // Reset queue after last element is dequeued
} else {
q->front++;
}
return value;
}
// Display the queue
void display(Queue *q) {
if (isEmpty(q)) {
printf(“Queue is empty\n”);
return;
}
printf(“Queue elements: “);
for (int i = q->front; i <= q->rear; i++) {
printf(“%d “, q->arr[i]);
}
printf(“\n”);
}
// Main function to demonstrate queue operations
int main() {
Queue q;
initQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
display(&q);
printf(“Dequeued: %d\n”, dequeue(&q));
display(&q);
return 0;
}
Output Example
plaintext
Copy code
Enqueued: 10
Enqueued: 20
Enqueued: 30
Queue elements: 10 20 30
Dequeued: 10
Queue elements: 20 30
This code showcases the basic operations of a queue using a fixed-size array.
Conclusion
Queues are fundamental data structures used in various applications, from task scheduling to algorithm implementations. They are efficient for situations requiring FIFO behavior and can be implemented flexibly with arrays or linked lists.