主要内容 #

1. 顺序队列的基本实现
2. 入队和出队
3. 参考代码

1. 顺序队列的基本实现 #

顺序队列指的是用顺序表模拟实现的队列存储结构。
我们知道，队列具有以下两个特点：

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

在顺序表的基础上，只要元素进出的过程遵循以上两个规则，就能实现队列结构。
通常情况下，我们采用 C 语言中的数组实现顺序表。既然用顺序表模拟实现队列，必然要先定义一个足够大的数组。不仅如此，为了遵守队列中数据从 “队尾进，队头出” 且 “先进先出” 的规则，还需要定义两个变量（top 和 rear）分别记录队头和队尾的具体位置，如下图所示：

初始状态下，顺序队列中没有任何元素，因此 top 和 rear 重合，都位于 a[0] 处。

2. 入队和出队 #

实现入队
当有新元素入队时，依次执行以下两步操作：

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

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

入队操作的 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）。例如，在上图基础上，顺序队列中元素逐个队列的过程如下图所示：

注意，虽然数组中仍保存着 1、2、3、4 这些元素，但队列中的元素是依靠 top 和 rear 来判别的，因此图b) 显示的队列中确实不存在任何元素。
出队操作的 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;
}

3. 完整参考代码 #

#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;
}