软考-软件设计师：数据结构-线性结构-队列、栈 作者：马育民 • 2025-04-07 08:49 • 阅读：10004 # 栈 栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。换句话说，栈的修改是按先进后出的原则进行的。 因此，栈又称为后进先出（LastIn First Out，LIFO）的线性表。  ### 类比 栈相当于弹夹，**后压入** 的子弹，**最先弹出**；**先压入** 的子弹，**最后弹出**  ### 相关概念 栈顶（Top）：栈中进行插入和删除操作的一端称为栈顶（Top) 栈底（Bottom）：固定的，不允许进行插入和删除的另一端。 空栈：不含任何元素的空表。 栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构 ### 考点 **入栈 不等于 出栈** 看下面题 ### 题（入栈不等于出栈） 习题：元素按照a、b、c的次序进入栈，请尝试写出其所有可能的出栈序列。 ``` abc acb cba bca bac ``` 不会有 `cab` # 队列 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、入栈序列与入队序列一定互为逆序 ### 分析 执行顺序如下： ``` 入栈 -> 出栈 -> 入队 -> 出队 ``` ``` 入栈 后 出栈 // 上面可知，入栈与出栈不相等 出栈 后 入队 // 出栈的结果，又入队，所以 出栈 等于 入队 入队 后 出队 // 先进先出，所以入队 等于 出队 ``` 总结： ``` 入栈 不等于 出栈 出栈 等于 入队 等于 出队 ``` 所以：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_1GWtt7GMbVT.html