大话数据结构5-队列

队列在我们生活中也很常见，例如客服人员接听电话，会将打电话的人按顺序进行排队，时间上最先打入的最早接听。抽象一下，我们定义数据结构：

队列（queue） 是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

如上面的解释，队列是一种“先进先出（First in First Out（FIFO））”的结构, 允许插入的一端称为队尾，允许删除的一端称为队头。例如队列 $(a_1,a_2,…a_n)$, $a_1$ 就是队头元素，$a_n$ 是队尾元素。

I 循环队列

对于队列而言，顺序存储结构会有些不足，因为“入队”操作很简单（向队尾追加一个元素），但“出队”很麻烦（移走第一个元素，后面所有元素都需要向前移动一位）。

因此，我们在利用顺序结构存储队列时，通常配合上两个指针来进行以提升存储效率。首先是头指针 front 指向队列的首个元素，然后是 rear 指针，指向队列最后一个元素的下一个值。当队列为空时，front 指针与 rear 指针重叠。然后我们定义数组（也就是顺序存储结构）的最后一个元素的下一个元素是数组的第一个元素，从而可以实现队列的循环存储。

此外，为了区分队列为空和队列为满的情况，我们定义数组中仅剩下一个空的元素时队列即为满。由于循环的存储，队列的长度不一定是 rear-front, 我们总结出队列长度计算的一般公式：

$$(rear-front + QueueSize)%QueueSize$$

下面我们看一下循环队列入队和出队的代码：

// 入队列操作
Status EnQueue(SqQueue *Q, QElemType e){
    if(Q->rear + 1)%MAXSIZE == Q-> front)       //判断队列是否已满
        return ERROR;
    Q->data[Q->rear] = e;               //将新元素放在队尾
    Q->rear = (Q->rear + 1) %MAXSIZE;          //队尾指针向后移动一位

    return OK;
}
//出队列操作
Status DeQueue(SqQueue *Q, QElemType *e){
    if(Q->front == Q->rear)     //判断队列是否为空
        return ERROR;
    *e = Q->data[Q->front];         //将头元素赋值给 e
    Q->front = (Q->front + 1)%MAXSIZE;  //front 指向向后移动一个位置

    return OK;
}

Remark：记住循环队列的头尾指针移动时，一定要 %MAXSIZE.

II 队列的链表实现

用链表实现队列时，我们将队头指针（front）指向链队列的头结点，队尾指针（rear）指向链表的最后一个结点。当队列为空时，front 和 rear 指向同一个结点-头结点。

队列的入队和出队操作如下：

//向队列中插入元素
Status EnQueue (LinkQueue *Q, QElemType e){
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if(!s)      //分配存储空间失败
        exit(OVERFLOW);
        
    s->data = e;
    s->next = NULL;
    Q->rear->next = s;  //将 s 放在队列的最后

    Q-rear = s;     //将队列的rear 指针指向s

    return OK;
}

//从队列中删除元素-出队
Status DeQueue(LinkQueue *Q, QElemType *e){
    QueuePtr p;
    if(Q->front == Q->rear)     //判断队列是否为空
        return ERROR;

    p = Q->front->next;     //p中暂存队列的头元素
    *e = p->data;
    Q->front->next = p->next;

    if(Q->rear == p)         //如果删除之后为空，将头尾指针重合
        Q->rear = Q->front;
    free(p);

    return OK;
}

Remark:

1. 需要注意的是 front 指针与头结点重合，所以 front 指针指向的不是第一个元素，Q->front->next 才是第一个元素。