Core Queue Operations

A queue is a linear data structure that enforces FIFO (First-In-First-Out) ordering. The essential primitives are:

• init – create an empty queue
• isEmpty – test for emptiness
• enqueue – append an element at the rear
• dequeue – remove the element at the front
• peek – inspect the front element without removal

Circular Buffer Queue

A fixed-size array wrapped into a ring eliminates the "false-full" problem of a straight array queue.

Structures

typedef struct {
    int head;          // index of the first element
    int tail;          // index where the next element will be inserted
    int capacity;
    ElemType *buffer;
} RingQueue;

Initialisation

void rq_init(RingQueue *q, int cap) {
    q->buffer = malloc(cap * sizeof(ElemType));
    q->head = q->tail = 0;
    q->capacity = cap;
}

Empty & Full Tests

int rq_is_empty(const RingQueue *q) {
    return q->head == q->tail;
}

int rq_is_full(const RingQueue *q) {
    return (q->tail + 1) % q->capacity == q->head;
}

Insertion

void rq_push(RingQueue *q, ElemType value) {
    if (rq_is_full(q)) {
        fprintf(stderr, "Ring buffer overflow\n");
        return;
    }
    q->buffer[q->tail] = value;
    q->tail = (q->tail + 1) % q->capacity;
}

Access Front Element

ElemType rq_front(const RingQueue *q) {
    if (rq_is_empty(q)) {
        fprintf(stderr, "Ring buffer empty\n");
        exit(EXIT_FAILURE);
    }
    return q->buffer[q->head];
}

Removal

ElemType rq_pop(RingQueue *q) {
    if (rq_is_empty(q)) {
        fprintf(stderr, "Ring buffer empty\n");
        exit(EXIT_FAILURE);
    }
    ElemType value = q->buffer[q->head];
    q->head = (q->head + 1) % q->capacity;
    return value;
}

Linked-List Queue (with Sentinel Node)

A dynamic version that never reports "full" and grows on demand.

Structures

typedef struct QNode {
    ElemType data;
    struct QNode *next;
} QNode;

typedef struct {
    QNode *sentinel;   // dummy head node
    QNode *rear;       // pointer to last node
} LinkedQueue;

Initialisation

void lq_init(LinkedQueue *q) {
    q->sentinel = malloc(sizeof(QNode));
    q->sentinel->next = NULL;
    q->rear = q->sentinel;
}

Empty Test

int lq_is_empty(const LinkedQueue *q) {
    return q->sentinel == q->rear;
}

Insertion

void lq_push(LinkedQueue *q, ElemType value) {
    QNode *node = malloc(sizeof(QNode));
    node->data = value;
    node->next = NULL;
    q->rear->next = node;
    q->rear = node;
}

Access Front Elemant

ElemType lq_front(const LinkedQueue *q) {
    if (lq_is_empty(q)) {
        fprintf(stderr, "Queue underflow\n");
        exit(EXIT_FAILURE);
    }
    return q->sentinel->next->data;
}

Removal

ElemType lq_pop(LinkedQueue *q) {
    if (lq_is_empty(q)) {
        fprintf(stderr, "Queue underflow\n");
        exit(EXIT_FAILURE);
    }
    QNode *front = q->sentinel->next;
    ElemType value = front->data;
    q->sentinel->next = front->next;
    if (q->rear == front)          // queue became empty
        q->rear = q->sentinel;
    free(front);
    return value;
}