Queues:
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. In a queue, elements are inserted at the rear (enqueue) and removed from the front (dequeue). This ensures that the first element added to the queue is the first one to be removed.
Array Representation and Implementation of Queues:
In the array representation of a queue, a fixed-size array is used to implement the queue. Similar to stacks, the front and rear pointers are used to keep track of the elements in the queue.
Here’s how a queue can be represented using an array in C:
 #define MAX_SIZE 10
// Structure to represent a queue
typedef struct {
int arr[MAX_SIZE];
int front;
int rear;
} Queue;
// Function to initialize the queue
void initQueue(Queue *q) {
q->front = -1;
q->rear = -1;
}
// Function to check if the queue is empty
int isEmpty(Queue *q) {
return (q->front == -1 && q->rear == -1);
}
// Function to check if the queue is full
int isFull(Queue *q) {
return ((q->rear + 1) % MAX_SIZE == q->front);
}
// Function to enqueue an element into the queue
void enqueue(Queue *q, int item) {
if (isFull(q)) {
printf(“Queue Overflow\n”);
return;
}
if (isEmpty(q))
q->front = q->rear = 0;
else
q->rear = (q->rear + 1) % MAX_SIZE;
q->arr[q->rear] = item;
}
// Function to dequeue an element from the queue
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf(“Queue Underflow\n”);
return -1;
}
int item = q->arr[q->front];
if (q->front == q->rear)
q->front = q->rear = -1;
else
q->front = (q->front + 1) % MAX_SIZE;
return item;
}
int main() {
Queue q;
initQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
printf(“Dequeued item: %d\n”, dequeue(&q)); // Output: 10
printf(“Dequeued item: %d\n”, dequeue(&q)); // Output: 20
enqueue(&q, 40);
return 0;
}
In this implementation:
- The
frontandrearpointers are initialized to-1to indicate an empty queue. - The
enqueueoperation inserts an element at the rear of the queue, and thedequeueoperation removes an element from the front of the queue. - Circular indexing is used to handle the case where the rear pointer reaches the end of the array.
Linked Representation and Implementation of Queues:
In the linked representation of a queue, each element of the queue is represented by a node of a linked list. The front pointer points to the first node of the queue, and the rear pointer points to the last node of the queue.
Here’s how a queue can be represented using a linked list in C:
// Structure to represent a node
typedef struct Node {
int data;
struct Node *next;
} Node;
// Structure to represent a queue
typedef struct {
Node *front;
Node *rear;
} Queue;
// Function to initialize the queue
void initQueue(Queue *q) {
q->front = q->rear = NULL;
}
// Function to check if the queue is empty
int isEmpty(Queue *q) {
return (q->front == NULL && q->rear == NULL);
}
// Function to enqueue an element into the queue
void enqueue(Queue *q, int item) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
printf(“Memory allocation failed\n”);
return;
}
newNode->data = item;
newNode->next = NULL;
if (isEmpty(q))
q->front = q->rear = newNode;
else {
q->rear->next = newNode;
q->rear = newNode;
}
}
// Function to dequeue an element from the queue
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf(“Queue Underflow\n”);
return -1;
}
int item = q->front->data;
Node *temp = q->front;
if (q->front == q->rear)
q->front = q->rear = NULL;
else
q->front = q->front->next;
free(temp);
return item;
}
int main() {
Queue q;
initQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
printf(“Dequeued item: %d\n”, dequeue(&q)); // Output: 10
printf(“Dequeued item: %d\n”, dequeue(&q)); // Output: 20
enqueue(&q, 40);
return 0;
}
In this implementation:
- Each node of the linked list contains the data and a pointer to the next node.
- The
enqueueoperation inserts a new node at the rear of the queue, and thedequeueoperation removes the first node from the front of the queue. - The
frontpointer points to the first node of the queue, and therearpointer points to the last node of the queue.
Both array-based and linked list-based implementations of queues have their advantages and disadvantages. Array-based implementations have fixed capacity and may lead to wasted memory if the capacity is not utilized fully, while linked list-based implementations dynamically allocate memory for each element, allowing for flexible memory usage. However, linked list-based implementations require more memory overhead due to the additional pointers.