4.2. 特殊线性表：栈和队列

前一部分我们介绍了线性表的概念和两种通常的实现线性表的数据结构：顺序表和链表。它们是根据元素的物理存储结构来进行分类的。

本部分我们将介绍两种根据用法来特别区分的特殊线性表数据结构：栈和队列。这是计算机软件和算法里面极其重要的两种数据结构，在搜索算法、编译系统、操作系统等几乎所有计算机软件中都属于必不可缺的组件，大量高级算法都依赖于使用栈或者队列来实现。例如深度优先搜索就是利用栈实现了非递归化，而广度优先搜索则是使用了队列，再如计算机程序调用函数或子程序时利用栈来传递参数和保存状态。

事实上无论是栈还是队列还是任何它们的变种，本质上都还是线性表。它们都可以用前一部分学过的顺序表和链表来实现，比如用顺序表实现的栈通常就叫做栈，而用链表来实现的栈一般叫做链栈。事实上栈和队列只不过是元素存取方式受到特定规则限制的线性表。

在这一部分我们将学习栈和队列的基本概念，学习分别用顺序表和链表来自己实现最简单的栈和队列，学习它们的一些典型应用和例题，学习STL提供的栈和队列容器 stack 和 queue 的使用。至于优先级队列，我们留在学习堆这个数据结构的时候再进行介绍。

• 4.2.1. 栈：概念、stack容器和实现
  • 4.2.1.1. 栈的概念及基本操作
  • 4.2.1.2. STL栈容器stack
  • 4.2.1.3. 栈的编程实现
• 4.2.2. 栈的应用：表达式求值
  • 4.2.2.1. 前缀、中缀和后缀表达式
  • 4.2.2.2. 中缀表达式的分析算法
  • 4.2.2.3. 后缀表达式的生成算法
  • 4.2.2.4. 后缀表达式的计算算法
• 4.2.3. 队列：基本概念
  • 4.2.3.1. 顺序队列
  • 4.2.3.2. 环形队列
  • 4.2.3.3. 链式队列
• 4.2.4. 队列：C++实现、STL容器
  • 4.2.4.1. 链式队列的实现
  • 4.2.4.2. STL队列容器
  • 4.2.4.3. STL双头队列容器