1. Introduction
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle: the first element added is the first one removed. Think of a line of people waiting at a ticket counter — whoever joins first gets served first. Queues are widely used in C programs for task scheduling, breadth-first search (BFS), buffering data (e.g., I/O buffers, print spoolers), and simulating real-world waiting-line systems.
Cricket analogy: A queue mirrors fans lining up outside the stadium gate for an IPL final: the first fan to arrive at 6am is the first one let in, exactly the FIFO principle a queue enforces, unlike a stack where the last person in would somehow enter first.
This lesson implements a queue using a fixed-size array with two index variables, 'front' and 'rear', that track the ends of the queue. A naive array queue wastes space as elements are dequeued, so production-quality implementations typically use a circular queue (wrapping indices with modulo arithmetic) or a linked-list-based queue for unbounded growth.
Cricket analogy: A naive stadium seating chart that never reuses vacated seats after fans leave wastes capacity, just as a naive array queue wastes space after dequeues; production venues reuse seats dynamically the way a circular queue wraps indices with modulo arithmetic.
2. Syntax
#define MAX 100
typedef struct Queue {
int items[MAX];
int front;
int rear;
} Queue;'front' points to the index of the next element to be dequeued, and 'rear' points to the index of the last enqueued element. An empty queue is initialized with front = 0 and rear = -1 (or equivalently, a count of 0).
Cricket analogy: 'front' is like the next fan due to enter the stadium gate, and 'rear' is like the last fan who joined the back of the line; an empty queue before the gates open has front = 0 and rear = -1, meaning no one has been let in and no one is waiting yet.
3. Explanation
The two core queue operations are enqueue (add an element at the rear) and dequeue (remove the element at the front). Enqueue increments 'rear' and stores the new value there; dequeue reads the value at 'front' and increments 'front'. Because elements are always added at one end and removed from the other, the relative order of insertion is preserved — the hallmark of FIFO behavior.
Cricket analogy: Enqueue is like a new fan joining the back of the stadium entry line, incrementing 'rear'; dequeue is like the gate letting the front-most fan in and incrementing 'front'; because entry always happens at one end and exit at the other, fans are let in exactly in the order they arrived, true FIFO.
A queue can be implemented with an array (as shown here) or with a linked list where 'front' and 'rear' are pointers to the head and tail nodes. The linked-list version avoids the wasted-space problem of a simple linear array queue and grows dynamically, similar to how a stack can also be built on either structure.
Cricket analogy: A stadium's entry line can be a fixed physical rope barrier (array) or a flexible chain of stewards who each point to the next person (linked list); the steward-chain version grows to any crowd size without wasting rope, just as a linked-list queue avoids the wasted-space problem of an array queue.
Queue overflow (enqueue when rear == MAX - 1) and queue underflow (dequeue when the queue is empty, front > rear) must always be checked. With a simple linear array queue, once 'front' advances past index 0 due to dequeues, that freed space at the beginning is never reused — this is why circular queues (using modulo arithmetic on indices) are preferred in production code.
Time complexity: enqueue and dequeue are both O(1) since they only touch the element at 'rear' or 'front' and adjust an index. A circular queue keeps this O(1) behavior while also reusing freed slots, unlike a simple linear array queue.
4. Example
#include <stdio.h>
#define MAX 5
typedef struct Queue {
int items[MAX];
int front;
int rear;
} Queue;
void initQueue(Queue *q) {
q->front = 0;
q->rear = -1;
}
int isFull(Queue *q) {
return q->rear == MAX - 1;
}
int isEmpty(Queue *q) {
return q->front > q->rear;
}
void enqueue(Queue *q, int value) {
if (isFull(q)) {
printf("Queue overflow: cannot enqueue %d\n", value);
return;
}
q->items[++(q->rear)] = value;
}
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue underflow: cannot dequeue\n");
return -1; /* sentinel value */
}
return q->items[(q->front)++];
}
int main(void) {
Queue q;
initQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
printf("Dequeued: %d\n", dequeue(&q));
printf("Dequeued: %d\n", dequeue(&q));
enqueue(&q, 40);
printf("Dequeued: %d\n", dequeue(&q));
printf("Dequeued: %d\n", dequeue(&q));
printf("Dequeued: %d\n", dequeue(&q)); /* triggers underflow */
return 0;
}5. Output
Dequeued: 10
Dequeued: 20
Dequeued: 30
Dequeued: 40
Queue underflow: cannot dequeue
Dequeued: -16. Key Takeaways
- A queue follows FIFO: the first element enqueued is the first one dequeued.
- 'front' tracks the next element to remove; 'rear' tracks the last element added.
- Always guard enqueue against overflow (rear == MAX - 1) and dequeue against underflow (front > rear).
- A simple linear array queue wastes freed slots; circular queues reuse them via modulo indexing.
- Enqueue and dequeue are both O(1) operations.
Practice what you learned
1. What ordering principle does a queue follow?
2. In the array-based queue, what does the condition 'front > rear' typically indicate?
3. What is the main drawback of a simple linear (non-circular) array-based queue?
4. What is the time complexity of enqueue and dequeue in an array-based queue?
5. How does a circular queue solve the wasted-space problem of a linear array queue?
Was this page helpful?
You May Also Like
Stack Implementation in C
Master array-based stack implementation in C with push, pop, peek, overflow/underflow checks, and full working code.
Linked List Basics in C
Learn singly linked lists in C: node structs, malloc-based insertion, traversal, and time complexity, with a full compilable example.
Arrays in C
Learn C arrays: 1D and 2D declarations, initialization, passing to functions, pointer decay, and out-of-bounds pitfalls with examples.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics