GESP 六级 · GESP 202409 C++ 六级 第 18 题

栈是一种线性结构，可通过数组或链表来实现。二者相比，数组实现占用的内存较少，链表实现的入队和出队操作的时间复杂度较低。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】栈操作复杂度｜内存占用｜数据结构特性

🎯 考纲定位 GESP 六级「数据结构与算法」模块第 4 章 栈与队列。命题人专门卡住考生对「栈」与「队列」术语的混淆——六级前阶段只要求会栈的基本操作，队列的入队出队复杂度是新增考点。这道题就是利用术语偷换，检验考生对栈操作和队列操作的区分能力。

🧠 解题思维 看到"栈"先锁定 LIFO 特性，再看"数组 vs 链表"：数组栈用连续内存，链表栈每个节点多存指针。关键陷阱是后半句"入队出队"——这是队列操作，栈只有入栈出栈！所以命题人把队列的术语嫁接在栈上，制造概念偷换。因此，无论前半句对错，后半句已经让整句话错误。

🪤 陷阱拆解 A 选项"正确"诱饵：前半句"数组占内存少"看似合理（无指针开销），但链表栈按需分配，内存效率取决于实际使用量；后半句"入队出队时间复杂度低"更是张冠李戴，栈操作都是 O(1)，队列才是入队出队。命题人利用考生对"栈""队列"术语的模糊记忆，让只背结论的人直接选 A。

🔄 反命题思维 如果改成"队列可通过数组或链表实现"，前半句仍成立，后半句"入队出队时间复杂度低"就变成真命题——链表队列 O(1) 入队出队是标准结论。这类题刷到先问自己：是不是把队列操作安在栈头上？