1.1 stack的介绍stack的文档介绍stack是一种后进先出LIFO, Last In First Out的容器适配器属于标准模板库STL中的一种。它仅允许在栈顶进行插入和删除操作保证了数据访问的顺序性。stack底层通常由deque、list或vector实现具体取决于编译器实现但用户无需关心底层细节。其核心特性包括只能通过top()访问栈顶元素。元素只能从栈顶压入push或弹出pop。不支持随机访问或遍历。适用于递归模拟、表达式求值、括号匹配、函数调用栈等场景。1.2 stack的使用函数说明接口说明stack()构造一个空的栈。若未指定容器类型默认使用deque作为底层容器。可显式指定如stackint, vectorint s;来改变底层结构。empty()判断栈是否为空。返回true表示无元素false表示有至少一个元素。常用于防止对空栈调用top()引发未定义行为。size()返回当前栈中元素的数量。时间复杂度为 O(1)因内部维护了计数器。top()返回栈顶元素的引用。注意不能对空栈调用此函数否则会导致未定义行为。使用前务必检查empty()。push(const T val)将元素val压入栈顶。该操作会复制val到栈中若val是对象则调用拷贝构造函数。pop()移除栈顶元素。仅移除不返回值。不能对空栈调用否则程序行为异常。重点强调top()和pop()必须在非空栈上调用否则引发运行时错误。stack不提供迭代器无法遍历所有元素。适合用于实现递归逻辑的非递归版本如树的深度优先遍历、路径回溯等。2.1 queue的介绍queue的文档介绍queue是一种先进先出FIFO, First In First Out的容器适配器同样属于 STL。它只允许在队尾插入元素在队头删除元素保证了数据处理的顺序性。典型应用场景包括消息队列广度优先搜索BFS缓冲区管理任务调度系统queue的底层实现通常基于deque也可自定义为list等容器但接口保持一致。2.2 queue的使用函数声明接口说明queue()构造一个空队列。可指定底层容器类型例如queueint, listint q;以使用list作为底层存储。empty()检测队列是否为空。返回true表示无元素false表示有元素。是安全使用front()/back()的前提。size()返回队列中有效元素的个数。时间复杂度为 O(1)内部维护计数。front()返回队头元素的引用。不可对空队列调用否则导致未定义行为。用于获取最早进入的元素。back()返回队尾元素的引用。同样需确保队列非空。用于查看最新加入的元素。push(const T val)在队尾插入新元素val。执行复制构造若为对象则触发拷贝语义。pop()移除队头元素。仅移除不返回值。调用前必须确认队列非空否则程序崩溃。重点强调front()与back()都要求队列非空调用前应始终检查empty()。queue不支持随机访问或遍历不能使用迭代器。在图的广度优先搜索BFS中queue是实现层级遍历的核心工具。若需频繁在头部删除元素且性能敏感可考虑使用std::deque直接实现避免封装开销。3. stack的模拟实现栈stack是一种后进先出LIFO, Last In First Out的数据结构其核心操作仅限于对尾部即栈顶进行插入与删除。在C中std::stack是一个适配器容器它基于其他容器如deque、vector、list实现但默认使用deque作为底层容器。3.1 为什么所有操作都在尾部栈的操作逻辑决定了只能在末尾进行压入push和弹出pop并且访问的是最后一个元素top。因此无论底层使用哪种容器都应将栈顶固定在容器的尾端并统一使用back()、push_back()、pop_back()等接口。// 模拟 stack 的基本结构以 vector 为底层templatetypenameTclassMyStack{private:std::vectorTdata;public:// 构造函数创建空栈MyStack()default;// 判空boolempty()const{returndata.empty();}// 返回元素个数size_tsize()const{returndata.size();}// 访问栈顶元素返回引用Ttop(){if(empty()){throwstd::runtime_error(Stack is empty!);}returndata.back();// 直接访问尾部}constTtop()const{if(empty()){throwstd::runtime_error(Stack is empty!);}returndata.back();}// 压入元素到栈顶尾部voidpush(constTval){data.push_back(val);}// 弹出栈顶元素尾部移除voidpop(){if(empty()){throwstd::runtime_error(Cannot pop from empty stack!);}data.pop_back();}};✅重点说明所有操作均围绕data.back()展开。使用vector时push_back与pop_back都是O(1)平摊时间复杂度。若用list虽然每次分配节点开销大但操作仍是常数时间。deque在性能和内存布局上更优是标准库默认选择。3.2 底层容器的选择分析容器类型是否适合做 stack 底层原因vector✅ 推荐内存连续缓存友好尾部操作push_back/pop_back为 O(1) 摊还list✅ 可行不需要搬移数据但每次动态分配节点性能略差deque✅✅ 标准推荐分段连续两端操作均为 O(1)且支持高效扩容关键点std::stack默认模板参数为std::dequeT即usingstackstd::stackint;// 等价于 std::stackint, std::dequeint这意味着你只需写stackint无需显式指定容器。3.3 为什么不使用 vector 的头部如果试图把栈顶放在vector的前端那么push要调用insert(data.begin(), val)→ O(n)pop要调用erase(data.begin())→ O(n)这会导致整个栈操作变为线性时间严重违背 LIFO 的设计初衷。❌ 错误做法示例data.insert(data.begin(),val);// O(n)不可取✅ 正确做法始终是尾部操作。3.4 时间复杂度总结操作复杂度说明push()O(1)向尾部添加元素pop()O(1)移除尾部元素top()O(1)查看尾部元素empty()O(1)检查是否为空size()O(1)vector.size()本身为常数时间⚠️ 注意vector在扩容时会触发整体复制但这是摊还平均为 O(1)不影响整体复杂度。4. queue的模拟实现队列queue是一种先进先出FIFO, First In First Out的数据结构特点是从一端入队从另一端出队。4.1 与 stack 的本质区别特性Stack栈Queue队列插入位置尾部back尾部back删除位置尾部back头部front操作方式LIFOFIFO 核心差异在于pop()对应的是pop_front()而非pop_back()。// 模拟 queue以 deque 为底层templatetypenameTclassMyQueue{private:std::dequeTdata;public:MyQueue()default;boolempty()const{returndata.empty();}size_tsize()const{returndata.size();}// 返回队头元素Tfront(){if(empty()){throwstd::runtime_error(Queue is empty!);}returndata.front();}constTfront()const{if(empty()){throwstd::runtime_error(Queue is empty!);}returndata.front();}// 返回队尾元素Tback(){if(empty()){throwstd::runtime_error(Queue is empty!);}returndata.back();}constTback()const{if(empty()){throwstd::runtime_error(Queue is empty!);}returndata.back();}// 入队在尾部插入voidpush(constTval){data.push_back(val);}// 出队从头部删除voidpop(){if(empty()){throwstd::runtime_error(Cannot pop from empty queue!);}data.pop_front();}};✅ 该实现中push_back()与pop_front()都是常数时间操作。4.2 为什么不能用 vector 做 queue 底层vector的pop_front()是O(n)操作因为要将所有元素向前移动一位。// ❌ 错误示范用 vector 做 queuestd::vectorintq;q.push_back(1);// OK: O(1)q.pop_front();// ❌ O(n)效率极低 结论vector 不能用于实现队列除非只做单向操作。4.3 为什么选择 deque 作为默认底层deque双端队列内部结构如下由多个固定大小的缓冲区组成通过指针数组连接这些缓冲区支持在首尾两端高效插入/删除任意一端扩展时只需新增一块缓冲区无需搬移原有数据因此push_front、pop_front、push_back、pop_back均为O(1)。✅std::queue默认使用std::dequeT正是因为它能完美满足队列的两端操作需求。4.4 环形缓冲区数组队列实现面试高频考点这是一种不依赖动态容器的高性能队列实现方式适用于固定容量场景。templatetypenameT,size_t CapacityclassCircularQueue{private:T buffer[Capacity];size_t head0;// 指向队头size_t tail0;// 指向下一个可写位置size_t count0;// 当前元素数量public:boolempty()const{returncount0;}boolfull()const{returncountCapacity;}voidpush(constTval){if(full()){throwstd::runtime_error(Queue is full!);}buffer[tail]val;tail(tail1)%Capacity;count;}voidpop(){if(empty()){throwstd::runtime_error(Queue is empty!);}head(head1)%Capacity;--count;}Tfront(){if(empty()){throwstd::runtime_error(Queue is empty!);}returnbuffer[head];}constTfront()const{if(empty()){throwstd::runtime_error(Queue is empty!);}returnbuffer[head];}Tback(){if(empty()){throwstd::runtime_error(Queue is empty!);}returnbuffer[(tail-1)%Capacity];}size_tsize()const{returncount;}};✅ 优点内存固定无动态分配所有操作均为常数时间适合嵌入式或实时系统。⚠️ 注意事项使用“牺牲一个位置”来区分空满状态即full()条件为count Capacity取模运算保证循环访问满时需扩容重新分配数组并复制数据代价较高。4.5 时间复杂度总结操作复杂度说明push()O(1)尾部插入pop()O(1)头部删除front()O(1)获取队头back()O(1)获取队尾empty()O(1)判空size()O(1)维护计数器✅ 当底层为deque或list时全部操作为O(1)。5. stack 与 queue 的对比对比维度Stack栈Queue队列数据访问原则LIFO后进先出FIFO先进先出插入位置尾部top尾部back删除位置尾部top头部front主要用途表达式求值、递归回溯、括号匹配、函数调用栈消息队列、广度优先搜索BFS、任务调度典型应用场景函数调用栈、撤销操作、表达式解析缓冲处理、打印队列、网络请求排队底层容器要求支持尾部增删vector/list/deque必须支持头部删除list/deque能否用 vector✅ 可以尾部操作❌ 不推荐pop_front() 为 O(n)STL 默认容器dequedeque操作复杂度所有操作均为 O(1)所有操作均为 O(1)底层为 deque/list总结要点重点提炼stack的核心是“尾部操作”所有接口都基于back()系列queue的核心是“两端操作”必须支持高效的pop_front()vector适合栈不适合队列deque是两者共同的理想底层容器list虽然性能稍差但也能胜任两种结构环形队列是面试中考察数据结构设计的重要题目std::stack与std::queue都是适配器可通过模板自定义底层容器实际开发中直接使用标准库即可无需手动实现但理解原理有助于调试与优化。 提醒掌握这些底层机制才能写出高效、安全的代码尤其在算法竞赛、系统编程、嵌入式开发中至关重要。