Queue & Circular Queue · Data Structures

A queue adds at one end (the rear) and removes from the other (the front): FIFO — First In, First Out. It models every real queue: people at a ticket counter, print jobs, network packets, processes waiting for the CPU.

Enqueue at the rear, dequeue from the front. 10 arrived first, so it leaves first.

Operation	Meaning	Cost
`enqueue(x)`	add `x` at the rear	O(1)
`dequeue()`	remove and return the front item	O(1)
`front()` / `peek()`	look at the front item	O(1)
`isEmpty()`, `isFull()`	status checks	O(1)

The problem with a simple array queue

Use front and rear indexes into an array. Enqueue does a[++rear] = x; dequeue does front++. But after a few dequeues, the empty slots at the start of the array are never reused: the queue reports "full" when rear reaches the end, even if it is mostly empty.

Linear queue after three dequeues: slots 0–2 are wasted, and rear is already at the end.

Circular queue

The fix: let the indexes wrap around to 0 using % capacity. The array behaves like a ring.

enqueue: rear = (rear + 1) % N; a[rear] = x;
dequeue: x = a[front]; front = (front + 1) % N;
keep a count to tell full from empty.

#include <stdio.h>
#define N 5

int q[N], front = 0, rear = -1, count = 0;

int enqueue(int x) {
    if (count == N) { printf("Queue full, cannot add %d\n", x); return 0; }
    rear = (rear + 1) % N;
    q[rear] = x;
    count++;
    return 1;
}

int dequeue(void) {
    if (count == 0) { printf("Queue empty\n"); return -1; }
    int x = q[front];
    front = (front + 1) % N;
    count--;
    return x;
}

void show(void) {
    printf("queue (front -> rear): ");
    for (int i = 0; i < count; i++) printf("%d ", q[(front + i) % N]);
    printf("  [front=%d rear=%d]\n", front, rear);
}

int main(void) {
    for (int i = 1; i <= 5; i++) enqueue(i * 10);
    show();
    enqueue(60);                         // full
    printf("dequeued %d\n", dequeue());
    printf("dequeued %d\n", dequeue());
    enqueue(60);                         // reuses slot 0
    enqueue(70);                         // reuses slot 1
    show();
    return 0;
}

Output

queue (front -> rear): 10 20 30 40 50   [front=0 rear=4]
Queue full, cannot add 60
dequeued 10
dequeued 20
queue (front -> rear): 30 40 50 60 70   [front=2 rear=1]

Try it Yourself

Linked-list queue

Keep pointers to both ends: enqueue at the tail, dequeue at the head. Both are O(1), and there is no fixed capacity.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int data; struct Node *next; } Node;
Node *front = NULL, *rear = NULL;

void enqueue(int x) {
    Node *n = malloc(sizeof(Node));
    n->data = x; n->next = NULL;
    if (rear == NULL) front = rear = n;
    else { rear->next = n; rear = n; }
}

int dequeue(void) {
    if (front == NULL) return -1;
    Node *t = front;
    int x = t->data;
    front = front->next;
    if (front == NULL) rear = NULL;      // queue became empty
    free(t);
    return x;
}

int main(void) {
    const char *jobs[] = {"report.pdf", "notes.docx", "photo.png"};
    for (int i = 0; i < 3; i++) { enqueue(i); printf("queued %s\n", jobs[i]); }
    int j;
    while ((j = dequeue()) != -1) printf("printing %s\n", jobs[j]);
    return 0;
}

Output

queued report.pdf
queued notes.docx
queued photo.png
printing report.pdf
printing notes.docx
printing photo.png

Try it Yourself

Stack vs queue

	Stack	Queue
Order	LIFO	FIFO
Insert at	top	rear
Remove from	top	front
Typical uses	undo, recursion, DFS, parsing	scheduling, buffering, BFS

Test yourself

4 questions · pick an answer to check it instantly

1
Enqueue 5, 8, 3, then dequeue once. What is at the front?
2
In a circular queue of size 6, rear is 5. Where does the next element go?
3
What problem does a circular queue solve?
4
Which algorithm uses a queue?

#The problem with a simple array queue

#Circular queue

#Linked-list queue

#Stack vs queue

Test yourself

The problem with a simple array queue

Circular queue

Linked-list queue

Stack vs queue