What is a Queue?
A Queue is a linear data structure that stores and manages elements in a specific order. Unlike a stack, which operates from one end, a queue works from both ends — elements are added at one end (called the rear) and removed from the other end (called the front).
This structure ensures that the element that has been waiting the longest is always served first — just like standing in a line at a ticket counter or a bank.
💡 Key Point: A Queue follows the FIFO (First In, First Out) principle — the first element inserted is the first one to be removed.
📊 Queue Diagram
Elements enter from the REAR and leave from the FRONT.
Real-World Analogies
- 🎟️ Ticket counter queue: The first person to arrive is the first person served. No jumping ahead.
- 🖨️ Printer job queue: Print jobs are processed in the order they are received.
- 🚗 Traffic lane: Cars enter from the back of the lane and exit from the front.
- 📞 Call center: Customer calls are handled in the order they arrive — first caller, first served.
- ⬇️ Download queue: Files are downloaded one by one in the order they were added.
The FIFO Principle
FIFO stands for First In, First Out. This is the fundamental rule of a queue. The first element that enters the queue will be the first element to leave it. Study the step-by-step trace below:
| Step | Operation | Queue State (front → rear) | Front | Rear |
|---|---|---|---|---|
| 1 | Enqueue(10) | [10] | 10 | 10 |
| 2 | Enqueue(20) | [10, 20] | 10 | 20 |
| 3 | Enqueue(30) | [10, 20, 30] | 10 | 30 |
| 4 | Dequeue() | [20, 30] | 20 | 30 |
| 5 | Enqueue(40) | [20, 30, 40] | 20 | 40 |
| 6 | Dequeue() | [30, 40] | 30 | 40 |
Queue Operations
A queue supports the following fundamental operations:
🔹 Enqueue (Insert)
Adds a new element to the rear of the queue. If the queue is already full (in a fixed-size array), this causes a Queue Overflow error.
🔹 Dequeue (Delete)
Removes and returns the element from the front of the queue. If the queue is empty, this causes a Queue Underflow error.
🔹 Peek / Front
Returns the front element without removing it. Useful for checking what's next without actually dequeuing it.
🔹 isEmpty
Returns true if the queue contains no elements, otherwise false.
🔹 isFull
Returns true if the queue has reached its maximum capacity (applicable for array-based queues).
| Operation | Description | Time Complexity |
|---|---|---|
| Enqueue(x) | Insert element x at rear | O(1) |
| Dequeue() | Remove and return front element | O(1) |
| Peek() | View front element | O(1) |
| isEmpty() | Check if queue is empty | O(1) |
| isFull() | Check if queue is full | O(1) |
Queue Implementation Using Array in C
The simplest way to implement a queue in C is by using an array with two integer pointers — front and rear. Initially, both are set to -1 to indicate an empty queue. Each enqueue increments rear; each dequeue increments front.
Advantage: Simple and fast. Disadvantage: Fixed size, and wasted memory positions after dequeuing (solved by Circular Queue).
#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // Maximum queue size
// Queue structure
struct Queue {
int arr[MAX];
int front;
int rear;
int size;
};
// Initialize the queue
void initQueue(struct Queue* q) {
q->front = -1;
q->rear = -1;
q->size = 0;
}
// Check if the queue is empty
int isEmpty(struct Queue* q) {
return q->front == -1;
}
// Check if the queue is full
int isFull(struct Queue* q) {
return q->rear == MAX - 1;
}
// Enqueue — add element to rear
void enqueue(struct Queue* q, int value) {
if (isFull(q)) {
printf("Queue Overflow! Cannot enqueue %d\n", value);
return;
}
if (isEmpty(q)) q->front = 0; // first element sets front
q->arr[++q->rear] = value;
q->size++;
printf("Enqueued: %d\n", value);
}
// Dequeue — remove element from front
int dequeue(struct Queue* q) {
if (isEmpty(q)) {
printf("Queue Underflow! Queue is empty.\n");
return -1;
}
int val = q->arr[q->front];
if (q->front == q->rear) {
// Queue becomes empty after this dequeue
q->front = -1;
q->rear = -1;
} else {
q->front++;
}
q->size--;
return val;
}
// Peek — view front element without removing
int peek(struct Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
return -1;
}
return q->arr[q->front];
}
// Display all queue elements
void display(struct Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
return;
}
printf("Queue (front to rear): ");
for (int i = q->front; i <= q->rear; i++) {
printf("%d ", q->arr[i]);
}
printf("\n");
}
int main() {
struct Queue q;
initQueue(&q);
printf("=== Queue Using Array in C ===\n\n");
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
enqueue(&q, 40);
printf("\n");
display(&q);
printf("Front element (peek): %d\n", peek(&q));
printf("\nDequeuing elements:\n");
printf("Dequeued: %d\n", dequeue(&q));
printf("Dequeued: %d\n", dequeue(&q));
printf("\nAfter dequeuing:\n");
display(&q);
return 0;
}📤 Output
=== Queue Using Array in C ===
Enqueued: 10
Enqueued: 20
Enqueued: 30
Enqueued: 40
Queue (front to rear): 10 20 30 40
Front element (peek): 10
Dequeuing elements:
Dequeued: 10
Dequeued: 20
After dequeuing:
Queue (front to rear): 30 40🔍 How it works: front and rear both start at -1. When the first element is enqueued, front is set to 0. Every enqueue increments rear; every dequeue increments front. When front == rear after a dequeue, both are reset to -1.
Circular Queue Implementation in C
A major problem with the simple array queue is memory wastage. After several enqueue and dequeue operations, the front pointer keeps moving right, leaving unused slots at the beginning of the array that can never be reused — even when there is space.
A Circular Queue solves this by treating the array as a circle. When rear reaches the end of the array, it wraps around to index 0 if space is available at the front. This makes full use of every slot in the array.
#include <stdio.h>
#define MAX 5 // Maximum circular queue size
struct CircularQueue {
int arr[MAX];
int front;
int rear;
int count; // tracks number of elements
};
void initCQ(struct CircularQueue* cq) {
cq->front = 0;
cq->rear = -1;
cq->count = 0;
}
int isEmpty(struct CircularQueue* cq) {
return cq->count == 0;
}
int isFull(struct CircularQueue* cq) {
return cq->count == MAX;
}
void enqueue(struct CircularQueue* cq, int value) {
if (isFull(cq)) {
printf("Circular Queue is full! Cannot enqueue %d\n", value);
return;
}
// Wrap rear around using modulo
cq->rear = (cq->rear + 1) % MAX;
cq->arr[cq->rear] = value;
cq->count++;
printf("Enqueued: %d\n", value);
}
int dequeue(struct CircularQueue* cq) {
if (isEmpty(cq)) {
printf("Circular Queue is empty!\n");
return -1;
}
int val = cq->arr[cq->front];
// Wrap front around using modulo
cq->front = (cq->front + 1) % MAX;
cq->count--;
return val;
}
void display(struct CircularQueue* cq) {
if (isEmpty(cq)) { printf("Queue is empty.\n"); return; }
printf("Circular Queue: ");
for (int i = 0; i < cq->count; i++) {
printf("%d ", cq->arr[(cq->front + i) % MAX]);
}
printf("\n");
}
int main() {
struct CircularQueue cq;
initCQ(&cq);
printf("=== Circular Queue in C ===\n\n");
enqueue(&cq, 10); enqueue(&cq, 20);
enqueue(&cq, 30); enqueue(&cq, 40);
enqueue(&cq, 50);
printf("\n"); display(&cq);
printf("\nDequeuing: %d\n", dequeue(&cq));
printf("Dequeuing: %d\n\n", dequeue(&cq));
// Now reuse the freed slots at front
enqueue(&cq, 60);
enqueue(&cq, 70);
printf("\n"); display(&cq);
return 0;
}🔍 Key Trick: The modulo operator % is used to wrap rear and front around the array: rear = (rear + 1) % MAX. This makes the array behave like a circle, reusing freed positions from dequeue operations.
Queue Implementation Using Linked List in C
The array-based queue has a fixed size. A Linked List-based queue solves this by growing dynamically. We maintain two pointers — front and rear — pointing to the first and last nodes respectively. Enqueue adds a node at rear; dequeue removes from front.
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
};
// Queue structure
struct Queue {
struct Node* front;
struct Node* rear;
int size;
};
// Initialize the queue
void initQueue(struct Queue* q) {
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
// Check if queue is empty
int isEmpty(struct Queue* q) {
return q->front == NULL;
}
// Enqueue — add element at rear
void enqueue(struct Queue* q, int value) {
struct Node* newNode =
(struct Node*) malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = value;
newNode->next = NULL;
if (isEmpty(q)) {
q->front = newNode; // first node: both front & rear
} else {
q->rear->next = newNode; // link to old rear
}
q->rear = newNode;
q->size++;
printf("Enqueued: %d (Queue size: %d)\n", value, q->size);
}
// Dequeue — remove element from front
int dequeue(struct Queue* q) {
if (isEmpty(q)) {
printf("Queue Underflow! Queue is empty.\n");
return -1;
}
struct Node* temp = q->front;
int val = temp->data;
q->front = temp->next;
if (q->front == NULL) q->rear = NULL; // queue now empty
free(temp);
q->size--;
return val;
}
// Peek — view front element
int peek(struct Queue* q) {
if (isEmpty(q)) { printf("Queue is empty.\n"); return -1; }
return q->front->data;
}
// Display all elements
void display(struct Queue* q) {
if (isEmpty(q)) { printf("Queue is empty.\n"); return; }
struct Node* curr = q->front;
printf("Queue (front to rear): ");
while (curr != NULL) {
printf("%d ", curr->data);
curr = curr->next;
}
printf("\n");
}
// Free all memory
void freeQueue(struct Queue* q) {
while (!isEmpty(q)) dequeue(q);
}
int main() {
struct Queue q;
initQueue(&q);
printf("=== Queue Using Linked List in C ===\n\n");
enqueue(&q, 100);
enqueue(&q, 200);
enqueue(&q, 300);
printf("\n");
display(&q);
printf("Front element (peek): %d\n", peek(&q));
printf("\nDequeuing elements:\n");
printf("Dequeued: %d\n", dequeue(&q));
printf("Dequeued: %d\n", dequeue(&q));
printf("\n");
display(&q);
freeQueue(&q);
printf("All memory freed.\n");
return 0;
}Queue Overflow and Queue Underflow
🔴 Queue Overflow
Queue overflow occurs when you try to enqueue an element into an already full queue. In array-based queues, this happens when rear == MAX - 1 (simple queue) or count == MAX (circular queue).
⚠️ Warning: In fixed-size array queues, always check isFull() before calling enqueue() to prevent overwriting valid data silently!
🔵 Queue Underflow
Queue underflow occurs when you try to dequeue from an empty queue. We guard against this by checking isEmpty() before every dequeue operation.
#include <stdio.h>
#define MAX 3 // Tiny size to trigger overflow easily
int queue[MAX];
int front = -1;
int rear = -1;
void enqueue(int val) {
if (rear == MAX - 1) {
printf("[OVERFLOW] Cannot enqueue %d — Queue is full!\n", val);
return;
}
if (front == -1) front = 0;
queue[++rear] = val;
printf("Enqueued: %d\n", val);
}
int dequeue() {
if (front == -1 || front > rear) {
printf("[UNDERFLOW] Cannot dequeue — Queue is empty!\n");
return -1;
}
return queue[front++];
}
int main() {
printf("-- Testing Queue Overflow --\n");
enqueue(1); enqueue(2); enqueue(3);
enqueue(4); // triggers overflow
printf("\n-- Testing Queue Underflow --\n");
printf("Dequeued: %d\n", dequeue());
printf("Dequeued: %d\n", dequeue());
printf("Dequeued: %d\n", dequeue());
dequeue(); // triggers underflow
return 0;
}Real-World Applications of Queue
Queues are used extensively across operating systems, networking, and real-world software. Here are the key application areas:
Print jobs are queued and processed in the exact order they are submitted to the printer.
Operating systems use queues (like Round Robin) to schedule processes and share CPU time fairly.
Data packets in routers and switches are buffered in queues before being forwarded to the destination.
Input events (keyboard, mouse) are stored in a queue and processed frame by frame in game loops.
Breadth-First Search uses a queue to visit all neighboring nodes level by level before going deeper.
Incoming calls are placed in a queue and routed to the next available agent in order.
📌 Bonus Program: BFS Using Queue in C
Breadth-First Search (BFS) is one of the most important graph algorithms, and it depends entirely on a queue to work correctly. Here is a complete BFS implementation using an adjacency matrix and a queue:
#include <stdio.h>
#define MAX 10
int adj[MAX][MAX]; // Adjacency matrix
int visited[MAX]; // Visited array
int queue[MAX];
int front = -1, rear = -1;
void enqueue(int v) {
if (rear == MAX - 1) return;
if (front == -1) front = 0;
queue[++rear] = v;
}
int dequeue() {
if (front == -1 || front > rear) return -1;
return queue[front++];
}
int isEmpty() {
return front == -1 || front > rear;
}
void bfs(int start, int n) {
visited[start] = 1;
enqueue(start);
printf("BFS Traversal: ");
while (!isEmpty()) {
int v = dequeue();
printf("%d ", v);
for (int i = 0; i < n; i++) {
if (adj[v][i] == 1 && !visited[i]) {
visited[i] = 1;
enqueue(i);
}
}
}
printf("\n");
}
int main() {
int n = 6; // 6 vertices: 0, 1, 2, 3, 4, 5
// Define edges (undirected graph)
adj[0][1] = adj[1][0] = 1;
adj[0][2] = adj[2][0] = 1;
adj[1][3] = adj[3][1] = 1;
adj[1][4] = adj[4][1] = 1;
adj[2][5] = adj[5][2] = 1;
printf("=== BFS Using Queue ===\n");
printf("Graph: 0-1, 0-2, 1-3, 1-4, 2-5\n\n");
bfs(0, n); // Start BFS from vertex 0
return 0;
}📤 Output
=== BFS Using Queue ===
Graph: 0-1, 0-2, 1-3, 1-4, 2-5
BFS Traversal: 0 1 2 3 4 5Time & Space Complexity
All fundamental queue operations execute in constant time, making queues highly efficient for managing ordered data streams.
| Operation | Array Queue | Circular Queue | Linked List Queue |
|---|---|---|---|
| Enqueue | O(1) | O(1) | O(1) |
| Dequeue | O(1) | O(1) | O(1) |
| Peek | O(1) | O(1) | O(1) |
| isEmpty | O(1) | O(1) | O(1) |
| Space | O(n) | O(n) | O(n) |
| Feature | Array Queue | Circular Queue | Linked List Queue |
|---|---|---|---|
| Memory size | Fixed | Fixed, fully reused | Dynamic |
| Memory waste | Yes (after dequeue) | None | None |
| Overflow risk | Yes | Yes (at MAX) | No |
| Implementation | Simple | Moderate | Moderate (pointers) |
| Best use case | Learning / Small tasks | Embedded systems | General purpose |
Conclusion
In this tutorial, we covered the Queue data structure from the ground up with complete, working C programs:
- ✅ We understood what a queue is and its FIFO principle
- ✅ We explored all queue operations — enqueue, dequeue, peek, isEmpty, isFull
- ✅ We implemented a queue using a simple Array in C
- ✅ We implemented a Circular Queue to eliminate memory waste
- ✅ We implemented a queue using a Linked List in C
- ✅ We handled Queue Overflow and Underflow with proper error messages
- ✅ We built a real-world BFS Graph Traversal using a queue
- ✅ We compared all three implementations for time and space complexity
Queues are fundamental to computer science. Understanding them deeply will help you tackle CPU scheduling, graph algorithms, networking, and system design problems with confidence. Practice each program by running it locally, modifying the input values, and observing the behavior.
📌 What's Next? After mastering Queues, explore Priority Queues, Deque (Double-Ended Queue), and Binary Trees to continue building your data structures knowledge!
Post a Comment