软考-软件设计师：数据结构-线性结构-队列、循环队列 作者：马育民 • 2026-02-09 21:55 • 阅读：10004 # 介绍 队列，queue是一种 **先进先出**(First In First Out，缩写 **FIFO** )的数据结构 从 **队尾添加** 元素，从 **队头删除** 元素 **最先插入** 在元素将是 **最先被删除**；**最后插入的** 元素将 **最后被删除**，因此队列称为“先进先出”（FIFO—first in first out） [](https://www.malaoshi.top/upload/0/0/1EF4sLPUXtTu.jpg) [](http://www.malaoshi.top/upload/0/0/1EF2xjBbJwbv.png) 一般不支持随机访问，即不能任意访问中间的元素 ### 概念 队尾(Rear)：允许插入元素的一端称 队头（Front)：允许删除元素的一端称 ### 例子 下面设顺序队列 Q 的容量为 6，其队头指针为 front，队尾指针为 rear，头、尾指针和队列中元素之间的关系如图： [](https://www.malaoshi.top/upload/0/0/1GWttzsHjCN.png) # 循环队列 ### 顺序队列的 缺点 在顺序队列中，为了降低运算的复杂度，元素入队时只修改队尾指针，元素出队时只修改队头指针，如下图 [](https://www.malaoshi.top/upload/0/0/1GWttzsHjCN.png) 由于顺序队列的存储空间 **容量是提前设定的**，所以队尾指针会有一个 **上限值**，**当队尾指针达到该上限时**，就 **不能只通过修改队尾指针** 来实现新元素的 **入队** 操作了，如上图 ### 循环队列 若将顺序队列假想成一个 **环状结构**（通过整除取余运算实现)，则可维持入队、出队操作运算的简单性，如图： [](https://www.malaoshi.top/upload/0/0/1GWtuek2B64.png) ### 优点 入队和出队操作都不需要移动队列中的其他元素 ### 缺点 当出队操作导致 **队列变为空** 时，则有 `Q.rear==Q.front`，如图 d所示 若入队操作导致 **队列满**，则 `Q.rear==Q.front`，如图e所示。 也就是说：在队列空和队列满的情况下，仅根据 `Q.rear==Q.front` ， **无法断 定队列的状态**。 ##### 解决 下两种处理方式： - 方法1：设置一个标志，以区别头、尾指针的值相同时队列是空还是满； - 方法2：牺牲一个存储单元，约定以“队列的尾指针所指位置的下一个位置是队头指针时”表示队列满，如图f所示，而头、尾指针的值相同时表示队列为空。 ### 概念 队空条件：`Q.head = Q.rear`，头尾指针指向同一个位置，如图a 队满条件：`(Q.rear + 1)%size = Q.head` 队列长度：`(Q.rear - Q.head + size) % size`。**提示：** ( `Q.rear - head` 可能为负数，所以 `+ size` ) # 题 对于一个长度为n(n>1)且元素互异的序列，令其所有元素依次通过一个 **初始为空的 栈** 后，再通过一个 **初始为空的 队列**。假设队列和栈的容量都足够大，且**只要栈非空就可以进行出栈操作**，只要队列非空就可以进行出队操作，那么以下叙述中，正确的是（） A、出队序列和出栈序列一定互为逆序 B、出队序列和出栈序列一定相同 C、入栈序列与入队序列一定相同 D、入栈序列与入队序列一定互为逆序 ### 分析 执行顺序如下： ``` 入栈 -> 出栈 -> 入队 -> 出队 ``` 关键：**只要栈非空就可以进行出栈操作**，有一个元素入栈就可以出栈，也可能有两个元素入栈，然后出栈 比如：序列是：`1,2,3` 执行过程如下： ``` 1入栈 2入栈 2出栈，2入队，2出队 3入栈 3出栈，3入队，3出队 1出栈，1入队，1出队 ``` 规律： - 入栈与出栈不相同 - 出栈后，又入队，所以 出栈 等于 入队 - 队列是 先进先出，所以入队 等于 出队 总结： - 入栈 不等于 出栈 - 出栈 等于 入队 等于 出队 所以：A 错，B对，C错，D错（不一定） ### 答案 B # 题 设有 `栈S` 和 `队列Q` 初始状态为空，数据元素序列 `a,b,c,d,e,f` 依次通过栈S，且多个元素从S出栈后立即进入队列Q，若出队的序列是 `b,d,f,e,c,a` ,则s中的元素最多时，栈底到栈顶的元素依次为（）。 A、 a,b,c B、a,c,d C、a,c,e,f D、a,d,f,e ### 分析 执行顺序如下： ``` 入栈 -> 出栈 -> 入队 -> 出队 ``` ``` 入栈 后 出栈 // 上面可知，入栈与出栈不相等 出栈 后 入队 // 出栈的结果，又入队，所以 出栈 等于 入队 入队 后 出队 // 先进先出，所以入队 等于 出队 ``` 总结： ``` 入栈 不等于 出栈 出栈 等于 入队 等于 出队 ``` 所以 `b,d,f,e,c,a` 也就是出栈的结果 则s中的元素最多时，栈底到栈顶的元素，如下图： [](https://www.malaoshi.top/upload/0/0/1GWu5sU0uaq.png) ### 答案 C # 题 **双端队列** 是指在队列的 **两个端口** 都可以 **加入** 和 **删除** 元素，如下图所示。现在要求元素 **进队列** 和 **出队列** 必须在 **同一端口**，**即从A端进队的元素必须从A端出、从B端进队的元素必须从B端出**，则对于4个元素的序列 `a、b、c、d`，若要求前2个元素 `(a、b)` 从A端口按次序全部进入队列，后两个元素 `(c、d)` 从B端口按次序全部进入队列，则不可能得到的出队序列是（） [](https://www.malaoshi.top/upload/0/0/1GWu5uGxWrv.png) A、d、a、b、c B、d、c、b、a C、b、a、d、c D、b、d、C、a ### 分析 将 `(a、b)` 依次进入左侧端口， `(c、d)` 依次进入右侧端口，如下图： [](https://www.malaoshi.top/upload/0/0/1GWu65N67ig.png) **关键：** 此时类似栈的操作：**先进后出**，因为同一个端口进出 **总结顺序：** - b先出，a后出 - d先出，c后厨 - bd谁先出不确定 - ac谁先出不确定 A、`d、a、b、c` a比b先出，不可能 B、`d、c、b、a` 可能 C、`b、a、d、c` 可能 D、`b、d、C、a` 可能 ### 答案 A # 题 设某循环队列Q的定义中有front和rear两个域变量，其中，front指示队头元素的位置，rear指示队尾元素之后的位置，如下图所示。若该队列的容量为M，则其长度为（ ） [](https://www.malaoshi.top/upload/0/0/1GWu6E0WomG.png) A、`(Q.rear-Q.front +1)` B、`(Q.rear-Q.front+M)` C、`(Q.rear-Q.front+1)%M` D、`(Q.rear-Q.front+M)%M` ### 答 D 原文出处：http://malaoshi.top/show_1GW2kjdhBCzY.html