Queue; Circular Queue

Queue

What is a Queue?

A Queue is a collection of similar type elements where:

• Elements are always added at the REAR location
• Elements are always removed from the FRONT location

Operations are performed using protocol FIFO (First In, First Out).

Real-world analogy: Checkout line at a store — first customer in is first served.

FRONT        [10] [20] [30] [40] [50]        REAR
 ↑                                            ↑
Dequeue (remove)                      Enqueue (add)

Queue Operations

Queue Conditions

// Queue is FULL when:
if (q->rear == size - 1)     // rear reached last index

// Queue is EMPTY when:
if (q->rear == -1 || q->front > q->rear)   // no valid elements

Types of Queue

Queue Implementation Methods

1. Static Implementation — using arrays
2. Dynamic Implementation — using linked lists

Applications of Queue

1. Process scheduling — OS ready queue for CPU scheduling
2. Printing — printer spooler queue
3. BFS (Breadth-First Search) — graph traversal using queue

Additional Applications

• Request handling — web server handles HTTP requests in queue order
• Traffic systems — traffic light queue management
• Keyboard buffer — keystrokes stored in queue
• Call center — customers hold in queue
• Message queue — Kafka, RabbitMQ message processing

Array-Based Queue Implementation in C

#include <stdio.h>
#define SIZE 100

typedef struct {
    int eles[SIZE];
    int front;
    int rear;
} queue_t;

void init_queue(queue_t *q) {
    q->front = -1;
    q->rear = -1;
}

int is_full(queue_t *q) {
    return (q->rear == SIZE - 1);
}

int is_empty(queue_t *q) {
    return (q->rear == -1 || q->front > q->rear);
}

void enqueue(queue_t *q, int value) {
    if (is_full(q)) {
        printf("Queue is full!
Cannot enqueue %d\n", value);
        return;
    }
    if (q->front == -1) q->front = 0;
// first element
    q->rear++;
    q->eles[q->rear] = value;
}

int dequeue(queue_t *q) {
    if (is_empty(q)) {
        printf("Queue is empty!\n");
return -1;
    }
    int value = q->eles[q->front];
    q->eles[q->front] = -1;  // clear
slot
    q->front++;
    if (q->front > q->rear) {
        q->front = q->rear = -1;  //
queue became empty
    }
    return value;
}

int peek_front(queue_t *q) {
    if (is_empty(q)) return -1;
    return q->eles[q->front];
}

void traverse(queue_t *q) {
    if (is_empty(q)) { printf("Queue empty\n"); return; }
printf("Queue (front to rear): ");
    for (int i = q->front; i <= q->rear; i++) {
printf("%d ", q->eles[i]);
    }
    printf("\n");
}

int main() {
    queue_t q;
    init_queue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    traverse(&q);                        // 10 20 30
    printf("Front: %d\n", peek_front(&q)); // 10
    printf("Dequeued: %d\n", dequeue(&q)); // 10
    traverse(&q);                        // 20 30
    return 0;
}

Circular Queue

Why Circular Queue?

Problem with linear queue: When items are dequeued, front moves forward but rear cannot wrap around.
Space before front is wasted even though it's free.

After several enqueue/dequeue operations:
[---][---][20][30][40]
        ↑           ↑
      front        rear

Free space at start cannot be used!

Solution: Circular Queue — rear wraps around to beginning.

  +------+------+------+------+------+
  |  20  |  30  |  40  |      |      |
  +------+------+------+------+------+
  0      1      2      3      4

Next enqueue goes to index 3, 4, then wraps to 0...

Circular Queue Conditions

// Queue is FULL when:
if ((p->rear == SIZE - 1 && p->front == 0) ||
    (p->rear + 1 == p->front))

// Queue is EMPTY when:
if (p->rear == -1)

Circular Queue in C

typedef struct {
    int eles[SIZE];
    int front;
    int rear;
} cqueue_t;

void enqueue(cqueue_t *q, int value) {
    int next_rear = (q->rear + 1) % SIZE;  // wrap
around
    if (next_rear == q->front) {
        printf("Queue Full!\n");
        return;
}
    if (q->rear == -1) q->front = 0;   // first element
    q->rear = next_rear;
q->eles[q->rear] = value;
}

int dequeue(cqueue_t *q) {
    if (q->rear == -1) {
        printf("Queue Empty!\n");
        return -1;
    }
    int value = q->eles[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;   // became empty
    } else {
        q->front = (q->front + 1) % SIZE;  // wrap around
    }
    return value;
}