Queues in C — Detailed Lesson
0%
Data Structures  ·  Queues

Queues in C —
Deep Dive

Understand the queue from the ground up — FIFO principle, front/rear pointers, every operation explained clearly, then two complete unique programs: a circular queue with all operations, and a real-world printer job spooler simulation.

1
Circular Queue
2
Printer Job Spooler

🚌 What is a Queue?

A queue is a linear data structure that follows the First In, First Out (FIFO) principle — the element inserted first is the one removed first. Think of a ticket counter queue: the first person to join the line is the first person to be served. New people join at the rear (back) of the line and leave from the front.

In C, a queue is most commonly implemented using a fixed-size array with two integer pointers: front (the index of the element to be dequeued next) and rear (the index where the next element will be enqueued). The circular queue (ring buffer) is the standard array-based queue — it wraps front and rear around using modulo arithmetic so that freed slots are reused, avoiding the wasted-space problem of a simple linear queue.

Queues are used everywhere: OS process scheduling, print spoolers, network packet buffers, breadth-first search (BFS), keyboard input buffers, producer-consumer pipelines, and streaming audio/video buffers.

enqueue(val)
void enqueue(Queue*, int)
Add element at the rear. Check for overflow first. O(1).
dequeue()
int dequeue(Queue*)
Remove and return element from front. Check for underflow. O(1).
peekFront()
int peekFront(Queue*)
Return front element without removing it. O(1).
peekRear()
int peekRear(Queue*)
Return rear element without removing it. O(1).
isEmpty()
int isEmpty(Queue*)
Returns 1 if size == 0, 0 otherwise. O(1).
isFull()
int isFull(Queue*)
Returns 1 if size == MAX, 0 otherwise. O(1).
FIFO — first in, first out: enqueue at REAR, dequeue from FRONT
Enqueue 10
10
·
·
·
·
← front=0 rear=0
Enqueue 20, 30
10
20
30
·
·
← front=0(teal) rear=2(violet)
Dequeue → 10
10*
20
30
·
·
← front moves to 1, 10 returned
Enqueue 40, 50
·
20
30
40
50
← front=1 rear=4, linear queue now full!
The linear array queue wastes space. Once elements are dequeued, their slots at the front are permanently abandoned. Even though size is small, rear keeps advancing until it hits MAX — the queue falsely appears full. The circular queue fixes this by wrapping both pointers using modulo: rear = (rear + 1) % MAX.
circular queue — modulo wrap reuses freed slots
Fill queue
A
B
C
D
E
← front=0 rear=4, full (size=5)
Dequeue 3
A*
B*
C*
D
E
← front=3 rear=4, size=2
Enqueue F, G, H
F
G
H
D
E
← rear wrapped to 2! slots reused
Wrap formula
rear = (rear + 1) % MAX
← front uses same formula
All queue operations are O(1) — enqueue advances rear by one slot, dequeue advances front by one slot, both with modulo wrap. Track size as a separate counter to distinguish full (size == MAX) from empty (size == 0) without ambiguity — the two conditions would otherwise look identical when front and rear are at the same index.
example 1 — circular queue
1
🔄 Complete Circular Queue — Every Operation Demonstrated
Build a full circular queue with enqueue, dequeue, peekFront, peekRear, display — then test every edge case including wrap-around
Circular Queue
This program builds a complete, production-quality circular queue in C. The queue is implemented as a struct with a fixed data array, front and rear indices, and a size counter. All operations use modulo arithmetic to wrap the indices. The main function demonstrates every scenario: filling the queue, overflow detection, dequeuing, wrap-around enqueuing (reusing freed slots), and underflow. Every edge case is exercised so you can see exactly how the circular behaviour works.
circular_queue.c
C
#include <stdio.h>

#define MAX 6

/* ── Queue structure ── */
typedef struct {
    int data[MAX];
    int front;   /* index of next element to dequeue */
    int rear;    /* index where next enqueue goes    */
    int size;    /* current number of elements        */
} Queue;

/* ── Initialise ── */
void initQueue(Queue *q) {
    q->front = q->rear = q->size = 0;
    printf("Queue initialised (capacity = %d)\n", MAX);
}

