- 第 112篇 -
Date: 2025 - 07 - 20
Author: 郑龙浩（仟墨）

队列（Queue）

1 基本介绍

1.1 定义

队列（Queue）是一种先进先出（FIFO, First-In-First-Out）的线性数据结构，只允许在队尾插入（入队）、在队头删除（出队）

1.2 栈 与 队列的区别

• 栈 是只允许一端进行插入或删除的线性表 –> 所以后进先出（在栈顶进行插入删除）
• 队列 是只允许在一端进行插入，在另一端删除的线性表 –> 所以先进先出（在队尾插入，队头删除）
• 先进先出：FIFO（First In First Out)

1.3 重要术语

队头、队尾、空队尾

队头：允许删除的一端

队尾：允许插入的一端

空队尾：没有任何元素的队列

2 基本操作

• 初始化：InitQueue(*Q)
• 清空：ClearQueue(*Q)
• 销毁：DestroyQueue(*Q)
• 入队：EnQueue(*Q, ElemType x)
• 出队：DeQueue(*Q, ElelType* x)
• 读取队头元素：GetHeadQueue(*Q, ElemType* x)
• 判断是否为空：IsEmpty(*Q)
• 判断是否已满：IsFull(Queue *Q)（只有顺序队列有这个）
• 队列长度：QueueLength(Queue *Q)
• 打印：PrintQueue(*Q)

3 顺序队列(循环版本)

两种版本

有好几个版本

注意：只有带size或tag参数的队列结构不需要浪费空间，即浪费最后一个存储单元，不带这俩参数的版本，如果不空出最后一个存储单元，就无法通过 rear == fron 判断出来：是满？是空？

当空出一个存储单元的时候就可以判断出是满还是空了

所以如果不带size或tag参数就必然要浪费一个存储单元，但是从整的结构来说，这样反而节省了空间，因为带了size或者tag的参数，每个节点都会多个变量，所以实际上来说，并没节省。

版本1 - 指向指向队尾元素的下一个位置（即队尾后边）

• 版本1.1 - rear 指向队尾后边 且 结构中无size或tag参数
  • 必须空出最后一个存储单元
  • 初始化时，各参数默认为：
    • front = 0
    • rear = 0
  • 队空条件：front == rear
  • 队满条件：(rar + 1) % MaxSize == front
• 版本1.2 - raer 指向队尾后边 且 结构中有size参数
  • 不需要空出任何存储单元
  • 初始化时，各参数默认为：
    • front = 0
    • rear = 0
    • size = 0
  • 可以直接通过size判断队列的状态
  • 队空条件：size = 0
  • 队满条件：size == MaxSize
• 版本1.3 - rear 指向队尾后边 且 结构中有tag参数
  • 不需要空出任何存储单元
  • 初始化时，各参数默认为：
    • front = 0
    • rear = 0
    • tag= 0（初始化相当于上一次操作出队）
  • 通过tag标记出最后一次操作是入队还是出队（0是出队，1是入队）
  • 队空条件：front == rear && tag == 0（如果上一次操作是出队tag==0，出现front == rear 就是队空）
  • 队满条件：front == rear && tag == 1（如果上一次操作是入队tag==1，出现front == raer 就是队满

版本2 - rear 指向队尾元素

• 版本2.1 - rear 指向队尾 且 结构中无size或tag参数

  • 必须空出最后一个存储单元
  • 初始化时，各参数默认为：
    • front = 0
    • rear = -1
  • 队空条件：(rear + 1) % MaxSize == front
  • 队满条件：(rear + 2) % MaxSize == front

• 版本2.2 - rear 指向队尾 且 结构中有size参数

  • 不需要空出存储单元
  • 初始化时，各参数默认为：
    • front = 0
    • rear = -1
    • size = 0
  • 通过size变量直接判断队列的状态
  • 队空条件：size == 0
  • 队满条件：size == MaxSize

• 版本2.3 - rear 指向队尾 且 结构中有tag参数

  • 不需要空出存储单元

  • 初始化时，各参数默认为：

    • front = 0
    • rear = -1
    • tag= 0（初始化相当于上一次操作出队）

  • 通过tag标记出最后一次操作是出队还是入队（0是出队，1是入队）

  • 队空条件：front == (rear + 1) % MaxSize && tag == 0

  • 队满条件：front == (rear + 1) % MaxSize && tag == 1

