第14章双端队列

课程目录第14章双端队列

双端队列：不止是队列的队列

队列这东西，大家应该都熟悉了——先进先出，一头进一头出。但实际项目中，你会发现很多场景需要更灵活的数据结构。比如任务调度，有时候新来的紧急任务要插队到最前面；又比如撤销操作，既要能撤销最近的，也要能撤销最早的。

这时候，双端队列就派上用场了。说白了，它就是一个可以在两端都能插入和删除的线性表。我当年第一次接触这个概念时，心想这不就是两个栈背靠背吗？后来发现，嗯，还真有点那个意思，但实现起来细节不少。

双端队列的概念

双端队列，英文叫 Deque（Double-Ended Queue）。它允许我们在队列的头部和尾部进行插入和删除操作。你想想看，这比普通队列灵活多了吧？

它的核心操作有这些：

头部插入：在队列最前面加一个元素
头部删除：移除队列最前面的元素
尾部插入：在队列最后面加一个元素
尾部删除：移除队列最后面的元素
查看头部：获取第一个元素但不删除
查看尾部：获取最后一个元素但不删除

我在做嵌入式系统时，经常用双端队列来做命令缓冲区。比如串口接收到的命令，普通命令按顺序处理，但紧急命令（比如急停）就得插队到最前面。用双端队列，这事儿就简单了。

核心要点：双端队列不是两个队列，而是一个队列，只是两端都能操作。它结合了栈和队列的部分特性，但又不是简单的组合。

双端队列的顺序实现

顺序实现，就是用数组来存储数据。这里有个关键点——循环数组。为什么要循环？因为如果只用线性数组，头部插入和删除会导致大量数据移动，效率太低了。

我习惯用两个指针：front 指向头部，rear 指向尾部。注意，这里我通常让 rear 指向最后一个元素的下一个位置，这样判断空和满会比较方便。

先看结构体定义：

#define MAX_DEQUE_SIZE 100

typedef struct {
    int data[MAX_DEQUE_SIZE];
    int front;  // 指向队头元素
    int rear;   // 指向队尾的下一个位置
    int size;   // 当前元素个数，方便判断空满
} SeqDeque;

初始化很简单：

void initSeqDeque(SeqDeque *dq) {
    dq->front = 0;
    dq->rear = 0;
    dq->size = 0;
}

判断空和满：

int isSeqEmpty(SeqDeque *dq) {
    return dq->size == 0;
}

int isSeqFull(SeqDeque *dq) {
    return dq->size == MAX_DEQUE_SIZE;
}

头部插入和尾部插入：

