作者：解学武

顺序队列指的是用顺序表模拟实现的队列存储结构。

我们知道，队列具有以下两个特点：

1. 数据从队列的一端进，从另一端出；
2. 数据的入队和出队遵循"先进先出"的原则；

在顺序表的基础上，只要元素进出的过程遵循以上两个规则，就能实现队列结构。

顺序队列的具体实现

通常情况下，我们采用 C 语言中的数组实现顺序表。既然用顺序表模拟实现队列，必然要先定义一个足够大的数组。不仅如此，为了遵守队列中数据从 "队尾进，队头出" 且 "先进先出" 的规则，还需要定义两个变量（top 和 rear）分别记录队头和队尾的具体位置，如图 1 所示：
初始状态下，顺序队列中没有任何元素，因此 top 和 rear 重合，都位于 a[0] 处。

实现入队

在图 1 的基础上，当有新元素入队时，依次执行以下两步操作：

1. 将新元素存储在 rear 记录的位置；
2. 更新 rear 的值（rear+1），记录下一个空闲空间的位置，为下一个新元素入队做好准备。

例如，在图 1 基础上将 {1,2,3,4} 用顺序队列存储的实现操作如图 2 所示：
入队操作的 C 语言实现代码如下：

int enQueue(int* a, int rear, int data) {
    //如果 rear 超出数组下标范围，队列将无法继续添加元素
    if (rear == MAX_LEN) {
        printf("队列已满，添加元素失败\n");
        return rear;
    }
    a[rear] = data;
    rear++;
    return rear;
}

实现出队

当有元素出队时，根据“先进先出”的原则，目标元素以及在它之前入队的元素要依次从队头出队。

出队操作的实现方法很简单，就是更新 top 的值（top+1）。例如，在图 2 基础上，顺序队列中元素逐个队列的过程如图 3 所示：

注意，虽然数组中仍保存着 1、2、3、4 这些元素，但队列中的元素是依靠 top 和 rear 来判别的，因此图 3b) 显示的队列中确实不存在任何元素。

出队操作的 C 语言实现代码为：

int deQueue(int* a, int top, int rear) {
    //如果 top==rear，表示队列为空
    if (top== rear) {
        printf("队列已空，出队执行失败\n");
        return top;
    }
    printf("出队元素：%d\n", a[top]);
    top++;
    return top;
}

顺序队列的完整实现代码

使用顺序表模拟实现顺序队列的 C 语言代码为：

#include <stdio.h>
#define MAX_LEN 100 //规定数组的长度
//实现入队操作
int enQueue(int* a, int rear, int data) {
    //如果 rear 超出数组下标范围，队列将无法继续添加元素
    if (rear == MAX_LEN) {
        printf("队列已满，添加元素失败\n");
        return rear;
    }
    a[rear] = data;
    rear++;
    return rear;
}
//实现出队操作
int deQueue(int* a, int top, int rear) {
    //如果 top==rear，表示队列为空
    if (top == rear) {
        printf("队列已空，出队执行失败\n");
        return top;
    }
    printf("出队元素：%d\n", a[top]);
    top++;
    return top;
}
int main() {
    int a[MAX_LEN];
    int top, rear;
    //设置队头指针和队尾指针，当队列中没有元素时，队头和队尾指向同一块地址
    top = rear = 0;
    //入队
    rear = enQueue(a, rear, 1);
    rear = enQueue(a, rear, 2);
    rear = enQueue(a, rear, 3);
    rear = enQueue(a, rear, 4);
    //出队
    top = deQueue(a, top, rear);
    top = deQueue(a, top, rear);
    top = deQueue(a, top, rear);
    top = deQueue(a, top, rear);
    top = deQueue(a, top, rear);
    return 0;
}

程序输出结果：

出队元素：1
出队元素：2
出队元素：3
出队元素：4
队列已空，出队执行失败

顺序队列的缺陷

图 2b) 是所有数据入队成功的示意图，图 3b) 是所有数据出队后的示意图，对比两张图会发现，top 和 rear 重合位置变成了  a[4] 而不再是 a[0]。

也就是说，在元素不断入队、出队的过程中，顺序队列会整体向顺序表的尾部移动。整个实现方案存在的缺陷是：

• 顺序队列前面的空闲空间无法再被使用，会造成空间浪费；
• 当顺序队列移动至顺序表尾部时，即便顺序表中有空闲空间，新元素也无法成功入队，我们习惯将这种现象称为“假溢出”。

下篇文章，我会教大家顺序队列的另一种实现方案，可以彻底弥补以上两个缺陷。

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。