1. 队列的定义#

队列(Queue)简称队，也是一种操作受限的线性表，仅允许在表的一端进行插入，而在另一端进行删除。向队列中插入元素称为入队(或进队)，删除元素称为出队(或离队)。这一规则符合日常排队“先到先服务”的原则，因此队列的操作特性为先进先出(First In First Out，FIFO)。

• 队头(Front)：允许删除的一端，也称队首。
• 队尾(Rear)：允许插入的一端。
• 空队列：不含任何元素的队列。

2. 队列常见的基本操作#

• InitQueue(&Q)：初始化队列，构造一个空队列Q。
• QueueEmpty(Q)：判队列空；若队列Q为空，返回true，否则返回false。
• EnQueue(&Q,x)：入队操作；若队列Q未满，将x加入队尾。
• DeQueue(&Q, &x)：出队操作；若队列Q非空，删除队首元素，并通过x返回其值。
• GetHead(Q, &x)：读队首元素但不出队；若队列Q非空，将队首元素赋值给x。

需要注意的是，栈和队列均为操作受限的线性表，因此并非所有线性表的操作都适用于它们。例如，不允许直接访问或修改栈或队列中间的元素，这是由其逻辑特性所决定的。

1. 队列的顺序存储#

队列的顺序实现是指分配一块连续的存储单元存放队列元素，并附设两个指针：队首指针front指向队首元素，队尾指针rear指向队尾元素的下一个位置。不同教材对front和rear指针含义的约定可能不同(例如，rear可能指向队尾元素或其下一位置)，这会导致入队和出队操作的具体实现不同。本节后附有相关习题，建议读者结合练习深入理解。

队列的顺序存储类型可定义为

1
#define MaxSize 50          //定义队列中元素的最大个数
2
typedef struct{
3
    ElemType data[MaxSize]; //用数组存放队列元素
4
    int front, rear;        //队首指针和队尾指针
5
} SqQueue;

初始状态：Q.front=Q.rear=0。

入队操作：当队列未满时，先将元素存入队尾，再将队尾指针加1。

出队操作：当队列非空时，先取出队首元素，再将队首指针加1。

初始时空队列满足 Q.front == Q.rear == 0，该条件可作为判空依据。

然而，能否以Q.rear==MaxSize作为队满条件呢？显然不能。队列中仅剩一个元素，但rear已达MaxSize，若此时继续入队，则会出现“上溢”。但这种溢出并非真正溢出，实际上数组中仍有空闲单元，因此称此现象为假溢出。

2. 循环队列#

为了解决顺序队列的假溢出问题，引入循环队列：将顺序存储空间在逻辑上组织为环状结构。当指针到达数组末尾时，自动回到起始位置，这可通过取模运算(%)实现。

初始状态：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。

出入队操作：指针均按顺时针方向移动。

那么，循环队列判空和判满的条件是什么呢？队空条件显然为 $Q.front == Q.rear$。但当入队速度远快于出队时，rear 会追上 front，此时同样满足 $Q.front == Q.rear$，却表示队满。因此，仅凭 $front == rear$ 无法区分队空与队满。

为解决这一问题，常用以下三种方法：

1. 牺牲一个存储单元：入队时少用一个存储单元，这是一种较为普遍的做法，约定以“队尾指针的下一位置为队首”作为队满标志。

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

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

   队列中元素个数：(Q.rear-Q.front+MaxSize)%MaxSize。

2. 增设 size 成员: 记录当前元素个数。若入队成功, 则 size++, 若出队成功, 则 size—。

   队空条件: Q.size==0。

   队满条件：Q.size==MaxSize。

   两种情形均有 Q.front == Q.rear，由 size 区分队空与队满。

3. 增设 tag 标志位：

   出队后置 tag=0，若此时 Q.front==Q.rear，则为队空。

   入队后置 tag=1，若此时 Q.front==Q.rear，则为队满。

3. 循环队列的操作(基于牺牲一个单元法)#

(1) 初始化

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

(2) 判队空

1
bool QueueEmpty(SqQueue Q) {
2
    if (Q.rear==Q.front)    //队空条件
3
        return true;
4
    else
5
        return false;
6
}

(3) 入队

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

(4) 出队

1
bool DeQueue(SqQueue &Q, ElemType &x) {
2
    if (Q.rear==Q.front)                //队空则报错
3
        return false;
4
    x=Q.data[Q.front];
5

6
Q.front=(Q.front+1) %MaxSize;           //队首指针加1取模
7
return true;
8
}

1. 队列的链式存储#

队列的链式表示称为链式队列，本质上是一个同时带有队首指针和队尾指针的单链表。队首指针指向队头结点，队尾指针指向队尾结点，即单链表的最后一个结点。

链式队列的类型可定义为

1
typedef struct LinkNode{    //链式队列结点
2
    ElemType data;
3
    struct LinkNode *next;
4
} LinkNode;
5
typedef struct{             //链式队列
6
    LinkNode *front, *rear; //队列的队头和队尾指针
7
} LinkQueue;

当不带头结点时，若 Q.front == NULL 且 Q.rear == NULL，则链式队列为空队列。

入队操作：创建一个新结点，将其插入链表尾部，并令Q.rear指向该结点；若原队列为空，则同时令Q.front也指向该结点。

出队操作：先判断队列是否为空；若非空，则取出队首元素，删除对应结点，并令Q.front指向下一个结点；若被删结点是最后一个元素，则将Q.front和Q.rear均置为NULL。

不难发现，不带头结点的链式队列在边界处理上较为烦琐。因此，通常将链式队列设计为带头结点的单链表，从而使插入与删除操作逻辑统一。

链式队列特别适用于元素数量频繁变化的场景，且不存在队满或溢出问题。此外，若程序中需使用多个队列(如同多个栈的情形)，优先选用链式队列可避免存储分配不合理或溢出等问题。

2. 链式队列的基本操作#

(1) 初始化

1
void InitQueue(LinkQueue &Q){ //初始化带头结点的链式队列
2
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); //建立头结点
3
    Q.front->next=NULL; //初始为空
4
}

(2) 判队空

1
bool QueueEmpty(LinkQueue Q){
2

3
if (Q.front==Q.rear) //判空条件
4
    return true;
5
else
6
    return false;
7
}

(3) 入队

1
void EnQueue(LinkQueue &Q,ElemType x) {
2
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode)); //创建新结点
3
    s->data=x;
4
    s->next=NULL;
5
    Q.rear->next=s; //插入链尾
6
    Q.rear=s; //修改尾指针
7
}

(4) 出队

1
bool DeQueue(LinkQueue &Q,ElemType &x) {
2
    if (Q.front==Q.rear)
3
        return false; //空队
4
    LinkNode *p=Q.front->next;
5
    x=p->data;
6
    Q.front->next=p->next;
7
    if (Q.rear==p)
8
        Q.rear=Q.front; //若原队列中只有一个结点，删除后变空
9
    free(p);
10
    return true;
11
}