基本概念

队列

队列(Queue)是一种先进先出(First In First Out,简称FIFO)的线性表,只允许在表的一端(称为队尾,rear)进行插入,在另一端(称为队头,front)进行删除。

  • 插入操作称为入队(enqueue)
  • 删除操作称为出队(dequeue)
  • 不含任何元素的队列称为空队列

队列的特点

  • 先进先出(FIFO):最先入队的元素最先出队
  • 操作受限:只能在队尾插入,在队头删除
  • 队头和队尾动态变化:两个指针分别随着出队和入队操作移动

队列的基本操作

操作说明
InitQueue(&Q)初始化一个空队列
DestroyQueue(&Q)销毁队列,释放内存
EnQueue(&Q, x)将元素 xx 入队
DeQueue(&Q, &x)队头元素出队,用 xx 返回
GetHead(Q, &x)读取队头元素,用 xx 返回(不出队)
QueueEmpty(Q)判断队列是否为空
QueueLength(Q)返回队列中元素的个数

习题

习题 1

队列的特点是( )

A. 先进先出 B. 后进先出 C. 随机进出 D. 按优先级进出

队列先进先出线性表

解题思路:

本题考查队列的基本特征。判断时抓住队列的两端分工——队尾插入、队头删除——由此推出出队次序必然是先进先出,再排除描述其他结构的选项。

详细步骤:

  1. 队列是一种操作受限的线性表,只允许在队尾插入(入队),在队头删除(出队)。
  2. 由于先入队的元素排在前面,最先入队的元素必然最先出队,队列的次序特征是先进先出(First In First Out,FIFO),选项 A 正确。
  3. 选项 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

队列栈出栈序列容量分析

解题思路:

本题要求由出队顺序倒推栈的最小容量。关键是把队列的先进先出反过来用:元素一进栈就紧接着进队列,所以队列的出队顺序恰好就是栈的出栈顺序。据此模拟每一步入栈出栈,找出栈中元素个数的最大值。

详细步骤:

  1. 因为每个元素出栈后立即进入队列,队列先进先出,所以这 6 个元素的出队顺序 b、d、c、f、e、a 就是栈的出栈顺序。
  2. a 入栈(栈:[a]);b 入栈(栈:[a,b])后 b 出栈(栈:[a])。
  3. c 入栈(栈:[a,c]);d 入栈(栈:[a,c,d])后 d 出栈(栈:[a,c])、c 出栈(栈:[a])。
  4. e 入栈(栈:[a,e]);f 入栈(栈:[a,e,f])后 f 出栈(栈:[a,e])、e 出栈(栈:[a])、a 出栈。
  5. 整个过程中栈里最多同时存放 3 个元素(a、c、d 或 a、e、f),所以栈的容量至少是 3。

最终答案:

B(3)。

习题 3

简述队列的定义和主要特点。队列和栈有什么区别?

队列先进先出队列与栈对比操作受限

解题思路:

本题要求先给出队列的定义与特点,再与栈作对比。答题时先讲清队列的两端分工与先进先出的次序特征,再从次序特征、操作端点、典型场景三个角度与栈逐条对照。

详细步骤:

  1. 队列的定义:队列是一种先进先出(FIFO)的线性表,只允许在表的一端(队尾)进行插入,在另一端(队头)进行删除。
  2. 主要特点:先进先出(FIFO),最先入队的元素最先出队;操作受限,只能在队尾插入(入队)、在队头删除(出队);队头和队尾动态变化,两个指针分别随出队和入队操作移动。
  3. 与栈的第一点区别:栈是后进先出(LIFO),队列是先进先出(FIFO)。
  4. 与栈的第二点区别:栈只允许在一端(栈顶)进行插入和删除,队列允许在一端(队尾)插入、在另一端(队头)删除。
  5. 与栈的第三点区别:栈适合处理“最后来的先处理”的场景(如函数调用、表达式求值),队列适合处理“先来先服务”的场景(如任务调度、缓冲区管理)。

最终答案:

队列是一种先进先出(FIFO)的线性表,只允许在队尾插入、在队头删除。与栈的区别在于:栈是后进先出且只在一端操作,队列是先进先出且两端分工,栈适合函数调用、表达式求值,队列适合任务调度、缓冲区管理。

发现内容有问题?

告诉我们哪里需要改进。