结合源码浅谈栈和队列
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
今天我们进入下一个章节，来看看栈和队列。
栈和队列是我们日常使用频率非常高的数据结构，广泛应用在各种问题和场景当中。并且它们的原理相对来说比较简单，并且有一定的相似之处，所以合并到一起来介绍。
栈
栈，英文是stack。这里我个人感觉只是信雅达的翻译，大家不能机械地联想栈道之类的东西。毕竟栈道虽然窄也是一个通道，两头都可以进出。而数据结构中的栈，它的定义是只有一头可以进出的数据结构。大家结合下图不难想明白，既然只有一头可以进出，那么先进栈的元素想要出栈就只能等它之后的所有元素都出栈才行。
这就是为什么我们说栈是先进后出的，这里指的就是元素的进出顺序。
栈的原理本身并不复杂，只有这一个特性。所以在实现的时候也没有太多的限制，只需要保证只有一头可以进出元素即可。常见的有基于deque,vector，list等，这些数据结构的更底层是数组和链表。
由于标准的栈结构只提供push，pop等接口，不提供迭代器。所以我们不能遍历栈中的元素，只能通过弹出的方式访问。因此栈不被视作是容器，而是container adapter（容器适配器）。
这里我建议可以直接阅读STL的源码，虽然使用了模板类以及一些宏，但整体上不影响我们阅读逻辑。
废话不多说，我们直接上源码：
template <class _Tp, class _Sequence>
class stack {
// requirements:
__STL_CLASS_REQUIRES(_Tp, _Assignable);
__STL_CLASS_REQUIRES(_Sequence, _BackInsertionSequence);
typedef typename _Sequence::value_type _Sequence_value_type;
__STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type);
//关系运算符重载，定义为友元函数，是必要的
#ifdef __STL_MEMBER_TEMPLATES //定义了成员模板函数宏
template <class _Tp1, class _Seq1>
friend bool operator== (const stack<_Tp1, _Seq1>&,
const stack<_Tp1, _Seq1>&);
template <class _Tp1, class _Seq1>
friend bool operator< (const stack<_Tp1, _Seq1>&,
const stack<_Tp1, _Seq1>&);
#else /* __STL_MEMBER_TEMPLATES */
friend bool __STD_QUALIFIER
operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
friend bool __STD_QUALIFIER
operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
#endif /* __STL_MEMBER_TEMPLATES */
public:
//型别定义
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
protected:
_Sequence c; //底层序列容器成员变量
public:
stack() : c() {} //构造器
explicit stack(const _Sequence& __s) : c(__s) {}
bool empty() const { return c.empty(); } //判断栈是否为空
size_type size() const { return c.size(); } //返回栈中元素个数
reference top() { return c.back(); } //访问栈顶元素
const_reference top() const { return c.back(); } //访问栈顶元素，const函数
void push(const value_type& __x) { c.push_back(__x); } //压栈
void pop() { c.pop_back(); } //出栈
};
template <class _Tp, class _Seq>
bool operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) //重载==运算符
{
return __x.c == __y.c;
}
template <class _Tp, class _Seq>
bool operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) //重载<运算符
{
return __x.c < __y.c;
}
#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER //定义了类成员函数到非成员函数传递宏
template <class _Tp, class _Seq>
bool operator!=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) //重载!=运算符
{
return !(__x == __y);
}
template <class _Tp, class _Seq>
bool operator>(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
{
return __y < __x;
}
template <class _Tp, class _Seq>
bool operator<=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
{
return !(__y < __x);
}
template <class _Tp, class _Seq>
bool operator>=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y)
{
return !(__x < __y);
}
#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
这一大段代码主要都是声明以及运算符的重载，真正的核心逻辑只有中间的一小段。我把它截出来，就很明显了。
可以看到像是size(),top(), push(), pop()这些函数都是直接调用的模板类实现的，而不是另外实现的。常用的C++ STL的stack是基于deque实现的，不论是deque还是vector都提供push_back(), pop_back(), back(), size()等函数，因此我们可以直接调用，这也是面向对象的优势之一。
队列
队列，即queue。它和现实中的队列比较类似，体现在一头进一头出。和栈一样，队列这个数据结构也基本只有这一个特性。我们可以参考一下下图，不过下图是基于链表实现的，队列的实现方式并不仅仅只有链表，但的确使用链表更加适合。
普通队列只能在队尾插入元素，队首弹出元素。所以先进入队列的元素也先出队列，这被称作先进先出。还有一种队列，队列的两端都可以插入、弹出元素，这种被称为双端队列，即deque。
C++中STL的队列基于list即链表实现，因为链表比较方便自由删除头部的元素。但实际上通过使用循环数组等方式，基于vector或者是array也是可以的，只不过实现上会稍微麻烦一些。
我们来看下STL中的源码：
template <class _Tp,
class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(deque<_Tp>) > //默认以deque实现
class queue;
template <class _Tp, class _Sequence>
class queue {
// requirements:
__STL_CLASS_REQUIRES(_Tp, _Assignable);
__STL_CLASS_REQUIRES(_Sequence, _FrontInsertionSequence);
__STL_CLASS_REQUIRES(_Sequence, _BackInsertionSequence);
typedef typename _Sequence::value_type _Sequence_value_type;
__STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type);
#ifdef __STL_MEMBER_TEMPLATES
template <class _Tp1, class _Seq1>
friend bool operator== (const queue<_Tp1, _Seq1>&,
const queue<_Tp1, _Seq1>&);
template <class _Tp1, class _Seq1>
friend bool operator< (const queue<_Tp1, _Seq1>&,
const queue<_Tp1, _Seq1>&);
#else /* __STL_MEMBER_TEMPLATES */
friend bool __STD_QUALIFIER
operator== __STL_NULL_TMPL_ARGS (const queue&, const queue&);
friend bool __STD_QUALIFIER
operator< __STL_NULL_TMPL_ARGS (const queue&, const queue&);
#endif /* __STL_MEMBER_TEMPLATES */
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
protected:
_Sequence c; //底层容器
public:
queue() : c() {}
explicit queue(const _Sequence& __c) : c(__c) {}
//以下完全利用_Sequence c的操作，完成queue的操作
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference front() { return c.front(); }
const_reference front() const { return c.front(); }
reference back() { return c.back(); }
const_reference back() const { return c.back(); }
void push(const value_type& __x) { c.push_back(__x); }
void pop() { c.pop_front(); }
};
template <class _Tp, class _Sequence>
bool
operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
{
return __x.c == __y.c;
}
template <class _Tp, class _Sequence>
bool
operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
{
return __x.c < __y.c;
}
#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
template <class _Tp, class _Sequence>
bool
operator!=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
{
return !(__x == __y);
}
template <class _Tp, class _Sequence>
bool
operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
{
return __y < __x;
}
template <class _Tp, class _Sequence>
bool
operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
{
return !(__y < __x);
}
template <class _Tp, class _Sequence>
bool
operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
{
return !(__x < __y);
}
和栈一样，这段代码当中大部分是模板类的声明以及运算符的重载，真正核心的代码只有中间的一小部分：
我们对照一下栈的代码，会发现这几个函数的实现几乎是完全一样的，唯一的一点小差异在于这里的pop，调用的是c.pop_front()，而栈中调用的是c.pop_back()。从字面上我们就能感受到，一个是从头部弹出元素，一个是从尾部，这也是队列和栈逻辑上的差异所在。
和栈一样，队列同样不提供迭代器接口，不允许我们直接遍历队列中的元素。也因此，队列同样是容器适配器，而非容器。
这两个数据结构在算法当中的应用非常广泛，但很多书本上的介绍却很浅薄，我个人认为这不太合适。作为学习者，我们不仅要知其然，更要知其所以然，了解原理也要了解细节，这样在使用的时候才能更加得心应手，体会和认知才更深刻。
关于栈和队列就聊到这里，感谢大家的阅读，如果喜欢的话，恳请帮忙转发扩散。算法学习之旅，与你同行。