Java教程

栈和队列

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

栈和队列都是以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;
这篇关于栈和队列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!