【C++】stack和queue

stack 栈 queue 队列C STL前言本文围绕 C STL 中的三种容器适配器展开stack栈、queue队列。它们本身不是独立容器而是对底层容器的封装与接口限制因此理解它们的接口语义和底层容器选择是正确使用它们的关键。文章会逐一介绍三者的常用接口、元素进出规则并说明为什么stack与queue默认使用deque作为底层容器而priority_queue默认使用vector帮助你在实际场景中做出合适的选择。底层stack、queue不是容器是容器适配器默认底层用 deque stackLIFO 后进先出 queueFIFO 先进先出为什么默认用 deque 作为底层容器deque是双端队列在头部和尾部插入、删除元素都是常数时间复杂度而且不需要像vector那样在扩容时整体搬移已有元素因此stack的push/pop和queue的入队/出队都能稳定地保持高效。从内存角度看deque由多段固定大小的缓冲区拼接而成扩容时只需新增一段缓冲区不会一次性申请大块连续内存也不会产生大量元素拷贝内存增长更平滑。相比之下vector要求元素在内存中连续存放尾部操作虽然也是均摊常数时间但一旦容量不足就要重新申请更大的连续空间并搬移全部元素而头部插入删除更是 O(n) 的整体移动对queue的队首弹出很不友好。结论需要双端高效操作、又不要求随机访问和内存连续性时deque是stack与queue更合适的默认底层容器vector更适合只在尾部操作、且看重连续内存与缓存友好的场景例如priority_queue。stackint s1接口作用push(val)入栈压到栈顶pop()弹出栈顶元素不返回值top()返回栈顶元素引用不会删除empty()判断是否为空空返回 truesize()返回栈中元素个数stack没有迭代器不能遍历只能操作栈顶。template class T, class Container dequeT class stack;stackint s1; s1.push(1); s1.push(2); cout st.top(); // 2 s1.pop(); cout st.top(); // 1栈不能遍历stack 没有迭代器不能 for 循环遍历只能不断 toppop。queue 队列template class T, class Container dequeT class queue;底层默认容器dequequeueint q;常用接口表格函数作用push(x)入队加到队尾pop()弹出队首不返回元素front()返回队首元素back()返回队尾元素empty()是否为空size()元素数量同样pop () 只删除不返回值queueint q; q.push(1); q.push(2); cout q.front(); // 1 q.pop(); cout q.front(); // 2queue 也没有迭代器不能直接遍历。容器规则取元素位置删除位置底层默认stackLIFO 后进先出top () 栈顶pop () 栈顶dequequeueFIFO 先进先出front () 队首pop () 队首dequepriority_queue按优先级top () 最值pop () 最值vectorstack 和 queue 叫容器适配器container adapter它们本身不是独立容器只是封装了 deque/vector限制接口只留下栈 / 队列行为。总结stack栈规则为 LIFO 后进先出取元素位置是top()栈顶删除位置是pop()栈顶默认底层容器为deque。queue队列规则为 FIFO 先进先出取元素位置是front()队首删除位置是pop()队首默认底层容器为deque。priority_queue优先队列规则为按优先级出队取元素位置是top()最值删除位置是pop()最值默认底层容器为vector。易错点一pop()只删除元素不返回被删除的值需要先通过top()或front()取值再pop()。易错点二三者都没有迭代器不能直接遍历只能通过各自的取元素接口逐个访问或不断取值加pop()的方式清空。面试高频细节问答Q1为什么 stack 和 queue 默认用 dequedeque 头尾增删 O (1)连续分段内存扩容开销优于 vectorstack 只用尾部queue 头尾都要用。vector 头部删除不行list 随机访问差、内存碎片多。Q2为什么 priority_queue 底层默认 vector堆是完全二叉树适合用连续数组存储下标计算父子节点很方便vector 连续内存缓存友好。Q3可以用 stack 遍历全部元素吗只能 toppop 依次拿拿出来就删掉如果想要保留数据要全部 pop 出来存到别的容器再装回去。Q4为什么 stack、queue 不提供迭代器设计目的是限制访问只暴露栈 / 队列接口保证 LIFO/FIFO 语义如果开放迭代器就可以随意修改中间元素破坏抽象。Q5空容器调用 top/front/back/pop 会抛异常吗不会抛异常标准规定是 UB这点和 Java 不一样Java 会抛异常。必须手动 empty 判断。