栈和队列

本文主要是介绍栈和队列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

栈和队列都是以deque为底层容器的适配器。栈（stack）、队列（queue）、优先队列（priority_queue）这三种数据结构，准确的来说其实是一种适配器，因为底层都是以其他容器为基准。

栈：先入后出，只允许在栈顶添加和删除元素，称为入栈和出栈。

队列：先入先出，载队首取元素，在队尾添加元素，称为出队和入队。

优先队列：带权值的队列。

常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现，深度优先遍历DFS等。

从源码中，可以证实stack和queue底层确实是使用deque作为底层容器封装。

stack源码：

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = deque<T> >
#else
template <class T, class Sequence>
#endif
class stack {
public:
  typedef typename Sequence::value_type value_type;
  typedef typename Sequence::size_type size_type;
  typedef typename Sequence::reference reference;
  typedef typename Sequence::const_reference const_reference;
protected:
  Sequence c;

queque源码

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = deque<T> >
#else
template <class T, class Sequence>
#endif
class queue {
public:
  typedef typename Sequence::value_type value_type;
  typedef typename Sequence::size_type size_type;
  typedef typename Sequence::reference reference;
  typedef typename Sequence::const_reference const_reference;
protected:
  Sequence c;

这篇关于栈和队列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！