CSP-J 2022 第一轮 第 10 题：关于栈和队列表述不恰当的一项

题目

以下对数据结构的表述不恰当的一项为：（ ）。

选项

• A. 图的深度优先遍历算法常使用的数据结构为栈。
• B. 栈的访问原则后进先出，队列的访问原则是先进先出。
• C. 队列常常被用于广度优先搜索算法。
• D. 栈与队列存在本质不同，无法用栈实现队列。

答案

D

题解

答案是 D。

栈和队列虽然存取顺序不同，但可以用两个栈实现一个队列。

例如，用栈 A 接收新元素，用栈 B 取出元素：

• 入队：将元素压入栈 A。
• 出队：若栈 B 为空，就把栈 A 的元素依次弹出并压入栈 B；再弹出栈 B 的栈顶元素。

假设依次入队 1、2、3，从 A 转移到 B 时顺序为 3、2、1，此时 B 的栈顶是 1，出队顺序就是 1、2、3，符合队列的先进先出原则。

其余选项都正确：

• A：深度优先遍历（DFS）常用栈实现，递归实现也会用到调用栈。
• B：栈是后进先出，队列是先进先出。
• C：广度优先搜索（BFS）常用队列实现。