|
|
|
|
栈（Stack）是一种特殊的线性表，是限定仅在表尾进行插入或者删除操作的线性表。进行插入和删除的那一端称为栈顶（top），另一端称为栈底（bottom）。栈的插入操作和删除操作也分别简称进栈和出栈。
|
|
|
|
如果栈中有n个结点｛k0，k1，k2，…, kn-1｝，k0为栈底，kn-1是栈顶，则栈中结点的进栈顺序为k0, k1, k2，…，kn-1，而出栈的顺序为kn-1, kn-2，…, k1,k0，如下图所示。
|
|
|
|
|
|
|
|
栈的主要操作是桟的初始化、插入和删除运算、判断栈是否为空以及读取栈顶结点的值等操作。栈的类型的描述如下：
|
|
|
|
|
|
和顺序表类似，栈的实现方式一般也有两种：顺序存储和链式存储。下面主要介绍顺序栈。由于栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制，使得它们仅能在顺序表的同一端进行，所以同顺序表一样也可用一维数组表示。一般地，可以设定一个足够大的一维数组存储栈，数组中下标为0的元素就是栈底，对于栈顶，可以设一个指针top指示它。为了方便，设定top所指的位置是下一个将要插入的结点的存储位置，这样，当top=0时就表示是一个空的栈。一个栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关系如下图所示。
|
|
|
|
|
|
|
|
|
|
|
|
顺序存储栈的几个基本操作的具体实现，具体如下所示：
|
|
|
|
|
|
|
|
|
|
|
|
