数据结构笔记06

队列(数组模型)

系列文章

队列的概念

类似于栈，队列(queue)也是一个表。然而，队列的插入操作在一端进行，而删除操作在另一端进行。

队列的基本操作是入队(enqueue)和出队(dequeue)。入队是在表的末端，即队尾(rear)插入一个元素；而出队则删除表的第一个元素，即队首(front)元素。

下图展示了一个队列的模型：

下图表示了一个处于中间状态的队列：

队列中的空白元素有着不确定的值，特别地，前面的空白元素曾经属于该队列。

这种实现的问题在于当多次入队后 rear 达到了队尾，那么下一次入队就会发生队列溢出。并且在入队与出队的过程中，front 和 rear 不断后移，造成队列空间不断被压缩。

简单的解决方法是，只要 front 或 rear 到达数组尾端，它就绕回开头，形成循环数组(circular array)结构。如果 front 或 rear 增 1 使得超越了数组，那么其值重置为数组的第一个位置。

实现绕回并不需要多少附加代码，不过它会使开销变大。在保证入队的次数不会大于队列长度的情况下，没必要使用回绕。

关于队列的循环实现，要注意：

  1. 检测队列为空非常重要，否则对空队列的 dequeue 将返回一个随机值
  2. 队首和队尾可能有多种表示方法，例如当队列为空时，队首和队尾可能在同一个单元，也可能在后一个单元，这两种情况下队列的长度计算方式不同

在保证 enqueue 的次数不会大于队列的大小时，没必要使用回绕的方式。

队列的实现

对于每一个队列结构，保留一个数组 queue[] 和位置 front 和 rear ，它们代表队列的两端。还要一个成员 size 来记录实际存在队列中的元素个数。因此，队列的结构定义为：

typedef struct queue_t {
    int capacity;
    int front;
    int rear;
    int size;    // actual size
    int* body;
} queue;

通过队列的类型声明，测试一个队列为空的方法是很容易的：

int isempty(queue* q) {
    return q->size == 0;
}

可以用类似的方法来测试队列是否已满：

/* return true if queue is full */
int isfull(queue* q) {
    return q->size == q->capacity;
}

在循环队列的实现下，为了清空队列，只需要将位置 front 和 rear ，以及队列大小改为合适的值即可，并不需要对队列中的元素作任何改动：

/* clear a queue */
void clear(queue* q) {
    q->size = 0;
    q->front = 0;
    q->rear = 1;
}

入队和出队

在循环队列的实现下，首先需要编写实现回绕功能的函数：

/* if front or rear reaches the end, go back to beginning */
static int succ(int value, queue* q) {
    if (++value == q->size)
        value = 0;
    return value;
}

根据以上对队列的介绍，入队和出队的操作分为为：

void enqueue(int elem, queue* q) {
    if (isfull(q)) {
        /* queue full */
        return;
    }
    else {
        q->size++;
        q->rear = succ(q->rear, q);
        q->body[q->rear] = elem;
    }
}
int deque(queue* q) {
    int elem;
    if (isempty(q)) {
        /* queue empty */
        return 0;  // return to avoid warning
    }
    else {
        q->size--;
        elem = q->body[q->front];
        q->front = succ(q->front, q);
        return elem;
    }
}