Queue

A queue is a FIFO (First In, First Out) structure: insert at the rear, delete from the front.

102030frontreardequeueenqueue01234
Queue: enqueue at the rear, dequeue from the front (FIFO)

Circular Queue

A simple array queue wastes space after deletions. A circular queue wraps around using the modulo operator.

C
#include <stdio.h>
#define N 5
int q[N], front = -1, rear = -1;

void enqueue(int x) {
    if ((rear + 1) % N == front) { printf("Queue full\n"); return; }
    if (front == -1) front = 0;
    rear = (rear + 1) % N;
    q[rear] = x;
}
int dequeue() {
    if (front == -1) { printf("Queue empty\n"); return -1; }
    int x = q[front];
    if (front == rear) front = rear = -1;      // last element removed
    else front = (front + 1) % N;
    return x;
}

int main() {
    enqueue(1); enqueue(2); enqueue(3);
    printf("%d ", dequeue());
    printf("%d\n", dequeue());
    enqueue(4);
    printf("front = %d\n", q[front]);
    return 0;
}
1 2 front = 3

Types of Queues

TypeDescription
Simple queueInsert at rear, delete at front
Circular queueRear wraps to the start
DequeInsert/delete at both ends
Priority queueHighest-priority element leaves first (usually a heap)

Uses include CPU scheduling, printer spooling, BFS and buffering.

Track your progress through the Data Structures course