/* ── Predicates ── */
int isEmpty(Queue *q) { return q->size == 0; }
int isFull (Queue *q) { return q->size == MAX; }

/* ── Enqueue: add at rear ── */
int enqueue(Queue *q, int val) {
    if (isFull(q)) {
        printf("  OVERFLOW  — cannot enqueue(%d), queue is full!\n", val);
        return 0;
    }
    q->data[q->rear] = val;
    q->rear  = (q->rear + 1) % MAX;   /* circular wrap */
    q->size++;
    printf("  enqueue(%2d)  rear=%-2d  size=%d\n",
           val, q->rear, q->size);
    return 1;
}

/* ── Dequeue: remove from front ── */
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("  UNDERFLOW — cannot dequeue, queue is empty!\n");
        return -1;
    }
    int val  = q->data[q->front];
    q->front = (q->front + 1) % MAX;  /* circular wrap */
    q->size--;
    printf("  dequeue() -> %2d  front=%-2d  size=%d\n",
           val, q->front, q->size);
    return val;
}

/* ── Peek front: read without removing ── */
int peekFront(Queue *q) {
    if (isEmpty(q)) {
        printf("  peekFront() — queue is empty!\n");
        return -1;
    }
    printf("  peekFront() -> %d\n", q->data[q->front]);
    return q->data[q->front];
}

/* ── Peek rear: read last element added ── */
int peekRear(Queue *q) {
    if (isEmpty(q)) {
        printf("  peekRear() — queue is empty!\n");
        return -1;
    }
    int rearIdx = (q->rear - 1 + MAX) % MAX;
    printf("  peekRear()  -> %d\n", q->data[rearIdx]);
    return q->data[rearIdx];
}

/* ── Display: print front-to-rear ── */
void display(Queue *q) {
    if (isEmpty(q)) {
        printf("  Queue (FRONT -> REAR): [empty]\n");
        return;
    }
    printf("  Queue (FRONT -> REAR): FRONT|");
    for (int i = 0; i < q->size; i++) {
        int idx = (q->front + i) % MAX;
        printf(" %d |", q->data[idx]);
    }
    printf("REAR  [front=%d rear=%d size=%d]\n",
           q->front, q->rear, q->size);
}

int main() {
    Queue q;
    initQueue(&q);

    /* 1. Normal enqueues */
    printf("\n--- Enqueue 6 elements ---\n");
    enqueue(&q, 10); enqueue(&q, 20); enqueue(&q, 30);
    enqueue(&q, 40); enqueue(&q, 50); enqueue(&q, 60);
    display(&q);

    /* 2. Overflow */
    printf("\n--- Overflow test ---\n");
    enqueue(&q, 99);

    /* 3. Peek */
    printf("\n--- Peek front and rear ---\n");
    peekFront(&q);
    peekRear(&q);

    /* 4. Dequeue 4 elements */
    printf("\n--- Dequeue 4 elements ---\n");
    dequeue(&q); dequeue(&q);
    dequeue(&q); dequeue(&q);
    display(&q);

    /* 5. Enqueue more — slots WRAP AROUND */
    printf("\n--- Enqueue 4 more (circular wrap!) ---\n");
    enqueue(&q, 70); enqueue(&q, 80);
    enqueue(&q, 90); enqueue(&q, 100);
    display(&q);

    /* 6. Drain queue completely */
    printf("\n--- Drain all elements ---\n");
    while (!isEmpty(&q)) dequeue(&q);
    display(&q);

    /* 7. Underflow */
    printf("\n--- Underflow test ---\n");
    dequeue(&q);
    peekFront(&q);

    printf("\n=== Done ===\n");
    return 0;
}
output
Queue initialised (capacity = 6)

--- Enqueue 6 elements ---
  enqueue(10)  rear=1   size=1
  enqueue(20)  rear=2   size=2
  enqueue(30)  rear=3   size=3
  enqueue(40)  rear=4   size=4
  enqueue(50)  rear=5   size=5
  enqueue(60)  rear=0   size=6
  Queue (FRONT -> REAR): FRONT| 10 | 20 | 30 | 40 | 50 | 60 |REAR  [front=0 rear=0 size=6]

