数据结构之栈

第三章 栈和队列

3.1栈

3.1.1 抽象数据类型栈的定义

3.1.2 栈的表示和实现

3.2 栈的应用举例（具体的应用参看书中讲解）

3.2.1 数值转换

3.2.2 括号匹配检测

3.2.3 行编辑程序

3.2.4 迷宫求解

3.2.5 表达式求值

**3.3 栈与递归的实现

3.4 队列

3.4.1 抽象的数据类型

3.4.2 链队列---队列的链式表示和实现

3.4.3 循环队列---队列的顺序表示和实现

3.1栈

3.1.1 抽象数据类型栈的定义

栈，是限定在仅在队尾进行插入或删除操作的线性表，因此对于栈来说，表尾端有其特殊含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。

栈的特点是：

1. 它是一个线性表

2. 对于这个线性表只能在栈顶进行操作

所以从抽象数据类型的角度来看，数据对象，数据关系与线性表相同，只是在基本操作有了一些限制，同时添加了一些新的操作函数

小提醒

对于初学者来说，可以把抽象数据类型中的基本操作当做是一些函数对于数据对象的操作，但是在熟练掌握这些数据结构之后，对于数据结构中某些函数操作是有其固定名称的，例如，对于 栈 来说 出栈,入栈 就代表相应的函数操作或者说数据操作。

3.1.2 栈的表示和实现

和线性表类似，栈也有两种存储表示方法。

1

顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设 指针 top 指示栈顶元素在顺序栈中的位置

通常的习惯做法是 以top=0 表示空栈，鉴于C语言中的数组的下标约定从0开始，则当以C做描述语言时，如此设定会带来很大的不便；

另一方面，由于栈在使用过程中所需最大空间的大小很难估计，因此，一般来说，在初始化设空栈时不应设定栈的最大容量。

一个较合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时在逐段扩大。具体的使用看代码部分，有详细的注解

具体程序见后图！！！！

顺序栈的示意图

2

链栈，栈的链式表示--由于栈的操作是线性表操作的特例，书中没有给出程序（如果大家需要会作补充，可以参看线性表的头插法）。

链栈的示意图

顺序栈程序

程序框可以左右滑动哦~

执行结果：