Queue in C
Subject: Data Structures and Algorithms · Language: C · Level: intermediate · 6 min read
Understand FIFO order, front and rear pointers, enqueue, dequeue, circular queue, and real queue uses.
A queue is a linear data structure where insertion and deletion happen from different ends. The element that enters first is removed first. This rule is called FIFO, which means First In, First Out.
Think about a ticket counter. The person who joins the line first gets served first. A queue in programming follows the same idea.
Why Queue Is Needed
A queue is useful when work must be handled in the same order in which it arrives. If many tasks are waiting, the first task should not be ignored while later tasks are processed.
This makes queue one of the most important data structures for scheduling, buffering, graph traversal, and request handling.
Queue Terms
- `front` points to the element that will be removed next
- `rear` points to the place where the next element is inserted
- `enqueue` means insert an element into the queue
- `dequeue` means remove an element from the queue
- `peek` means read the front element without removing it
FIFO Order
If we insert 10, 20, and 30 into a queue, then 10 will be removed first, then 20, then 30.
The queue does not remove the largest or smallest value. It removes according to arrival order.
Queue Representation Using Array
In C, a simple queue can be implemented using an array and two integer variables: `front` and `rear`.
At the beginning, both `front` and `rear` can be set to `-1`, which means the queue is empty.
When the first element is inserted, both `front` and `rear` move to index 0. After that, `rear` moves forward for every new insertion.
Enqueue Operation
Before inserting, we check whether the queue is full. If `rear == MAX - 1`, there is no space left in a simple array queue.
If space is available, increase `rear` and store the new value at that position.
Dequeue Operation
Before removing, we check whether the queue is empty. If the queue is empty, there is nothing to remove.
If the queue has elements, remove the value at `front` and then move `front` forward.
Queue Program
This program inserts three values, prints the queue, reads the front element, removes one value, and prints the queue again.
```c
#include <stdio.h>
#define MAX 5
int queue[MAX];
int front = -1;
int rear = -1;
int isEmpty(void) {
return front == -1 || front > rear;
}
int isFull(void) {
return rear == MAX - 1;
}
void enqueue(int value) {
if (isFull()) {
printf("Queue is full\n");
return;
}
if (front == -1) {
front = 0;
}
rear++;
queue[rear] = value;
}
int dequeue(void) {
if (isEmpty()) {
printf("Queue is empty\n");
return -1;
}
int removed = queue[front];
front++;
return removed;
}
int peek(void) {
if (isEmpty()) {
return -1;
}
return queue[front];
}
void display(void) {
if (isEmpty()) {
printf("Queue is empty\n");
return;
}
for (int i = front; i <= rear; i++) {
printf("%d ", queue[i]);
}
printf("\n");
}
int main(void) {
enqueue(10);
enqueue(20);
enqueue(30);
printf("Queue after enqueue: ");
display();
printf("Front element = %d\n", peek());
printf("Removed = %d\n", dequeue());
printf("Queue after dequeue: ");
display();
return 0;
}
```
How to Read the Program
`enqueue(10)` stores 10 at the rear side. After three insertions, the queue contains 10, 20, and 30.
`peek()` returns the front value, which is 10. `dequeue()` removes the same value because 10 entered first.
After one deletion, the queue starts from 20, so the remaining values are 20 and 30.
Simple Queue Limitation
In a simple array queue, `front` keeps moving forward after deletion. The deleted spaces at the beginning are not reused.
For example, if MAX is 5 and we insert five elements, `rear` reaches the last index. Even if we delete two elements from the front, a simple queue still cannot insert new elements because `rear` is already at the end.
Circular Queue
A circular queue solves this space wastage problem. It treats the array like a circle. When `rear` reaches the last index, it can move back to index 0 if there is free space.
Circular queues are better when the queue size is fixed and insert-delete operations happen again and again.
Queue Using Linked List
A queue can also be implemented using a linked list. In that case, memory can grow as needed, and we do not have the fixed-size problem of arrays.
In linked-list queue, insertion usually happens at the rear node and deletion happens from the front node.
Queue Types
- Simple queue follows normal FIFO order
- Circular queue reuses array space by wrapping indexes
- Priority queue removes elements based on priority
- Deque allows insertion and deletion from both ends
Time Complexity
`enqueue`, `dequeue`, and `peek` take O(1) time when front and rear are maintained correctly.
Displaying all elements takes O(n) time because every current element must be printed.
Where Queues Are Used
Queues are used in CPU scheduling, printer queues, keyboard buffers, network request handling, breadth-first search, customer support systems, and producer-consumer problems.
Practice Question
Write a C program that implements a circular queue and shows insertion, deletion, and display operations.