两种版本区别

版本1：rear 指向队尾的下一个位置

front 指向队头元素，rear 指向下一个可插入的位置。队列长度计算为 (rear - front + MaxSize) % MaxSize，队空条件是 front == rear，队满条件是 (rear + 1) % MaxSize == front。此版本逻辑清晰，计算简单，是最常用的实现方式。

版本2：rear 指向队尾元素

front 指向队头元素，rear 直接指向队尾元素。队列长度计算为 (rear - front + 1 + MaxSize) % MaxSize，队空条件是 (rear + 1) % MaxSize == front，队满条件是 (rear + 2) % MaxSize == front。此版本需要额外调整计算，容易出错，一般不建议使用。

版本1.1 - rear指向队尾后边 且 无 size 或 tag

• 先进先出 -> 队尾进，队头出

• 队头指针：front 指向队头元素

• 队尾指针：rear 指向队尾元素的后一个位置

• 必须知道：即使是顺序队列，队头指针也不可能一直指向data[0]

  初始化后，如果一直入队操作，队头指针肯定是一直指向0的，但是如果执行了出队操作，那么队头指针会指向1，再执行出队操作，会指向2… –> 现在的front指向2，队头元素是data[2]

  假设此时队尾指针指向的是MaxSize-1，然后进行入队操作，执行完入队以后，队尾指针不会指向MaxSize而是0，

  也就是要将线性的结构转换为一个环形的、循环的结构，方法如下：

  Q->rear = (Q->rear + 1) % MaxSize
  

  也就是当rear指向线性结构的末尾的时候要从头开始

  因为现在的data[0]和data[1]都是空的并且访问data[MaxSize]会越界（因为数组索引是0~MaxSize），所以rear要指向0，如果再入队操作，在data[0]的位置会存储一个值，然后rear指向1，此时仅有一个data[1]还未存储数据

  注意了！！！！

  那么这个位置是否可以存储数据呢？

  答案是否定的， 我们必须牺牲一个元素在队列的末尾，原因如下：

  因为判断队列是否为空以及初始化的时候都是front == rear

  如果真的在执行一次入队操作，队尾元素会是data[1]，而rear指向了2，

  那么此时的front和rear都同时指向2，那么我到底是将这种情况归为满队，还是空队呢，所以为了避免这种情况的发生，统一约定：

  • 队列的最后一个位置要空出来（牺牲一个存储单元）

  • 队列已满的条件：rear下一个位置是front，即

    (Q->rear + 1) % MaxSize == Q->front
    

  • 队列为空的条件：

    Q->front == Q->rear
    

• 使用模运算将线状的存储空间在逻辑上变成了环状

SeqQueue.h

#pragma once
#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"
#define MaxSize 10
typedef int ElemType;
typedef struct {ElemType data[MaxSize]; // 静态数组存放元素int front, rear; // 队头指针 队尾指针
}SeqQueue;// 初始化
void InitQueue(SeqQueue* Q);// 销毁队列
void DestroyQueue(SeqQueue* Q);// 清空队列
void ClearQueue(SeqQueue* Q);// 判断队列是否为空
bool IsEmpty(SeqQueue* Q);// 入队
bool EnQueue(SeqQueue* Q, ElemType x);// 出队
bool DeQueue(SeqQueue* Q, ElemType* x);// 读取队头元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x);// 判断队列是否已满
bool IsFull(SeqQueue* Q);// 队列长度
int QueueLength(SeqQueue* Q);// 打印
void PrintQueue(SeqQueue* Q);

SeqQueue.c

#include "sequence_queue.h"
#include "stdio.h"
#include "stdlib.h"// 初始化
void InitQueue(SeqQueue* Q) {// 队头 == 队尾 且都 指向0Q->rear = Q->front = 0;
}// 销毁队列
void DestroyQueue(SeqQueue* Q) {Q->front = Q->rear = 0;
}// 清空队列
void ClearQueue(SeqQueue* Q) {Q->front = Q->rear = 0;
}// 判断队列是否为空
bool IsEmpty(SeqQueue* Q) {return Q->front == Q->rear;
}// 入队
bool EnQueue(SeqQueue* Q, ElemType x) {if (IsFull(Q)) return false; // 队列已满，不能入队Q->data[Q->rear] = x;Q->rear = (Q->rear + 1) % MaxSize; // 队尾指针要一直保持在 0 ~ MaxSize-1之间return true; // 入队成功
}// 出队
bool DeQueue(SeqQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false; // 空队列不能删除*x = Q->data[Q->front];Q->front = (Q->front + 1) % MaxSize;return true;
}// 读取队头元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false;*x = Q->data[Q->front];return true;
}// 判断队列是否已满
bool IsFull(SeqQueue* Q) {return (Q->rear + 1) % MaxSize == Q->front;
}// 队列长度
int QueueLength(SeqQueue* Q) {return (Q->rear - Q->front + MaxSize) % MaxSize;
}// 打印
void PrintQueue(SeqQueue* Q) {if (IsEmpty(Q)) {printf("队列为空\n");return;}printf("队头 --> ");int cur = Q->front; // 遍历下标while (cur != Q->rear) {printf("%d -> ", Q->data[cur]);cur = (cur + 1) % MaxSize;}printf("队尾\n");
}

版本1.2 - rear指向队尾后边 且 有 size

SeqQueue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MaxSize 10
typedef int ElemType;typedef struct {ElemType data[MaxSize]; // 静态数组存放元素int front, rear;        // 队头指针和队尾指针int size;               // 队列当前长度
} SeqQueue;// 初始化队列
void InitQueue(SeqQueue* Q);// 销毁队列
void DestroyQueue(SeqQueue* Q);// 清空队列
void ClearQueue(SeqQueue* Q);// 判断队列是否为空
bool IsEmpty(SeqQueue* Q);// 判断队列是否已满
bool IsFull(SeqQueue* Q);// 入队
bool EnQueue(SeqQueue* Q, ElemType x);// 出队
bool DeQueue(SeqQueue* Q, ElemType* x);// 读取队头元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x);// 获取队列长度
int QueueLength(SeqQueue* Q);// 打印队列
void PrintQueue(SeqQueue* Q);

SeqQueue.c

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MaxSize 10
typedef int ElemType;typedef struct {ElemType data[MaxSize]; // 静态数组存放元素int front, rear;        // 队头指针和队尾指针int size;               // 队列当前长度
} SeqQueue;// 初始化队列
void InitQueue(SeqQueue* Q) {Q->front = Q->rear = 0;Q->size = 0;
}// 销毁队列
void DestroyQueue(SeqQueue* Q) {Q->front = Q->rear = 0;Q->size = 0;
}// 清空队列
void ClearQueue(SeqQueue* Q) {Q->front = Q->rear = 0;Q->size = 0;
}// 判断队列是否为空
bool IsEmpty(SeqQueue* Q) {return Q->size == 0;
}// 判断队列是否已满
bool IsFull(SeqQueue* Q) {return Q->size == MaxSize;
}// 入队
bool EnQueue(SeqQueue* Q, ElemType x) {if (IsFull(Q)) return false;Q->data[Q->rear] = x;Q->rear = (Q->rear + 1) % MaxSize;Q->size++;return true;
}// 出队
bool DeQueue(SeqQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false;*x = Q->data[Q->front];Q->front = (Q->front + 1) % MaxSize;Q->size--;return true;
}// 读取队头元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false;*x = Q->data[Q->front];return true;
}// 获取队列长度
int QueueLength(SeqQueue* Q) {return Q->size;
}// 打印队列
void PrintQueue(SeqQueue* Q) {if (IsEmpty(Q)) {printf("队列为空\n");return;}printf("队头 --> ");int cur = Q->front;for (int i = 0; i < Q->size; i++) {printf("%d -> ", Q->data[cur]);cur = (cur + 1) % MaxSize;}printf("队尾\n");
}

版本1.3 - rear指向队尾后边 且 有 tag

