- A queue is a type of linear data structure that can be constructed with an array or a linked list.
- Elements are relocated to the back of the queue while being removed from the front.
- Enqueue (add an element to the back) and dequeue (remove an element from the front) are two queue operations.
- When elements are added and removed often, a queue might be built as a circular queue to prevent wasting memory.
Using Array:
To create a queue in C using an array, begin by specifying the maximum capacity of the queue and initializing an array with that capacity. The integers front and back are then initialized to 1. The front integer indicates the frontmost element in the queue, while the back integer signifies the rearmost element.
Before adding the latest item to the end of the queue, it is essential to increment the back pointer by 1. Once the back pointer reaches the maximum capacity of the queue, it signifies that the queue is full and cannot accommodate any more elements. To make space for a new element, we insert it at the front of the queue and increment the front pointer by one, ensuring that the oldest element is removed. When the front and back pointers coincide, indicating that no further elements can be removed, the queue is considered empty.
Here is an example of a queue implemented in C using an array:
C Programming Language:
#define MAX_SIZE 100
int queue[MAX_SIZE];
int front = -1;
int rear = -1;
void enqueue(int element) {
if (rear == MAX_SIZE - 1) {
printf("Queue is full");
return;
}
if (front == -1) {
front = 0;
}
rear++;
queue[rear] = element;
}
int dequeue() {
if (front == -1 || front > rear) {
printf("Queue is empty");
return -1;
}
int element = queue[front];
front++;
return element;
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
printf("%d ", dequeue());
printf("%d ", dequeue());
printf("%d ", dequeue());
printf("%d ", dequeue());
return 0;
}
The output of the code will be:
Output:
10 20 30 Queue is empty-1
Explanation:
- First, we enqueue three elements 10, 20 and 30 into the queue.
- Then, we dequeue and print the front element of the queue, which is 10.
- Next, we dequeue and print the front element of the queue again, which is 20.
- Then, we dequeue and print the front element of the queue again, which is 30.
- Finally, we make a dequeue from an empty queue that outputs "Queue is empty" and returns -1.
Using Linked List:
An alternative method for implementing a queue in C programming involves utilizing a linked list. In this approach, each queue node consists of the element's value and a reference to the next node in the queue. Front and rear pointers are employed to manage the first and last nodes in the queue.
We create a fresh node containing the element value and assign its nexLogic Practiceer as NULL to insert a new element into the queue. In case the queue is vacant, we assign the front and rear pointers to the new node. Otherwise, we update the rear pointer and adjust the nexLogic Practiceer of the former rear node to reference the new node.
When removing a node from a queue, the previous node is eliminated initially, followed by updating the front pointer to the next node in the queue. Subsequently, the memory allocated to the deleted node is freed. If the front pointer becomes NULL post-deletion, the queue is considered empty.
Here is a sample of a queue created in C through a linked list:
C Programming Language:
#include<stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* front = NULL;
struct Node* rear = NULL;
void enqueue(int element) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = element;
new_node->next = NULL;
if (front == NULL && rear == NULL) {
front = rear = new_node;
return;
}
rear->next = new_node;
rear = new_node;
}
int dequeue() {
if (front == NULL) {
printf("Queue is empty");
return -1;
}
struct Node* temp = front;
int element = temp->data;
if (front == rear) {
front = rear = NULL;
}
else {
front = front->next;
}
free(temp);
return element;
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
printf("%d ", dequeue());
printf("%d ", dequeue());
printf("%d ", dequeue());
printf("%d ", dequeue());
return 0;
}
The output of the code will be:
Output:
10 20 30 Queue is empty-1
Explanation:
- First, we enqueue three elements 10, 20 and 30 into the queue.
- Then, we dequeue and print the front element of the queue, which is 10.
- Next, we dequeue and print the front element of the queue again, which is 20.
- Then, we dequeue and print the front element of the queue again, which is 30.
- Finally, we try to dequeue from the empty queue, which prints the message "Queue is empty" and returns -1.
- Queues are particularly useful for implementing algorithms that require elements to be processed in a precise sequence, such as breadth-first search and task scheduling.
- Because queue operations have an O(1) time complexity, they can be executed fast even on enormous queues.
- Queues are particularly flexible since they may be simply implemented using an array or a linked list.
- A queue, unlike a stack, cannot be constructed with a single pointer, making queue implementation slightly more involved.
- If the queue is constructed as an array, it might soon fill up if too many elements are added, resulting in performance concerns or possibly a crash.
- When utilising a linked list to implement the queue, the memory overhead of each node can be significant, especially for small elements.
Advantages:
Disadvantages:
Conclusion:
Applications that rely on queues, a fundamental data structure, encompass operating systems, networking, and gaming, among others. Queues prove to be optimal for algorithms requiring strict element processing sequence, as they can be easily implemented using either an array or a linked list. Nonetheless, it is essential to weigh the drawbacks of queues, like memory usage and implementation intricacy, when determining the most suitable data structure for a specific application.