Queues

Queue

A queue is an operation-restricted linear data structure. Unlike the first-in, last-out behavior of a stack, queue elements follow first in, first out (FIFO).

The exit end is called the front, and the entrance end is called the rear. A queue allows enqueue only at the rear and dequeue only at the front.

Like a stack, a queue can be implemented with an array or a linked list. In an array implementation, the rear position is defined as the position after the last enqueued element to simplify enqueue.

Enqueue

Enqueue places a new element into the queue, only at the rear. The position after the new element becomes the new rear. Enqueue has time complexity $O(1)$.

Dequeue

Dequeue removes an element from the queue, only from the front. The element after the removed element becomes the new front. Dequeue has time complexity $O(1)$.

Circular Queue

If dequeue continues in a simple array queue, the space to the left of front becomes unusable and the available capacity keeps shrinking.

An array queue can retain constant capacity by using a circular queue. To use space fully and overcome false overflow without growing the array, imagine the array as a ring whose ends meet. Space left by dequeued elements can be reused when rear wraps back to the beginning.

In physical storage, rear may therefore appear before front. A new element can enter at the beginning of the array and rear continues moving. Front and rear chase each other as enqueue and dequeue proceed.

If rear catches front the queue is full; if front catches rear the queue is empty. The array is not physically bent. Modulo arithmetic keeps both pointers within its bounds and creates the logical ring.

For an array of maximum capacity MAX:

• Move rear after enqueue: (rear + 1) % MAX
• Move front after dequeue: (front + 1) % MAX
• Queue full: (rear + 1) % MAX == front
• Queue empty: front == rear

The position addressed by rear is always reserved, so the maximum queue capacity is one less than the array length.

bool queue_enqueue(queue_t *queue, T elem) {
    int next_rear = (queue->rear + 1) % MAX;
    if (next_rear == queue->front) {
        return false;
    }
    queue->data[queue->rear] = elem;
    queue->rear = next_rear;
    return true;
}

bool queue_dequeue(queue_t *queue, T *elem) {
    if (queue->front == queue->rear) {
        return false;
    }
    *elem = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAX;
    return true;
}