SeqQueue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MaxSize 10
typedef int ElemType;typedef struct {ElemType data[MaxSize]; // 静态数组存放元素int front, rear;        // 队头指针和队尾指针bool tag;               // 最近操作标记: true为入队, false为出队
} SeqQueue;// 初始化队列
void InitQueue(SeqQueue* Q);// 销毁队列
void DestroyQueue(SeqQueue* Q);// 清空队列
void ClearQueue(SeqQueue* Q);// 判断队列是否为空
bool IsEmpty(SeqQueue* Q);// 判断队列是否已满
bool IsFull(SeqQueue* Q);// 入队
bool EnQueue(SeqQueue* Q, ElemType x);// 出队
bool DeQueue(SeqQueue* Q, ElemType* x);// 读取队头元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x);// 获取队列长度
int QueueLength(SeqQueue* Q);// 打印队列
void PrintQueue(SeqQueue* Q);

SeqQueue.c

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MaxSize 10
typedef int ElemType;typedef struct {ElemType data[MaxSize]; // 静态数组存放元素int front, rear;        // 队头指针和队尾指针bool tag;               // 最近操作标记: true为入队, false为出队
} SeqQueue;// 初始化队列
void InitQueue(SeqQueue* Q) {Q->front = Q->rear = 0;Q->tag = false;
}// 销毁队列
void DestroyQueue(SeqQueue* Q) {Q->front = Q->rear = 0;Q->tag = false;
}// 清空队列
void ClearQueue(SeqQueue* Q) {Q->front = Q->rear = 0;Q->tag = false;
}// 判断队列是否为空
bool IsEmpty(SeqQueue* Q) {return Q->front == Q->rear && Q->tag == false;
}// 判断队列是否已满
bool IsFull(SeqQueue* Q) {return Q->front == Q->rear && Q->tag == true;
}// 入队
bool EnQueue(SeqQueue* Q, ElemType x) {if (IsFull(Q)) return false;Q->data[Q->rear] = x;Q->rear = (Q->rear + 1) % MaxSize;Q->tag = true;return true;
}// 出队
bool DeQueue(SeqQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false;*x = Q->data[Q->front];Q->front = (Q->front + 1) % MaxSize;Q->tag = false;return true;
}// 读取队头元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false;*x = Q->data[Q->front];return true;
}// 获取队列长度
int QueueLength(SeqQueue* Q) {if (IsFull(Q)) return MaxSize;return (Q->rear - Q->front + MaxSize) % MaxSize;
}// 打印队列
void PrintQueue(SeqQueue* Q) {if (IsEmpty(Q)) {printf("队列为空\n");return;}printf("队头 --> ");int cur = Q->front;int count = QueueLength(Q);for (int i = 0; i < count; i++) {printf("%d -> ", Q->data[cur]);cur = (cur + 1) % MaxSize;}printf("队尾\n");
}

4 链式队列

4.1 两种版本区别

函数/操作	带头结点版本	不带头结点版本
初始化队列	创建头结点，front/rear指向头结点	front/rear初始化为NULL
入队操作	直接插入到rear->next	需先判断是否为空队列再插入
出队操作	删除front->next结点	直接删除front结点
判断队列空	检查front == rear	检查front == NULL
获取队头元素	访问front->next->data	访问front->data
清空队列	释放所有数据结点，保留头结点	释放所有结点
销毁队列	释放头结点和队列结构体	直接释放队列结构体
队列长度	从front->next开始计数	从front开始计数
打印队列	从front->next开始打印	从front开始打印
内存方面	多占用1个头结点空间	不多占用