--- Overflow test ---
  OVERFLOW  — cannot enqueue(99), queue is full!

--- Peek front and rear ---
  peekFront() -> 10
  peekRear()  -> 60

--- Dequeue 4 elements ---
  dequeue() -> 10  front=1   size=5
  dequeue() -> 20  front=2   size=4
  dequeue() -> 30  front=3   size=3
  dequeue() -> 40  front=4   size=2
  Queue (FRONT -> REAR): FRONT| 50 | 60 |REAR  [front=4 rear=0 size=2]

--- Enqueue 4 more (circular wrap!) ---
  enqueue(70)  rear=1   size=3
  enqueue(80)  rear=2   size=4
  enqueue(90)  rear=3   size=5
  enqueue(100) rear=4   size=6
  Queue (FRONT -> REAR): FRONT| 50 | 60 | 70 | 80 | 90 | 100 |REAR  [front=4 rear=4 size=6]

--- Drain all elements ---
  dequeue() ->  50  front=5   size=5
  dequeue() ->  60  front=0   size=4
  dequeue() ->  70  front=1   size=3
  dequeue() ->  80  front=2   size=2
  dequeue() ->  90  front=3   size=1
  dequeue() -> 100  front=4   size=0
  Queue (FRONT -> REAR): [empty]

--- Underflow test ---
  UNDERFLOW — cannot dequeue, queue is empty!
  peekFront() — queue is empty!

=== Done ===
array slot usage at key moments — front and rear wrap around the ring
After 6 enqueues
10
20
30
40
50
60
← front=0 rear=0 (full, rear wrapped!)
After 4 dequeues
10*
20*
30*
40*
50
60
← front=4, slots 0-3 freed
After 4 enqueues
70
80
90
100
50
60
← rear wrapped to 4, slots 0-3 reused
Drain order
50
60
70
80
90
100
← FIFO preserved even after wrap
When front == rear and size > 0, the queue is FULL. When front == rear and size == 0, it is EMPTY. Both conditions produce the same front/rear positions — this is why tracking size separately is essential. Without it, you cannot distinguish full from empty when the indices coincide after wrapping.
peekRear uses (rear - 1 + MAX) % MAX. Since rear always points to the next empty slot (where the next enqueue will land), the last actual element is one position back. Adding MAX before modulo prevents a negative index when rear == 0.
example 2 — printer job spooler
2
🖨️ Printer Job Spooler — Queue in the Real World
Users submit print jobs that queue up; the printer processes them one-by-one in arrival order — classic FIFO scheduling
Real-World App
A print spooler is one of the most famous real-world uses of queues. When you press Print, your job is added to the back of the printer queue. The printer works through the queue front-to-back, processing each job in the exact order it arrived. This program simulates a printer spooler: users can submit jobs (enqueue), the printer can process the next job (dequeue and simulate printing), and you can view the pending queue at any time. Each job carries a name, a page count, and a priority level (Normal or Urgent). Urgent jobs use a second express queue that is always processed first.
printer_spooler.c
C
#include <stdio.h>
#include <string.h>

#define MAX   8
#define NLEN  30

/* ── Print Job ── */
typedef struct {
    int  jobId;
    char owner[NLEN];
    int  pages;
    char priority[8];  /* "Normal" or "Urgent" */
} Job;

/* ── Job Queue ── */
typedef struct {
    Job  items[MAX];
    int  front, rear, size;
} JQueue;

void jq_init  (JQueue *q) { q->front=q->rear=q->size=0; }
int  jq_empty (JQueue *q) { return q->size==0; }
int  jq_full  (JQueue *q) { return q->size==MAX; }

void jq_enq(JQueue *q, Job j) {
    if(jq_full(q)){printf("  [SPOOLER] Queue full! Job %d rejected.\n",j.jobId);return;}
    q->items[q->rear] = j;
    q->rear  = (q->rear + 1) % MAX;
    q->size++;
}

Job jq_deq(JQueue *q) {
    Job j = q->items[q->front];
    q->front = (q->front + 1) % MAX;
    q->size--;
    return j;
}

