数据结构--队列

本文写于 2020 年 3 月 21 日，2022 年 3 月 6 日重新整理

写在前面

队列 (Queue) 也是线性表中的一种重要数据结构，队列中的元素只能在队列的头部 (front) 出队 (delete) ，只能在队列的尾部 (rear) 入队 (add) 。因此它是一种先入先出 (First In First Out) 的数据结构。

定义

操作集

一个队列应有以下操作：

Queue *createQueue();                     //生成队列
int isFull(Queue *queue);                 //查询队列是否为满队列
void add(Queue *queue, ElementType item); //入队
int isEmpty(Queue *queue);                //查询队列是否为空
ElementType delete (Queue *queue);        //出队

实现

链式结构

链式结构的队列由两个节点域组成，它们分别是 front 和 rear 节点，指向链表头和链表尾。

0. 原型

typedef struct queueNode
{
    ElementType data;
    QueueNode *next;
} QueueNode;

typedef struct queue_list_based
{
    QueueNode *front;   //指向头节点
    QueueNode *rear;    //指向尾节点
} Queue;

1. 生成空队列

生成一个 Queue 结构体，并把它的 front 和 rear 节点赋值为 NULL 。

Queue *createQueue()
{
    Queue *queue = (Queue *)malloc(sizeof(Queue));
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

2. 查询是否为满队列

链式实现的队列不存在满队列

3. 查询是否为空队列

当且仅当链式实现的队列为空队列时，它的头节点 front 为 NULL 。

int isEmpty(Queue *queue)
{
    return queue->front == NULL;
}

4. 入队

入队时，若队列不为空把尾节点的 next 节点赋值为要入队的节点，然后把尾节点移动到新插入的节点，否则，把头节点赋值为新插入的节点。

void add(Queue *queue, ElementType item)
{
    QueueNode *node = (QueueNode *)malloc(sizeof(QueueNode));
    node->data = item;
    node->next = NULL;
    if (isEmpty(queue))
    {
        queue->front = node;
        queue->rear = node;
    }
    else
    {
        queue->rear->next = node;
        queue->rear = node;
    }
}

5. 出队

出队时，若队列不为空，先把头节点保存下来，然后把头节点后移，最后删除并返回原头节点。

ElementType delete (Queue *queue)
{
    if (isEmpty(queue))
    {
        return NULL; //Error!queue is Empty
    }
    QueueNode *frontNode = queue->front;
    if (queue->front == queue->rear)
    { //if queue has just one element,make it empty.
        queue->front = NULL;
        queue->rear = NULL;
    }
    else
    {
        queue->front = queue->front->next;
    }
    ElementType frontNodeValue = frontNode->data;
    free(frontNode);
    return frontNodeValue;
}

顺序结构

0. 原型

顺序结构的队列使用一个数组存放数据，它的内部维护两个整形变量 front 和 rear 分别指示队列头部和尾部节点的位置。

由于队列的入队和出队的操作将改变队列元素在内部数组中的起始和终止位置，因此顺序结构的队列常常是一个循环队列，即内部数组循环使用，数组下标对数组长度取模，这样可以提高空间的利用效率。

容易知道，当队列的 front 和 rear 值相同时，队列是空的，同时，当队列处于满的状态时， front 和 rear 也是相同的，这种情况将使我们无法分辨队列的满空状态。

这种情况的出现是必然的，比如对于一个长度为 10 的队列，它的内部可以有 0,1,2,3...10 个元素，即 11 个状态，我们使用头尾差值即 front - rear 的值表征这 11 中状态。然而 front - rear 只有 10 种可能的结果，无法表征 11 种状态。

这种矛盾的解决方案十分简单，我们可以在队列的内部增加一个 counter 计数器来记录队列内部的元素个数。或者我们可以让头节点 front 指向队列中第一个元素的前一位置，这样，队列内部实际只能储存数组长度减一个元素，头尾节点便不会因为队列满而相遇了。

typedef struct queue_array_based
{
    ElementType *data;
    int front;
    int rear;
}Queue;

1. 生成队列

生成最大长度为 maxSize - 1 的队列，并把 front,rear 赋值为 0 ，标志为空队列。

Queue *createQueue(const int maxSize)
{
    Queue *queue = (Queue *)malloc(sizeof(Queue));
    queue->data = (ElementType *)malloc(maxSize * sizeof(ElementType));
    queue->front = 0;
    queue->rear = 0;
    return queue;
}

2. 查询队列是否为满队列

当且仅当队列满时， rear 和 front 必定是相邻位置，且 rear 在 front 后面，因此，通过判断 front + 1 与数组长度的余与 rear 比较，可以获知队列是否已满。

int isFull(Queue *queue, const int maxSize)
{
    return ((queue->front + 1) % maxSize) == (queue->rear);
}

3. 查询队列是否为空

当且仅当队列空时， front 和 rear 的值相等。

int isEmpty(Queue *queue)
{
    return queue->front == queue->rear;
}

4. 入队

入队时，若队列未满， rear 的值变为 rear + 1 对数组长度的取余，然后把入对的元素放在 rear 的位置。

void add(Queue *queue, ElementType item, const int maxSize)
{
    if (isFull(queue, maxSize))
    {
        return; //Error!queue is Full.
    }
    queue->rear = (queue->rear + 1) % maxSize;
    queue->data[queue->rear] = item;
}

5. 出队

出队时，若队列非空，将 front 移到 front + 1 对数组长度取余的位置，然后返回 front 位置的元素。

ElementType delete (Queue *queue, const int maxSize)
{
    if (isEmpty(queue))
    {
        return NULL; //Error!queue is Empty.
    }
    queue->front = (queue->front + 1) % maxSize;
    return queue->data[queue->front];
}