队列的基本概念

队列的定义

队列（Queue）简称队，是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。其操作的特性是先进先出（First In First Out，FIFO）。

队头（Front）。允许删除的一端，又称队首。

队尾（Rear）。允许插入的一端。

空队列。不含任何元素的空表。

队列常见的基本操作

InitQueue(&Q)：初始化队列，构造一个空队列Q。
QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
EnQueue(&Q, x)：入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q, &x)：出队，若队列Q非空，删除队头元素，并用x返回。
GetHead(Q, &x)：读队头元素，若队列Q非空，则将队头元素赋值给x。

队列的顺序存储结构

队列的顺序存储

队列的顺序存储附设两个指针：队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置（不同教材、不同题目可能对 front 和 rear 的定义不同，会导致操作的具体实现有区别，注意区分）。

队列的顺序存储类型可描述为

#define MaxSize 50          // 定义队列中元素的最大个数
typedef struct {
    ElemType data[MaxSize]; // 存放队列元素
    int front;              // 队头指针
    int rear;               // 队尾指针
} SqQueue;

初始条件（队空条件）：Q.front == Q.rear == 0。

进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。

出队操作：队不空时，先取队头元素值，再将队头指针加1。

队列的顺序存储的缺点是可能会出现“上溢出”，但这种溢出并不是真正的溢出，在 data 数组中依然存在可以存放元素的空位置，所以是一种“假溢出”。

循环队列

将顺序队列臆造为一个环状的空间，即把存储队列的元素的表从逻辑上视为一个环，称为循环队列。当队首指针 Q.front = MaxSize - 1 后，再前进一个位置就自动到 0，这可以利用除法取余运算（%）来实现。

初始时：Q.front = Q.rear = 0。

队首指针进1：Q.front = (Q.front + 1) % MaxSize。

队尾指针进1：Q.rear = (Q.rear + 1) % MaxSize。

队列长度：(Q.rear + MaxSize - Q.front) % MaxSize。

出队入队时：指针都按顺时针方向进1。

为了区分队空还是队满的情况，有三种处理方式：

牺牲一个单元来区分队空还是队满，入队时少用一个队列单元，这是一种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”。

队满条件：(Q.rear + 1) % MaxSize == Q.front。

队空条件仍为：Q.front == Q.rear。

队列中元素的个数：(Q.rear - Q.front + MaxSize) % MaxSize。
类型中增设表示元素个数的数据成员。这样，队空的条件为 Q.size == 0；队满的条件为 Q.size == MaxSize。这两种情况都有 Q.front == Q.rear。
类型中增设 tag 数据成员，以区分是队满还是队空。tag 等于 0 时，若因删除导致 Q.front == Q.rear，则为队空；tag 等于 1 时，若因插入导致 Q.front == Q.rear，则为队满。

循环队列的操作

基于上述第一种处理方式区分队空还是队满，不另设 size 或 tag 数据成员。

初始化

1
2
3

void InitQueue(SqQueue &Q) {
    Q.rear = Q.front = 0; // 初始化队尾、队首指针
}

判队空

bool isEmpty(SqQueue Q) {
    if (Q.rear == Q.front) // 队空条件
        return true;
    else
        return false;
}

入队

bool EnQueue(SqQueue &Q, ElemType x) {
    if ((Q.rear + 1) % MaxSize == Q.front) // 队满报错
        return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;       // 队尾指针加1取模
    return true;
}

出队

bool DeQueue(SqQueue &Q, ElemType &x) {
    if (Q.rear == Q.front)             // 队空报错
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize; // 队首指针加1取模
    return true;
}

队列的链式存储结构

队列的链式存储

链队列实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点（注意与顺序存储的不同）。

队列的链式存储类型可描述为

typedef struct {            // 链式队列结点
    ElemType data;
    struct LinkNode *next;
} LinkNode;
typedef struct {            // 链式队列
    LinkNode *front, *rear; // 队列的队头和队尾指针
} LinkQueue;

通常将链式队列设计成一个带头结点的单链表，这样可以统一插入和删除操作。

用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。

链式队列的基本操作

基于上述说明，设计为带头结点的单链表

初始化

void InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode)); // 建立头结点
    Q.front->next = NULL; //初始为空
}

判队空

bool isEmpty(LinkQueue Q) {
    if (Q.front == Q.rear)
        return true;
    else
        return false;
}

入队

bool EnQueue(LinkQueue &Q, ElemType x) {
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL; // 以上为创建新结点，插入到链尾
    Q.rear->next = s;
    Q.rear = s;
}

出队

bool DeQueue(LinkQueue &Q, ElemType &x) {
    if (Q.front == Q.rear)       // 空队
        return false;
    LinkNode *p = Q.front->next; // 要删除的结点
    x = p->data;
    Q.front->next = p->next;     // 修改队头指针的位置
    if (Q.rear == p)             // 若原队列中只有一个结点，删除后变空
        Q.rear = Q.front;
    free(p);                     // 释放删除的结点的空间
    return true;
}

王理庚的博客

数据结构-队列