UNIT 07Prerequisite: Unit 06 — Stacks60 min read
If a stack is a pile of plates — a queue is a line of people at a ticket counter. The first person in the line is the first one served. The last person in the line waits until everyone ahead of them is done. No jumping, no skipping. First In, First Out.
Queues are everywhere in computing — your print jobs wait in a queue, your CPU runs processes in a queue, every BFS graph traversal uses a queue. In this unit we build queues from scratch two ways, fix the classic wasted-space problem with circular queues, and understand every real-world application.
// Section 1
What is a Queue?
A queue is a linear data structure with two open ends — one for adding elements (REAR) and one for removing elements (FRONT). You always add at the rear and remove from the front — just like a real queue.
🎟️ The ticket counter — FIFO in action
Three people are in line: Alice, Bob, Carol. A new person Dave joins at the rear. The counter serves Alice first — she is at the front.
FRONT — where removal happens
The oldest element. Always served next. Like the person at the front of the line.
REAR — where addition happens
The newest element. Just joined. Like the person who just got in line.
enqueue(x)
Add element x at the REAR of the queue
O(1)dequeue()
Remove and return the element at FRONT
O(1)peek()
Read the FRONT element without removing it
O(1)isEmpty()
Check if the queue has no elements
O(1)💡 Note
Stack vs Queue — one line summary: Stack = LIFO, one end. Queue = FIFO, two ends. Both have O(1) operations. Choose based on whether you need the newest item (stack) or the oldest item (queue).
// Section 2
Queue Using an Array
To build a queue with an array we track two indices: front (where we remove from) and rear (where we add to). Both start at -1. When we enqueue, rear moves right. When we dequeue, front moves right.
#include <stdio.h>
#define MAX 6
struct Queue {
int data[MAX];
int front;
int rear;
};
typedef struct Queue Queue;
void initQueue(Queue *q) {
q->front = -1;
q->rear = -1;
}
int isEmpty(Queue *q) {
return q->front == -1;
}
int isFull(Queue *q) {
return q->rear == MAX - 1;
}
void enqueue(Queue *q, int value) {
if (isFull(q)) {
printf("Queue is full — cannot enqueue %d\n", value);
return;
}
if (isEmpty(q)) {
q->front = 0; /* first element — set front to 0 */
}
q->rear++;
q->data[q->rear] = value;
printf("Enqueued: %d\n", value);
}
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty — nothing to dequeue\n");
return -1;
}
int val = q->data[q->front];
if (q->front == q->rear) {
/* last element removed — reset both pointers */
q->front = -1;
q->rear = -1;
} else {
q->front++; /* move front forward */
}
return val;
}
int peek(Queue *q) {
if (isEmpty(q)) return -1;
return q->data[q->front];
}
void printQueue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
return;
}
printf("Queue (front → rear): ");
int i;
for (i = q->front; i <= q->rear; i++) {
printf("%d ", q->data[i]);
}
printf("\n");
}
int main() {
Queue q;
initQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
enqueue(&q, 40);
printQueue(&q); /* Queue (front → rear): 10 20 30 40 */
printf("Dequeue: %d\n", dequeue(&q)); /* Dequeue: 10 */
printf("Dequeue: %d\n", dequeue(&q)); /* Dequeue: 20 */
printQueue(&q); /* Queue (front → rear): 30 40 */
printf("Peek: %d\n", peek(&q)); /* Peek: 30 */
return 0;
}
// Section 3
The Wasted Space Problem — Why Circular Queue Exists
The simple array queue has a critical flaw. Once you dequeue elements, the slots at the front of the array become empty — but you can never use them again because rear can only move right, never left. Eventually the queue reports "full" even though most of the array is empty.
// After enqueueing 6 items then dequeueing 4 — rear = 5 (MAX-1), looks "full"
rear == MAX-1 → isFull() returns true — but 4 slots are empty and unused!
⚠️ Important
This is a real problem in systems programming. Imagine a network packet buffer that reports full after processing a few thousand packets — even though most of the buffer is empty. The fix is the circular queue.
// Section 4
Circular Queue — Fixing Wasted Space
A circular queue wraps around. When rear reaches the last index, the next enqueue goes back to index 0 — if that slot is free. The array is treated as a circle, not a straight line. We achieve this with one elegant trick: the modulo operator.
// rear = (rear + 1) % MAX — wraps back to 0 when it reaches MAX
Linear (broken)
rear can't move → STUCK
→
Circular (fixed)
70 wraps to index 0 ✓
#include <stdio.h>
#define MAX 6
struct CQueue {
int data[MAX];
int front;
int rear;
int size; /* track actual number of elements */
};
typedef struct CQueue CQueue;
void initCQ(CQueue *q) {
q->front = 0;
q->rear = -1;
q->size = 0;
}
int isEmptyCQ(CQueue *q) { return q->size == 0; }
int isFullCQ(CQueue *q) { return q->size == MAX; }
void enqueueCQ(CQueue *q, int value) {
if (isFullCQ(q)) {
printf("Circular queue is full\n");
return;
}
q->rear = (q->rear + 1) % MAX; /* wrap around using modulo */
q->data[q->rear] = value;
q->size++;
printf("Enqueued: %d at index %d\n", value, q->rear);
}
int dequeueCQ(CQueue *q) {
if (isEmptyCQ(q)) {
printf("Circular queue is empty\n");
return -1;
}
int val = q->data[q->front];
q->front = (q->front + 1) % MAX; /* wrap front around too */
q->size--;
return val;
}
void printCQ(CQueue *q) {
if (isEmptyCQ(q)) { printf("Queue is empty\n"); return; }
printf("Circular queue: ");
int i, idx = q->front;
for (i = 0; i < q->size; i++) {
printf("%d ", q->data[idx]);
idx = (idx + 1) % MAX;
}
printf("\n");
}
int main() {
CQueue q;
initCQ(&q);
enqueueCQ(&q, 10); /* index 0 */
enqueueCQ(&q, 20); /* index 1 */
enqueueCQ(&q, 30); /* index 2 */
enqueueCQ(&q, 40); /* index 3 */
enqueueCQ(&q, 50); /* index 4 */
enqueueCQ(&q, 60); /* index 5 */
printf("Dequeue: %d\n", dequeueCQ(&q)); /* 10 — front moves to index 1 */
printf("Dequeue: %d\n", dequeueCQ(&q)); /* 20 — front moves to index 2 */
enqueueCQ(&q, 70); /* wraps around to index 0 — the slot freed earlier */
enqueueCQ(&q, 80); /* wraps around to index 1 */
printCQ(&q); /* 30 40 50 60 70 80 — all 6 slots used efficiently */
return 0;
}
🎯 Pro Tip
The modulo trick explained: When rear = 5 (MAX-1) and MAX = 6, doing (5 + 1) % 6 = 0 — rear wraps back to index 0. This single line of arithmetic turns a straight array into a circular buffer. Used everywhere: operating system scheduling, network buffers, audio processing.
// Section 5
Queue Using a Linked List
A linked list queue has no size limit and no wasted space problem. We keep two pointers — front pointing to the first node (dequeue here) and rear pointing to the last node (enqueue here). Enqueue is O(1) because we have the rear pointer directly.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
typedef struct Node Node;
/* keep both front and rear pointers */
Node *front = NULL;
Node *rear = NULL;
int isEmptyLL() { return front == NULL; }
void enqueueLL(int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (rear == NULL) {
/* empty queue — new node is both front and rear */
front = rear = newNode;
} else {
rear->next = newNode; /* attach at rear */
rear = newNode; /* move rear forward */
}
}
int dequeueLL() {
if (isEmptyLL()) {
printf("Queue is empty\n");
return -1;
}
Node *temp = front;
int val = temp->data;
front = front->next; /* move front forward */
if (front == NULL) {
rear = NULL; /* queue became empty — reset rear too */
}
free(temp);
return val;
}
void printQueueLL() {
Node *current = front;
printf("Queue (front → rear): ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
enqueueLL(10);
enqueueLL(20);
enqueueLL(30);
enqueueLL(40);
printQueueLL(); /* 10 20 30 40 */
printf("Dequeue: %d\n", dequeueLL()); /* 10 */
printf("Dequeue: %d\n", dequeueLL()); /* 20 */
printQueueLL(); /* 30 40 */
return 0;
}
// Section 6
Deque — Double Ended Queue
A Deque (pronounced "deck") is a queue where you can insert and delete from both ends — front and rear. It is more flexible than both stack and queue and can act as either. Real use: the browser's back/forward history, sliding window problems in DSA.
| Operation | What it does | Time |
|---|
| insertFront(x) | Add x at the FRONT | O(1) |
| insertRear(x) | Add x at the REAR | O(1) |
| deleteFront() | Remove from FRONT | O(1) |
| deleteRear() | Remove from REAR | O(1) |
| peekFront() | Read FRONT without removing | O(1) |
| peekRear() | Read REAR without removing | O(1) |
#include <stdio.h>
#define MAX 8
struct Deque {
int data[MAX];
int front;
int rear;
int size;
};
typedef struct Deque Deque;
void initDeque(Deque *dq) {
dq->front = MAX / 2; /* start in the middle so both ends have room */
dq->rear = MAX / 2 - 1;
dq->size = 0;
}
int isEmptyDQ(Deque *dq) { return dq->size == 0; }
int isFullDQ(Deque *dq) { return dq->size == MAX; }
void insertRear(Deque *dq, int val) {
if (isFullDQ(dq)) { printf("Deque full\n"); return; }
dq->rear = (dq->rear + 1) % MAX;
dq->data[dq->rear] = val;
dq->size++;
}
void insertFront(Deque *dq, int val) {
if (isFullDQ(dq)) { printf("Deque full\n"); return; }
dq->front = (dq->front - 1 + MAX) % MAX; /* move front backward (wrap) */
dq->data[dq->front] = val;
dq->size++;
}
int deleteRear(Deque *dq) {
if (isEmptyDQ(dq)) return -1;
int val = dq->data[dq->rear];
dq->rear = (dq->rear - 1 + MAX) % MAX;
dq->size--;
return val;
}
int deleteFront(Deque *dq) {
if (isEmptyDQ(dq)) return -1;
int val = dq->data[dq->front];
dq->front = (dq->front + 1) % MAX;
dq->size--;
return val;
}
int main() {
Deque dq;
initDeque(&dq);
insertRear(&dq, 10); /* [10] */
insertRear(&dq, 20); /* [10, 20] */
insertFront(&dq, 5); /* [5, 10, 20] */
insertFront(&dq, 1); /* [1, 5, 10, 20] */
printf("Delete front: %d\n", deleteFront(&dq)); /* 1 */
printf("Delete rear: %d\n", deleteRear(&dq)); /* 20 */
/* remaining: [5, 10] */
return 0;
}
// Section 7
Priority Queue — Not All Are Equal
In a normal queue, everyone waits in order. In a priority queue, the element with the highest priority is served first — regardless of when it arrived. Think of a hospital emergency room: a critical patient goes ahead of someone with a minor injury, even if the minor patient arrived first.
Simple priority queue using an ordered array:
P3: Surgery
P2: X-Ray
P2: Blood
P1: Check
Surgery is served first — highest priority, regardless of arrival order
#include <stdio.h>
#define MAX 10
struct PQItem {
int data;
int priority; /* higher number = higher priority */
};
struct PQueue {
struct PQItem items[MAX];
int size;
};
typedef struct PQueue PQueue;
void initPQ(PQueue *pq) { pq->size = 0; }
int isEmptyPQ(PQueue *pq) { return pq->size == 0; }
void enqueuePQ(PQueue *pq, int data, int priority) {
if (pq->size == MAX) { printf("Priority queue full\n"); return; }
pq->items[pq->size].data = data;
pq->items[pq->size].priority = priority;
pq->size++;
}
/* dequeue returns the item with the HIGHEST priority */
int dequeuePQ(PQueue *pq) {
if (isEmptyPQ(pq)) return -1;
int maxIdx = 0; /* index of highest priority item */
int i;
for (i = 1; i < pq->size; i++) {
if (pq->items[i].priority > pq->items[maxIdx].priority) {
maxIdx = i;
}
}
int val = pq->items[maxIdx].data;
/* remove by shifting remaining items left */
for (i = maxIdx; i < pq->size - 1; i++) {
pq->items[i] = pq->items[i + 1];
}
pq->size--;
return val;
}
int main() {
PQueue pq;
initPQ(&pq);
enqueuePQ(&pq, 100, 1); /* low priority */
enqueuePQ(&pq, 200, 3); /* high priority */
enqueuePQ(&pq, 300, 2); /* medium priority */
enqueuePQ(&pq, 400, 3); /* also high priority */
printf("%d\n", dequeuePQ(&pq)); /* 200 (priority 3, arrived first) */
printf("%d\n", dequeuePQ(&pq)); /* 400 (priority 3) */
printf("%d\n", dequeuePQ(&pq)); /* 300 (priority 2) */
printf("%d\n", dequeuePQ(&pq)); /* 100 (priority 1) */
return 0;
}
💡 Note
Note: This simple O(n) priority queue works for learning. In production systems, priority queues are implemented using a Heap data structure which gives O(log n) enqueue and dequeue. We build heaps in Unit 13 — and you will see exactly why they are better.
// Section 8
What This Looks Like at Work — Real Queue Uses
🖨️
Printer Spooling
Every office network
When multiple people print, jobs go into a queue. First print request sent = first document printed. Exactly FIFO. The OS manages this with a queue internally.
⚙️
CPU Process Scheduling
Every operating system
Your OS uses multiple queues to decide which program gets CPU time next. Ready queue, waiting queue, I/O queue — all managed using queue data structures.
💬
Message Delivery — WhatsApp, Kafka
WhatsApp · Zomato · Swiggy
Messages are queued at the server and delivered in order. Apache Kafka is essentially a distributed queue that handles billions of messages per day for companies like Swiggy.
🌐
Web Server Request Handling
Razorpay · PhonePe · Zerodha
When thousands of requests hit a payment API at once, they are queued. The server processes them one by one — fairly, in order — preventing overload.
🔍
BFS Graph Traversal
Google Search · LinkedIn · Maps
Breadth-First Search — which we cover in Unit 15 — uses a queue to visit nodes level by level. Every shortest-path algorithm in maps and social networks relies on this.
// Section 9
All Queue Types — Side by Side
| Type | Add at | Remove from | Key feature | Use case |
|---|
| Simple Queue | Rear | Front | FIFO, fixed array | Basic ordering tasks |
| Circular Queue | Rear (wraps) | Front (wraps) | No wasted space | Buffers, OS scheduling |
| Queue (LL) | Rear | Front | Dynamic size | Unknown max size |
| Deque | Front or Rear | Front or Rear | Both ends flexible | Sliding window, history |
| Priority Queue | Anywhere | Highest priority first | Order by priority | Scheduling, Dijkstra |
// What's Next
You Are Ready for Unit 08
You now understand all queue variants — simple, circular, linked list, deque, and priority queue. You also know why queues are used in real systems from printers to payment APIs to graph algorithms.
In Unit 08 we tackle Recursion — the concept that trips up almost every beginner. A function that calls itself. We will explain it more clearly than any textbook ever has, trace every call step by step, and build up to the legendary Tower of Hanoi problem.
UP NEXT → UNIT 08
Recursion — A Function That Calls Itself
Base case, recursive case, call stack tracing, Tower of Hanoi — made simple.
🎯 Key Takeaways
- ✓A queue is FIFO — First In, First Out. Add at REAR, remove from FRONT
- ✓Four operations: enqueue (add rear), dequeue (remove front), peek (read front), isEmpty — all O(1)
- ✓Simple array queue wastes space — once front moves right, those slots can never be reused
- ✓Circular queue fixes this with modulo: rear = (rear + 1) % MAX — wraps around to use freed slots
- ✓Linked list queue: no size limit, no wasted space, enqueue and dequeue both O(1) with front and rear pointers
- ✓Deque allows insert and delete from BOTH ends — more flexible than stack or queue
- ✓Priority queue serves highest priority first — not necessarily the oldest. Used in scheduling and Dijkstra
- ✓Real uses: printer spooling, CPU scheduling, message queues (Kafka), BFS graph traversal
- ✓Stack vs Queue: stack = newest first (LIFO), queue = oldest first (FIFO)