A Queue is a linear data structure that operates on the FIFO (First In, First Out) principle. This means that the element added first is removed first. Queues are widely used in scenarios like scheduling tasks, managing resources, and handling asynchronous data.
Key Concepts of Queue Implementation
- Basic Operations in Queue:
- Enqueue: Adding an element to the rear (end) of the queue.
- Dequeue: Removing an element from the front of the queue.
- Peek/Front: Getting the value of the front element without removing it.
- IsEmpty: Checking if the queue is empty.
- IsFull: Checking if the queue is full (only for arrays).
- Types of Queues:
- Simple Queue: Basic FIFO queue.
- Circular Queue: Improves memory utilization by connecting the rear and front when the queue is full but has vacant spots.
- Priority Queue: Elements are dequeued based on priority, not the order of insertion.
- Deque (Double-Ended Queue): Allows insertion and deletion from both ends.
- Queue Representation:
- Array-Based Implementation: Fixed-size queue using arrays.
- Linked-List Implementation: Dynamically resizable queue using linked nodes.
Programs for Queue in C
1. Simple Queue using Array
#include <stdio.h>
#define SIZE 5
int queue[SIZE], front = -1, rear = -1;
// Function to add an element
void enqueue(int element) {
if (rear == SIZE – 1) {
printf(“Queue is full.\n”);
} else {
if (front == -1) front = 0;
rear++;
queue[rear] = element;
printf(“Enqueued: %d\n”, element);
}
}
// Function to remove an element
void dequeue() {
if (front == -1 || front > rear) {
printf(“Queue is empty.\n”);
} else {
printf(“Dequeued: %d\n”, queue[front]);
front++;
}
}
// Function to display the queue
void display() {
if (front == -1 || front > rear) {
printf(“Queue is empty.\n”);
} else {
printf(“Queue elements: “);
for (int i = front; i <= rear; i++) {
printf(“%d “, queue[i]);
}
printf(“\n”);
}
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
dequeue();
display();
return 0;
}
2. Circular Queue using Array
#include <stdio.h>
#define SIZE 5
int queue[SIZE], front = -1, rear = -1;
void enqueue(int element) {
if ((rear + 1) % SIZE == front) {
printf(“Queue is full.\n”);
} else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
queue[rear] = element;
printf(“Enqueued: %d\n”, element);
}
}
void dequeue() {
if (front == -1) {
printf(“Queue is empty.\n”);
} else {
printf(“Dequeued: %d\n”, queue[front]);
if (front == rear) {
front = -1; // Reset the queue
rear = -1;
} else {
front = (front + 1) % SIZE;
}
}
}
void display() {
if (front == -1) {
printf(“Queue is empty.\n”);
} else {
printf(“Queue elements: “);
int i = front;
while (1) {
printf(“%d “, queue[i]);
if (i == rear) break;
i = (i + 1) % SIZE;
}
printf(“\n”);
}
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50); // Queue full here
display();
dequeue();
enqueue(60); // Reuse the space
display();
return 0;
}
3. Queue Using Linked List
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* front = NULL;
Node* rear = NULL;
void enqueue(int element) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = element;
newNode->next = NULL;
if (rear == NULL) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
printf(“Enqueued: %d\n”, element);
}
void dequeue() {
if (front == NULL) {
printf(“Queue is empty.\n”);
} else {
Node* temp = front;
printf(“Dequeued: %d\n”, front->data);
front = front->next;
free(temp);
if (front == NULL) rear = NULL;
}
}
void display() {
if (front == NULL) {
printf(“Queue is empty.\n”);
} else {
Node* temp = front;
printf(“Queue elements: “);
while (temp != NULL) {
printf(“%d “, temp->data);
temp = temp->next;
}
printf(“\n”);
}
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
dequeue();
display();
return 0;
}
Key Points
- Array-based queues are simple but have a fixed size.
- Circular queues improve memory usage in array-based queues.
- Linked-list queues are dynamic and avoid size limitations.
- Choosing the implementation depends on the use case.