// 头部插入
int insertFront(SeqDeque *dq, int value) {
    if (isSeqFull(dq)) return -1;  // 队列已满
    
    // front 向前移动（循环）
    dq->front = (dq->front - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
    dq->data[dq->front] = value;
    dq->size++;
    return 0;
}

// 尾部插入
int insertRear(SeqDeque *dq, int value) {
    if (isSeqFull(dq)) return -1;
    
    dq->data[dq->rear] = value;
    dq->rear = (dq->rear + 1) % MAX_DEQUE_SIZE;
    dq->size++;
    return 0;
}

头部删除和尾部删除：

// 头部删除
int deleteFront(SeqDeque *dq, int *value) {
    if (isSeqEmpty(dq)) return -1;
    
    *value = dq->data[dq->front];
    dq->front = (dq->front + 1) % MAX_DEQUE_SIZE;
    dq->size--;
    return 0;
}

// 尾部删除
int deleteRear(SeqDeque *dq, int *value) {
    if (isSeqEmpty(dq)) return -1;
    
    dq->rear = (dq->rear - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
    *value = dq->data[dq->rear];
    dq->size--;
    return 0;
}

小技巧：用 size 字段来判断空满，比用 front == rear 更直观。因为 front == rear 既可能是空也可能是满，还得额外处理。我早期写代码时就被这个坑过，后来就改用 size 了。

双端队列的链式实现

链式实现，说白了就是用链表。好处是容量动态扩展，没有固定大小限制。对于嵌入式系统来说，如果内存碎片不是问题，链式实现更灵活。

我一般用双向链表来实现，因为需要在两端快速操作。单向链表在尾部删除时效率太低，得遍历到倒数第二个节点。

先看节点和结构体：

typedef struct DequeNode {
    int data;
    struct DequeNode *prev;
    struct DequeNode *next;
} DequeNode;

typedef struct {
    DequeNode *front;  // 指向头节点
    DequeNode *rear;   // 指向尾节点
    int size;
} LinkedDeque;

初始化：

void initLinkedDeque(LinkedDeque *dq) {
    dq->front = NULL;
    dq->rear = NULL;
    dq->size = 0;
}

头部插入：

int insertFrontLinked(LinkedDeque *dq, int value) {
    DequeNode *node = (DequeNode *)malloc(sizeof(DequeNode));
    if (!node) return -1;  // 内存分配失败
    
    node->data = value;
    node->prev = NULL;
    node->next = dq->front;
    
    if (dq->front) {
        dq->front->prev = node;
    } else {
        dq->rear = node;  // 第一个节点
    }
    dq->front = node;
    dq->size++;
    return 0;
}

尾部插入：

int insertRearLinked(LinkedDeque *dq, int value) {
    DequeNode *node = (DequeNode *)malloc(sizeof(DequeNode));
    if (!node) return -1;
    
    node->data = value;
    node->next = NULL;
    node->prev = dq->rear;
    
    if (dq->rear) {
        dq->rear->next = node;
    } else {
        dq->front = node;  // 第一个节点
    }
    dq->rear = node;
    dq->size++;
    return 0;
}

头部删除和尾部删除：

int deleteFrontLinked(LinkedDeque *dq, int *value) {
    if (!dq->front) return -1;
    
    DequeNode *temp = dq->front;
    *value = temp->data;
    
    dq->front = temp->next;
    if (dq->front) {
        dq->front->prev = NULL;
    } else {
        dq->rear = NULL;  // 删完了
    }
    
    free(temp);
    dq->size--;
    return 0;
}

int deleteRearLinked(LinkedDeque *dq, int *value) {
    if (!dq->rear) return -1;
    
    DequeNode *temp = dq->rear;
    *value = temp->data;
    
    dq->rear = temp->prev;
    if (dq->rear) {
        dq->rear->next = NULL;
    } else {
        dq->front = NULL;  // 删完了
    }
    
    free(temp);
    dq->size--;
    return 0;
}

注意：链式实现一定要处理好边界情况。比如删除最后一个节点时，front 和 rear 都要置 NULL。我曾经在项目中漏掉了这个判断，结果程序跑着跑着就野指针崩溃了，排查了好久才发现。

顺序实现 vs 链式实现

我整理了一个对比表格，方便你根据实际场景选择：

特性	顺序实现	链式实现
内存分配	静态，固定大小	动态，按需分配
访问速度	O(1)，直接索引	O(1)，但指针间接访问
内存碎片	无	可能有
容量限制	有，定义时确定	无，受堆内存限制
实现复杂度	中等，需处理循环	稍高，需管理指针

我个人建议：如果数据量可预估且不大，用顺序实现更稳。如果数据量变化大，或者你不知道最大会有多少，那就用链式实现。

双端队列知识结构图

这张图把双端队列的知识体系梳理清楚了。从核心概念出发，分两条路——顺序实现和链式实现。底部是选择依据，帮你做决策。

我的经验：在嵌入式项目中，我通常优先考虑顺序实现。因为嵌入式系统的内存通常比较紧张，动态分配容易产生碎片，而且一旦内存不足，malloc 返回 NULL 处理起来很麻烦。但如果你在做上层应用，内存充裕，链式实现会更省心。

好了，双端队列的内容就这些。记住，它不是什么高深的东西，就是一个两端都能操作的线性表。但用好了，很多场景下能让你事半功倍。

📚 课程目录

双端队列：不止是队列的队列

双端队列的概念

双端队列的顺序实现

双端队列的链式实现

顺序实现 vs 链式实现

双端队列知识结构图