基本概念
定义
定义是对概念、术语或对象含义的精确描述。理解定义是学习任何知识领域的基础,每个概念都有其明确的定义。
队列(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. 按优先级进出
解题思路:
本题考查队列的基本特征。判断时抓住队列的两端分工——队尾插入、队头删除——由此推出出队次序必然是先进先出,再排除描述其他结构的选项。
详细步骤:
- 队列是一种操作受限的线性表,只允许在队尾插入(入队),在队头删除(出队)。
- 由于先入队的元素排在前面,最先入队的元素必然最先出队,队列的次序特征是先进先出(First In First Out,FIFO),选项 A 正确。
- 选项 B“后进先出”是栈的特点;选项 C“随机进出”违反了队列的操作限制;选项 D“按优先级进出”不属于队列的基本特征。
最终答案:
A。
习题 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
解题思路:
本题要求由出队顺序倒推栈的最小容量。关键是把队列的先进先出反过来用:元素一进栈就紧接着进队列,所以队列的出队顺序恰好就是栈的出栈顺序。据此模拟每一步入栈出栈,找出栈中元素个数的最大值。
详细步骤:
- 因为每个元素出栈后立即进入队列,队列先进先出,所以这 6 个元素的出队顺序 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。
最终答案:
B(3)。
习题 3
简述队列的定义和主要特点。队列和栈有什么区别?
解题思路:
本题要求先给出队列的定义与特点,再与栈作对比。答题时先讲清队列的两端分工与先进先出的次序特征,再从次序特征、操作端点、典型场景三个角度与栈逐条对照。
详细步骤:
- 队列的定义:队列是一种先进先出(FIFO)的线性表,只允许在表的一端(队尾)进行插入,在另一端(队头)进行删除。
- 主要特点:先进先出(FIFO),最先入队的元素最先出队;操作受限,只能在队尾插入(入队)、在队头删除(出队);队头和队尾动态变化,两个指针分别随出队和入队操作移动。
- 与栈的第一点区别:栈是后进先出(LIFO),队列是先进先出(FIFO)。
- 与栈的第二点区别:栈只允许在一端(栈顶)进行插入和删除,队列允许在一端(队尾)插入、在另一端(队头)删除。
- 与栈的第三点区别:栈适合处理“最后来的先处理”的场景(如函数调用、表达式求值),队列适合处理“先来先服务”的场景(如任务调度、缓冲区管理)。
最终答案:
队列是一种先进先出(FIFO)的线性表,只允许在队尾插入、在队头删除。与栈的区别在于:栈是后进先出且只在一端操作,队列是先进先出且两端分工,栈适合函数调用、表达式求值,队列适合任务调度、缓冲区管理。
