深入解剖STL Stack/Queue：配接器模式的容器变奏与源码探秘

❤️@燃于AC之乐 来自重庆 计算机专业的一枚大学生
✨专注 C/C++ Linux 数据结构 算法竞赛 AI
🏞️志同道合的人会看见同一片风景！

👇点击进入作者专栏：

《算法画解》 ✅

《linux系统编程》✅

《C++》 ✅

🌟《算法画解》算法相关题目点击即可进入实操🌟
感兴趣的可以先收藏起来，请多多支持，还有大家有相关问题都可以给我留言咨询，希望希望共同交流心得，一起进步，你我陪伴，学习路上不孤单！

文章目录

• 前言
  • 1. stack 概述
  • 2. stack 定义完整列表
  • 3. stack 没有迭代器
  • 4. 以 list 作为 stack 的底层容器
  • 5. queue 概述
  • 6. queue 定义完整列表
  • 7. queue 没有迭代器
  • 8. 以 list 作为 queue 的底层容器

前言

今天这篇，是初阶之旅的最后一站：stack与queue。它们看似简单，却是“配接器”思想的精华体现——用已有的容器，演绎出全新的行为逻辑。没有迭代器，因为无需遍历；只有push/pop，因为纯粹即是力量。
源码很短，短到令人惊讶；思想很深，深到值得回味。
如果你也喜欢这种“挖到底”的爽感，不妨点个收藏，这个系列我会持续更新。从初阶到进阶，从容器到算法，从使用到造轮——我们一起，见天地，见源码，见自己。

现在，让我们走进stack与queue的四十行代码世界。看它们如何用最少的语句，讲述最深刻的道理。

1. stack 概述

stack 是一种**先进后出（FILO）**的数据结构，只有一个出口，形式如图所示。stack 允许新增元素、移除元素、取得最顶端元素，但除了最顶端外，没有任何其它方法可以存取 stack 的其它元素，不允许遍历行为。

• 将元素推入 stack：push
• 将元素推出 stack：pop

stack 是一种 adapter（配接器），通常不被归类为 container，而是 container adapter。

2. stack 定义完整列表

stack 通常以 deque 作为底层容器，通过封闭其头端开口实现 FILO 特性。

template<classT,classSequence= deque<T>>classstack{friendbooloperator==(__STL_NULL_TMPL_ARGS(const stack&,const stack&));friendbooloperator<(__STL_NULL_TMPL_ARGS(const stack&,const stack&));public:typedeftypenameSequence::value_type value_type;typedeftypenameSequence::size_type size_type;typedeftypenameSequence::reference reference;typedeftypenameSequence::const_reference const_reference;protected: Sequence c;// 底层容器public:boolempty()const{return c.empty();} size_type size()const{return c.size();} reference top(){return c.back();} const_reference top()const{return c.back();}voidpush(const value_type& x){ c.push_back(x);}voidpop(){ c.pop_back();}};template<classT,classSequence>booloperator==(const stack<T, Sequence>& x,const stack<T, Sequence>& y){return x.c == y.c;}template<classT,classSequence>booloperator<(const stack<T, Sequence>& x,const stack<T, Sequence>& y){return x.c < y.c;}

3. stack 没有迭代器

stack 所有元素的进出都必须符合“先进后出”的条件，只有 stack 顶端的元素才有机会被外界取用。stack 不提供遍历功能，也不提供迭代器。

4. 以 list 作为 stack 的底层容器

除了 deque，list 也可作为底层容器。只要实现 empty()、size()、back()、push_back()、pop_back() 即可。

// file : 4stack-test.cpp#include<stack>#include<list>#include<iostream>#include<algorithm>usingnamespace std;intmain(){ stack<int, list<int>> s1stack; s1stack.push(1); s1stack.push(3); s1stack.push(5); s1stack.push(7); cout << s1stack.size()<< endl;// 4 cout << s1stack.top()<< endl;// 7 s1stack.pop(); cout << s1stack.top()<< endl;// 5 s1stack.pop(); cout << s1stack.top()<< endl;// 3 s1stack.pop(); cout << s1stack.top()<< endl;// 1 cout << s1stack.size()<< endl;// 1}

5. queue 概述

queue 是一种**先进先出（FIFO）**的数据结构，有两个出口。queue 允许新增元素、移除元素、从最底端加入元素、取得最顶端元素，但除了底端可加入、顶端可取出外，不允许其他存取方式，不允许遍历行为。

• 将元素推入 queue：push
• 将元素推出 queue：pop

queue 也是一种 adapter（配接器），通常不被归类为 container，而是 container adapter。

6. queue 定义完整列表

queue 通常以 deque 作为底层容器，通过封闭其底端出口和前端入口实现 FIFO 特性。

template<classT,classSequence= deque<T>>classqueue{friendbooloperator==(__STL_NULL_TMPL_ARGS const queue& x,const queue& y);friendbooloperator<(__STL_NULL_TMPL_ARGS(const queue& x,const queue& y);public:typedeftypenameSequence::value_type value_type;typedeftypenameSequence::size_type size_type;typedeftypenameSequence::reference reference;typedeftypenameSequence::const_reference const_reference;protected: Sequence c;// 底层容器public:boolempty()const{return c.empty();} size_type size()const{return c.size();} reference front()const{return c.front();} const_reference front()const{return c.front();} reference back()const{return c.back();} const_reference back()const{return c.back();}voidpush(const value_type& x){ c.push_back(x);}voidpop(){ c.pop_front();}};template<classT,classSequence>booloperator==(const queue<T, Sequence>& x,const queue<T, Sequence>& y){return x.c == y.c;}template<classT,classSequence>booloperator<(const queue<T, Sequence>& x,const queue<T, Sequence>& y){return x.c < y.c;}

7. queue 没有迭代器

queue 所有元素的进出都必须符合“先进先出”的条件，只有 queue 顶端的元素才有机会被外界取用。queue 不提供遍历功能，也不提供迭代器。

8. 以 list 作为 queue 的底层容器

除了 deque，list 也可作为 queue 的底层容器。需支持 empty()、size()、front()、back()、push_back()、pop_front() 等操作。

// file: 4queue-test.cpp#include<queue>#include<list>#include<iostream>#include<algorithm>usingnamespace std;intmain(){ queue<int, list<int>> iqueue; iqueue.push(1); iqueue.push(3); iqueue.push(5); iqueue.push(7); cout << iqueue.size()<< endl;// 4 cout << iqueue.front()<< endl;// 1 iqueue.pop(); cout << iqueue.front()<< endl;// 3 iqueue.pop(); cout << iqueue.front()<< endl;// 5 iqueue.pop(); cout << iqueue.front()<< endl;// 7 iqueue.pop(); cout << iqueue.front()<< endl;// 1 cout << iqueue.size()<< endl;// 1}

加油！志同道合的人会看到同一片风景。
看到这里请点个赞，关注，如果觉得有用就收藏一下吧。后续还会持续更新的。 创作不易，还请多多支持！