基本概念
队列
队列（Queue）是一种先进先出（First In First Out，简称FIFO）的线性表，只允许在表的一端（称为队尾，rear）进行插入，在另一端（称为队头，front）进行删除。
- 插入操作称为入队（enqueue）
- 删除操作称为出队（dequeue）
- 不含任何元素的队列称为空队列
队列的特点
- 先进先出（FIFO）：最先入队的元素最先出队
- 操作受限：只能在队尾插入，在队头删除
- 队头和队尾动态变化：两个指针分别随着出队和入队操作移动
队列的基本操作
| 操作 | 说明 |
|---|---|
InitQueue(&Q) | 初始化一个空队列 |
DestroyQueue(&Q) | 销毁队列，释放内存 |
EnQueue(&Q, x) | 将元素 入队 |
DeQueue(&Q, &x) | 队头元素出队，用 返回 |
GetHead(Q, &x) | 读取队头元素，用 返回（不出队） |
QueueEmpty(Q) | 判断队列是否为空 |
QueueLength(Q) | 返回队列中元素的个数 |
习题
习题 1
队列的特点是（ ）
A. 先进先出 B. 后进先出 C. 随机进出 D. 按优先级进出
答案与解析
答案：A
解析：队列是一种先进先出（First In First Out，FIFO）的线性表，只允许在队尾插入，在队头删除。最先入队的元素最先出队。
习题 2
设栈S和队列Q的初始状态均为空，元素 a、b、c、d、e、f 依次进入栈S。若每个元素出栈后立即进入队列Q，且6个元素出队的顺序是 b、d、c、f、e、a，则栈S的容量至少是（ ）
A. 2 B. 3 C. 4 D. 5
答案与解析
答案：B
解析： 队列的特点是先进先出，所以出队顺序就是入队顺序，也就是出栈顺序：b, d, c, f, e, a。
模拟入栈出栈过程：
- a入栈（栈：[a]）
- b入栈（栈：[a,b]）→ b出栈（栈：[a]）
- c入栈（栈：[a,c]）
- d入栈（栈：[a,c,d]）→ d出栈（栈：[a,c]）→ c出栈（栈：[a]）
- e入栈（栈：[a,e]）
- f入栈（栈：[a,e,f]）→ f出栈（栈：[a,e]）→ e出栈（栈：[a]）→ a出栈
栈中最多同时有3个元素（a,c,d 或 a,e,f），所以容量至少是3。
习题 3
简述队列的定义和主要特点。队列和栈有什么区别？
答案与解析
队列的定义：队列是一种先进先出（FIFO）的线性表，只允许在表的一端（队尾）进行插入，在另一端（队头）进行删除。
主要特点：
- 先进先出（FIFO）：最先入队的元素最先出队
- 操作受限：只能在队尾插入（入队），在队头删除（出队）
- 队头和队尾动态变化：两个指针分别随着出队和入队操作移动
队列与栈的区别：
- 栈是后进先出（LIFO），队列是先进先出（FIFO）
- 栈只允许在一端（栈顶）进行插入和删除
- 队列允许在一端（队尾）插入，在另一端（队头）删除
- 栈适合处理”最后来的先处理”的场景（如函数调用、表达式求值）
- 队列适合处理”先来先服务”的场景（如任务调度、缓冲区管理）