4.2 链式队列_带头结点

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"typedef int ElemType;
// 结点结构
typedef struct LinkNode {ElemType data;struct LinkNode* next;
}LinkNode;// 链式队列结构
typedef struct LinkQueue {LinkNode *front, *rear;
}LinkQueue;#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef int ElemType;// 结点结构
typedef struct LinkNode {ElemType data;struct LinkNode* next;
} LinkNode;// 链式队列结构
typedef struct LinkQueue {LinkNode *front, *rear;
} LinkQueue;// 函数声明
// 初始化
void InitQueue(LinkQueue* Q);
// 清空
void ClearQueue(LinkQueue* Q);
// 销毁
void DestroyQueue(LinkQueue** Q);
// 入队
bool EnQueue(LinkQueue* Q, ElemType x);
// 出队
bool DeQueue(LinkQueue* Q, ElemType* x);
// 判断队空
bool IsEmpty(LinkQueue* Q);
// 读取队头元素
bool GetHead(LinkQueue* Q, ElemType* x);
// 队列长度
int QueueLength(LinkQueue* Q);
// 打印
void PrintQueue(LinkQueue* Q);// 函数实现
// 初始化（带头结点）
void InitQueue(LinkQueue* Q) {Q->front = Q->rear = (LinkNode*)malloc(sizeof(LinkNode));Q->front->next = NULL; // Q->fornt 是头结点 再加->next是第一个结点
}// 清空（带头结点）
void ClearQueue(LinkQueue* Q) {LinkNode* cur = Q->front->next;// 释放所有结点while (cur != NULL) {LinkNode* temp = cur;cur=cur->next;free(temp);}Q->rear = Q->front = NULL; // 将头指针和尾指针指向头结点并且置空
}// 销毁（带头结点）销毁要用二级指针
void DestroyQueue(LinkQueue** Q) {ClearQueue(*Q);// 释放头结点free((*Q)->front);// 此时头尾指针指向头结点，释放谁都一样// 释放队列结构free(*Q);Q = NULL;
}// 入队（带头结点） 
bool EnQueue(LinkQueue* Q, ElemType x) {LinkNode* NewNode = (LinkNode*)malloc(sizeof(LinkNode));if (!NewNode) return false; // 申请内存失败返回falseNewNode->data = x; // 新结点存储值NewNode->next = NULL; // 新结点（最后一个结点）的后驱是NULLQ->rear->next = NewNode; // 新结点插入到rear后边Q->rear = NewNode; // rear指向刚刚插入的元素return true;
}// 出队（带头结点）
bool DeQueue(LinkQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false; // 空队列无法出队LinkNode* first = Q->front->next; // 将队列第一个存储单元（要删除的单元）位置保存下来，以防将头结点的后继连接到第二个存储单元后，第一个存储单元的位置丢失*x = first->data; // 将队列第一个数据读取出来Q->front->next = first->next; // 将头结点后继连接到第二个存储单元--> 这样第一个存储单元地址就不会保存在队列当中了，也就相当于删除了，或者出队// 如果只有一个存储结点的话，那么rear队尾指针指向的就是第一个存储单元，当把这最后一个存储单元删除的时候rear就不该指向这个“已经删除的结点”了，而应该指向“头结点”，相当于初始化了if (Q->rear == first) Q->rear = Q->front;free(first);return true;
}// 判断队空（带头结点）
bool IsEmpty(LinkQueue* Q) {return Q->front == Q->rear;
}// 读取队头元素
bool GetHead(LinkQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false; // 空队*x = Q->front->next->data;return true;
}// 队列长度（带头结点）
int QueueLength(LinkQueue* Q) {if (IsEmpty(Q)) return 0;LinkNode* cur = Q->front->next; // 从第一个存储结点开始int len = 0;while (cur != NULL) {len++;cur = cur->next;}return len;
}// 打印（带头结点）
void PrintQueue(LinkQueue* Q) {LinkNode* cur = Q->front->next; // 从第一个存储结点开始printf("队头 -> ");while (cur != NULL) {printf("%d -> ", cur->data);cur = cur->next;}printf("队尾\n");
}
int main(void) {return 0;
}