/* ── Show pending queue ── */
void showQueue(const char *label, JQueue *q) {
    printf("  %s (%d job%s pending):\n",
           label, q->size, q->size==1?"":"s");
    if(jq_empty(q)){printf("    (empty)\n");return;}
    printf("    %-5s %-16s %5s  %s\n","ID","Owner","Pages","Priority");
    printf("    %s\n","-------------------------------------------");
    for(int i=0; i<q->size; i++){
        Job *j = &q->items[(q->front+i)%MAX];
        printf("    %-5d %-16s %5d  %s\n",
               j->jobId, j->owner, j->pages, j->priority);
    }
}

/* ── Submit a job ── */
void submit(JQueue *normal, JQueue *urgent, Job j) {
    printf("  SUBMIT  Job#%02d  %-14s  %2d page(s)  [%s]\n",
           j.jobId, j.owner, j.pages, j.priority);
    if(strcmp(j.priority, "Urgent")==0)
        jq_enq(urgent, j);
    else
        jq_enq(normal, j);
}

/* ── Process next job: urgent first ── */
void processNext(JQueue *normal, JQueue *urgent) {
    if(jq_empty(urgent) && jq_empty(normal)){
        printf("  PRINTER  Idle — no jobs in queue.\n");
        return;
    }
    Job j = (!jq_empty(urgent)) ? jq_deq(urgent) : jq_deq(normal);
    printf("  PRINT    Job#%02d  %-14s  %2d page(s)  [%s]  ...DONE\n",
           j.jobId, j.owner, j.pages, j.priority);
}

int main() {
    JQueue normal, urgent;
    jq_init(&normal); jq_init(&urgent);

    printf("=== Printer Spooler Simulation ===\n\n");

    /* ── Batch of submissions ── */
    printf("--- Users submit print jobs ---\n");
    submit(&normal, &urgent, (Job){1, "Ananya",    5,  "Normal"});
    submit(&normal, &urgent, (Job){2, "Rohan",     12, "Normal"});
    submit(&normal, &urgent, (Job){3, "Priya",     2,  "Urgent"});
    submit(&normal, &urgent, (Job){4, "Karan",     8,  "Normal"});
    submit(&normal, &urgent, (Job){5, "Sunita",    1,  "Urgent"});
    submit(&normal, &urgent, (Job){6, "Arjun",     20, "Normal"});
    submit(&normal, &urgent, (Job){7, "Meena",     3,  "Normal"});

    printf("\n");
    showQueue("Urgent Queue", &urgent);
    printf("\n");
    showQueue("Normal Queue", &normal);

    /* ── Printer processes jobs ── */
    printf("\n--- Printer processes all jobs (urgent first) ---\n");
    while(!jq_empty(&urgent) || !jq_empty(&normal))
        processNext(&normal, &urgent);

    /* ── Late urgent job arrives ── */
    printf("\n--- Late urgent job arrives mid-session ---\n");
    submit(&normal, &urgent, (Job){8, "Principal",  1,  "Urgent"});
    submit(&normal, &urgent, (Job){9, "Vijay",       6,  "Normal"});
    submit(&normal, &urgent, (Job){10,"Divya",       4,  "Normal"});

    printf("\n");
    showQueue("Urgent Queue", &urgent);
    printf("\n");
    showQueue("Normal Queue", &normal);
    printf("\n--- Resume printing ---\n");
    while(!jq_empty(&urgent) || !jq_empty(&normal))
        processNext(&normal, &urgent);

    /* ── Idle check ── */
    printf("\n--- Queue drained ---\n");
    processNext(&normal, &urgent);
    printf("\n=== Session complete ===\n");
    return 0;
}
output
=== Printer Spooler Simulation ===

--- Users submit print jobs ---
  SUBMIT  Job#01  Ananya          5 page(s)  [Normal]
  SUBMIT  Job#02  Rohan          12 page(s)  [Normal]
  SUBMIT  Job#03  Priya           2 page(s)  [Urgent]
  SUBMIT  Job#04  Karan           8 page(s)  [Normal]
  SUBMIT  Job#05  Sunita          1 page(s)  [Urgent]
  SUBMIT  Job#06  Arjun          20 page(s)  [Normal]
  SUBMIT  Job#07  Meena           3 page(s)  [Normal]

  Urgent Queue (2 jobs pending):
    ID    Owner            Pages  Priority
    -------------------------------------------
    3     Priya                2  Urgent
    5     Sunita               1  Urgent

  Normal Queue (5 jobs pending):
    ID    Owner            Pages  Priority
    -------------------------------------------
    1     Ananya               5  Normal
    2     Rohan               12  Normal
    4     Karan                8  Normal
    6     Arjun               20  Normal
    7     Meena                3  Normal

