队列

队列（Queue）

队列是一种运算受限的线性数据结构，不同于栈的先进后出（FILO），队列中的元素只能先进先出（FIFO, First In First Out）。

队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）。队列只允许在队尾进行入队（enqueue），在队头进行出队（dequeue）。

与栈类似，队列既可以用数组来实现，也可以用链表来实现。其中用数组实现时，为了入队操作的方便，把队尾位置规定为最后入队元素的下一个位置。

入列（enqueue）

入队就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾。入队操作的时间复杂度是 $O(1)$。

出队（dequeue）

出队就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将成为新的队头。出队操作的时间复杂度是 $O(1)$。

循环队列（Circular Queue）

如果不断出队，队头左边的空间就失去了作用，那队列的容量就会变得越来越小。

用数组实现的队列可以采用循环队列的方式来维持队列容量的恒定。为充分利用空间，克服假溢出的现象，在数组不做扩容的情况下，将队列想象为一个首尾相接的圆环，可以利用已出队元素留下的空间，让队尾指针重新指回数组的首位。这样一来整个队列的元素就循环起来了。

在物理存储上，队尾的位置也可以在队头之前。当再有元素入队时，将其放入数组的首位，队尾指针继续后移即可。队头和队尾互相追赶，这个追赶的过程就是入队和出队的过程。

如果队尾追上队头说明队列满了，如果队头追上队尾说明队列为空。循环队列并非真正地把数组弯曲，利用求余操作就能使队头和队尾指针不会跑出数组的范围，逻辑上实现了弯曲的效果。

假设数组的最大容量为 MAX：

• 入队时队尾指针后移：(rear + 1) % MAX
• 出队时队头指针后移：(front + 1) % MAX
• 判断队满：(rear + 1) % MAX == front
• 判断队空：front == rear

需要注意的是，队尾指针指向的位置永远空出一位，所以队列最大容量比数组长度小 1。

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;
}