4.3 链式队列_无头结点

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"typedef int ElemType;
// 结点结构
typedef struct LinkNode {ElemType data;struct LinkNode* next;
}LinkNode;// 链式队列结构
typedef struct LinkQueue {LinkNode *front, *rear;
}LinkQueue;#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef int ElemType;// 结点结构
typedef struct LinkNode {ElemType data;struct LinkNode* next;
} LinkNode;// 链式队列结构
typedef struct LinkQueue {LinkNode *front, *rear;
} LinkQueue;// 函数声明
// 初始化
void InitQueue(LinkQueue* Q);
// 清空
void ClearQueue(LinkQueue* Q);
// 销毁
void DestroyQueue(LinkQueue** Q);
// 入队
bool EnQueue(LinkQueue* Q, ElemType x);
// 出队
bool DeQueue(LinkQueue* Q, ElemType* x);
// 判断队空
bool IsEmpty(LinkQueue* Q);
// 读取队头元素
bool GetHead(LinkQueue* Q, ElemType* x);
// 队列长度
int QueueLength(LinkQueue* Q);
// 打印
void PrintQueue(LinkQueue* Q);// 函数实现
// 初始化（无头结点）
void InitQueue(LinkQueue* Q) {// 初始化时，头尾都指向NULLQ->front = Q->rear = NULL;
}// 清空（无头结点）
void ClearQueue(LinkQueue* Q) {LinkNode* cur = Q->front;// 释放所有结点while (cur != NULL) {LinkNode* temp = cur;cur=cur->next;free(temp);}Q->rear = Q->front = NULL; // 将头指针和尾指针指向NULL
}// 销毁（无头结点）应使用二级指针-->因为销毁后要将Q置空
void DestroyQueue(LinkQueue** Q) {ClearQueue(*Q); // 清空// 释放队列结构free(*Q);Q = NULL; // 给Q置空
}// 入队（无头结点） 
bool EnQueue(LinkQueue* Q, ElemType x) {// 有头节点的时候入队不需要额外判断是否为空队，因为头尾指针此时都是指向的头结点，操作相同的LinkNode* NewNode = (LinkNode*)malloc(sizeof(LinkNode));if (!NewNode) return false; // 申请内存失败返回falseNewNode->data = x; // 新结点存储值NewNode->next = NULL; // 新结点（最后一个结点）的后驱是NULL// 一句：空队修改队尾队头，不是空队列只修改尾指针if (IsEmpty(Q)) {// 更新队头队尾指针Q->front = NewNode; // 如果是空队列，因为没有头结点的存在，所以要将这个新的结点放到第一个结点的位置，而Q->front就是指的第一个结点（如果有头结点的话，指的是头结点，而Q->front->next指的是第一个结点）Q->rear = NewNode; // 更新尾指针：rear指向刚刚插入的元素} else { // 当不是空队的时候-Q->rear->next = NewNode; // 新结点插入到rear后边Q->rear = NewNode; // 更新尾指针：rear指向刚刚插入的元素}return true;
}// 出队（无头结点）
bool DeQueue(LinkQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false; // 空队列无法出队LinkNode* First = Q->front; // 将队列第一个存储单元（要删除的单元）位置保存下来，以防第二个结点变为第一个结点地址后，第一个结点地址无法释放*x = First->data; // 将队列第一个数据读取出来// 注意：如果是只有一个结点，执行出队的话，要改变队尾队头指针指向，因为当是空队的时候队头队尾指针都要指向NULLif (Q->rear == First) {Q->front = NULL;Q->rear = NULL;} else { // 当有多个结点的时候，只需要改变队头指向即可Q->front = First->next; // 将第一个结点改为原第二个结点}// 别忘了：释放原来第一个结点free(First); // 释放原第一个结点return true;
}// 判断队空
bool IsEmpty(LinkQueue* Q) {return Q->front == NULL; // 当是空队列的时候头指针指向NULL
}// 读取队头元素（无头结点）
bool GetHead(LinkQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false; // 空队*x = Q->front->data;return true;
}// 队列长度（无头结点）
int QueueLength(LinkQueue* Q) {if (IsEmpty(Q)) return 0;LinkNode* cur = Q->front; // 从第一个结点开始int len = 0;while (cur != NULL) {len++;cur = cur->next;}return len;
}// 打印（无头结点）
void PrintQueue(LinkQueue* Q) {LinkNode* cur = Q->front; // 从第一个结点开始printf("队头 -> ");while (cur != NULL) {printf("%d -> ", cur->data);cur = cur->next;}printf("队尾\n");
}
int main(void) {return 0;
}

5 双端队列

除了顺序队列和链式队列以外，还有一种队列叫做双端队列

首先，先来将栈、普通队列与双端队列比较一下，都为线性表

• 栈：只允许从一端插入删除
• 普通队列：只允许从一端插入，只允许从另一端删除
• 双端队列：只允许从两端插入或删除 –> 队头队尾都可以插入和删除
  • 输入受限的双端队列：允许一端插入删除；另一端只能允许插入 –> 队头只能删除，队尾既可以插入和删除
  • 输出受限的双端队列：允许一端插入删除；另一端只能允许删除 –> 队头可以插入和删除，队尾只能插入