第11章队列的定义与顺序实现

课程目录第11章队列的定义与顺序实现

队列的定义与顺序实现：从排队说起

大家好，我是你们的嵌入式系统讲师。今天我们来聊聊队列——这个在嵌入式开发中几乎天天打交道的结构。

队列是什么？说白了，就是排队。你去银行办业务，先来的人先办，后来的人后办。这就是队列的核心思想：先进先出（FIFO）。

我记得刚入行那会儿，有个老工程师跟我说：「小伙子，搞嵌入式，队列搞不明白，你连串口数据都收不利索。」当时我不信，后来真吃了亏——一次项目里，串口接收缓冲区没用好，数据全乱套了。从那以后，我对队列就格外上心。

队列的概念与特性

队列是一种操作受限的线性表。它只允许在一端插入（叫队尾），在另一端删除（叫队头）。

你想想看，生活中哪些场景是队列？

食堂打饭——先排队的先打到饭
打印机任务——先提交的先打印
串口数据接收——先到的字节先被处理

队列的两个基本操作：

入队（Enqueue）：在队尾添加一个元素
出队（Dequeue）：从队头移除一个元素

核心特性：FIFO（First In First Out）

最先进入队列的元素，最先被移出队列。这个特性决定了队列在数据缓冲、任务调度等场景中的广泛应用。

队列的抽象数据类型

作为一个C语言开发者，我们得把队列抽象成数据结构。我个人习惯这样定义：

// 队列的抽象数据类型定义
typedef struct {
    int *data;      // 存储元素的数组
    int front;      // 队头指针
    int rear;       // 队尾指针
    int capacity;   // 队列容量
} Queue;

这里有几个关键点：

data：指向一块连续内存，用来存数据
front：指向队头元素的位置
rear：指向队尾元素的下一个位置（这个约定很重要）
capacity：队列最多能存多少个元素

队列的基本操作接口：

// 初始化队列
Queue* queue_create(int capacity);

// 销毁队列
void queue_destroy(Queue *q);

// 判断队列是否为空
int queue_is_empty(Queue *q);

// 判断队列是否已满
int queue_is_full(Queue *q);

// 入队
int queue_enqueue(Queue *q, int value);

// 出队
int queue_dequeue(Queue *q, int *value);

// 获取队头元素
int queue_peek(Queue *q, int *value);

// 获取队列当前元素个数
int queue_size(Queue *q);

我的经验之谈：在嵌入式系统中，我通常会把队列的容量设计成2的幂次方（比如16、32、64）。这样可以用位运算代替取模运算，效率更高。不过这是后话了，今天我们先打好基础。

顺序队列的实现与假溢出问题

顺序队列就是用数组来实现的队列。听起来简单，但有个坑——假溢出。

先看一个简单的顺序队列实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define QUEUE_SIZE 5

typedef struct {
    int data[QUEUE_SIZE];
    int front;
    int rear;
} SeqQueue;

// 初始化
void init_queue(SeqQueue *q) {
    q->front = 0;
    q->rear = 0;
}

// 判断是否为空
bool is_empty(SeqQueue *q) {
    return q->front == q->rear;
}

// 判断是否已满
bool is_full(SeqQueue *q) {
    return q->rear == QUEUE_SIZE;
}

// 入队
bool enqueue(SeqQueue *q, int value) {
    if (is_full(q)) {
        printf("队列已满，无法入队\n");
        return false;
    }
    q->data[q->rear] = value;
    q->rear++;
    return true;
}

// 出队
bool dequeue(SeqQueue *q, int *value) {
    if (is_empty(q)) {
        printf("队列为空，无法出队\n");
        return false;
    }
    *value = q->data[q->front];
    q->front++;
    return true;
}

这段代码看起来没问题，对吧？但实际运行一下，你就会发现问题。

假设队列容量是5，我们做以下操作：

入队A、B、C、D、E —— 队列满了，rear指向5
出队A、B、C —— front指向3，rear还是5
现在想入队F —— 判断队列已满，但实际上前面3个位置是空的！

这就是假溢出问题。

注意：假溢出不是队列真的满了，而是rear指针走到了数组末尾，无法再插入新元素。但数组前面还有空闲位置。这就像排队时，前面的人走了，但新来的人却只能排在最后面——显然不合理。

为什么会这样？因为我们的front和rear指针只增不减。出队时front往后移，但前面的空间就浪费了。随着操作次数增加，rear迟早会撞到数组边界。

我曾经在一个数据采集项目中遇到过这个问题。当时用顺序队列缓存传感器数据，跑了一整天后，队列突然报满，但实际只存了不到一半的数据。排查了半天才发现是假溢出。嗯，从那以后，我对这个问题就特别敏感。

解决假溢出的思路

解决假溢出，常见有两种方案：

方案一：元素搬移

每次出队后，把后面的元素往前移动。但这样时间复杂度是O(n)，效率太低。在嵌入式系统中，尤其是实时性要求高的场景，这招基本不能用。

方案二：循环队列

把数组首尾相连，形成一个环。当rear到达数组末尾时，如果数组前面有空位，就绕回到开头。这是最常用的方案，也是下一节的重点内容。

循环队列的核心思想：

用取模运算实现指针的循环移动：rear = (rear + 1) % capacity
判空条件：front == rear
判满条件：(rear + 1) % capacity == front（牺牲一个元素空间来区分空和满）

这里我画了一张图，帮你理解顺序队列和假溢出的关系：

假溢出的本质

假溢出的本质是什么？说白了，就是线性数组的「一次性」使用问题。

数组是线性的，从0到N-1。front和rear只能往后移动，不能回头。这就导致了一个矛盾：

从逻辑上看，队列前面有空位
从物理上看，rear已经到数组边界了

解决这个矛盾，就是把数组「掰弯」，让首尾相连。这就是循环队列的由来。

避坑指南：我曾经在一个项目中，用顺序队列做串口数据缓冲。测试时数据量小，一切正常。量产之后，用户反馈设备运行几小时后会死机。查了三天，发现是假溢出导致数据丢失，进而引发协议解析错误。从那以后，我只要用顺序队列，一定会考虑假溢出的问题。

小结

今天我们聊了队列的基本概念和顺序实现。核心要点：

队列是FIFO结构，入队在队尾，出队在队头
顺序队列用数组实现，front和rear指针管理
假溢出是顺序队列的固有缺陷——rear到边界但前面有空位
解决方案：循环队列（下一节详细讲）

队列在嵌入式系统中太常见了。串口数据缓冲、按键事件处理、任务调度……几乎每个项目都会用到。把队列搞明白，你的嵌入式开发之路会顺畅很多。

下一节，我们来解决假溢出问题——循环队列的实现。到时候我会分享一个我实际项目中用过的循环队列代码，保证实用。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录

队列的定义与顺序实现：从排队说起

队列的概念与特性

队列的抽象数据类型

顺序队列的实现与假溢出问题

解决假溢出的思路

假溢出的本质

小结