--- Printer processes all jobs (urgent first) ---
  PRINT    Job#03  Priya           2 page(s)  [Urgent]  ...DONE
  PRINT    Job#05  Sunita          1 page(s)  [Urgent]  ...DONE
  PRINT    Job#01  Ananya          5 page(s)  [Normal]  ...DONE
  PRINT    Job#02  Rohan          12 page(s)  [Normal]  ...DONE
  PRINT    Job#04  Karan           8 page(s)  [Normal]  ...DONE
  PRINT    Job#06  Arjun          20 page(s)  [Normal]  ...DONE
  PRINT    Job#07  Meena           3 page(s)  [Normal]  ...DONE

--- Late urgent job arrives mid-session ---
  SUBMIT  Job#08  Principal       1 page(s)  [Urgent]
  SUBMIT  Job#09  Vijay           6 page(s)  [Normal]
  SUBMIT  Job#10  Divya           4 page(s)  [Normal]

  Urgent Queue (1 job pending):
    ID    Owner            Pages  Priority
    -------------------------------------------
    8     Principal            1  Urgent

  Normal Queue (2 jobs pending):
    ID    Owner            Pages  Priority
    -------------------------------------------
    9     Vijay                6  Normal
    10    Divya                4  Normal

--- Resume printing ---
  PRINT    Job#08  Principal       1 page(s)  [Urgent]  ...DONE
  PRINT    Job#09  Vijay           6 page(s)  [Normal]  ...DONE
  PRINT    Job#10  Divya           4 page(s)  [Normal]  ...DONE

--- Queue drained ---
  PRINTER  Idle — no jobs in queue.

=== Session complete ===
two-queue spooler — urgent jobs always print before normal jobs
After submit
Urgent: P3,P5
Normal: P1,P2,P4,P6,P7
← 2 urgent, 5 normal
Print order
P3
P5
P1
P2
P4
P6
P7
← urgent drain first, then normal FIFO
Late urgent
P8
P9
P10
← P8 jumps ahead of P9, P10
The two-queue pattern (urgent + normal) is exactly how real OS print spoolers work. Windows Print Spooler, CUPS on Linux, and virtually every printer management system internally maintains a priority queue or dual-queue: high-priority jobs interrupt the normal FIFO order. The same pattern is used in OS process schedulers, hospital patient triage, and network packet routers.
FIFO is preserved separately within each queue. Urgent jobs are served before all normal jobs, but among urgent jobs, they still go in submission order (Priya before Sunita because Priya submitted first). Same for normal jobs. This is because each queue individually obeys FIFO — the priority only determines which queue to drain first.
key concepts checklist
  • A queue is a FIFO structure — First In, First Out. Elements enter at the rear and leave from the front. All operations (enqueue, dequeue, peekFront, peekRear, isEmpty, isFull) are O(1).
  • Use a circular queue for array-based queues. Enqueue: data[rear] = val; rear = (rear+1) % MAX; size++. Dequeue: val = data[front]; front = (front+1) % MAX; size--.
  • Track size as a separate counter. When front == rear, size tells you whether the queue is full (size == MAX) or empty (size == 0) — without it the two states are indistinguishable.
  • Always guard against overflow (size == MAX) before enqueue, and underflow (size == 0) before dequeue. peekRear uses (rear - 1 + MAX) % MAX to avoid a negative index.
  • Real-world use — Printer Spooler: two queues (urgent + normal). Submit routes to urgent or normal queue based on priority. Process always drains urgent queue first, then normal — FIFO preserved within each queue.
  • Other classic queue applications: BFS graph traversal (process level by level), OS CPU scheduling (round-robin), keyboard/mouse input buffers, network packet queuing, and producer-consumer pipelines.