3.3 的顺序存储结构★2◎3
3.3 栈的顺序存储结构★2◎3
栈是线性表的一种，因此可以采用顺序结构存储。
1．栈顺序存储结构表示
一般来讲，我们采用数组结构来定义一个栈，如下定义了一个数据元素为Elemtype的顺序存储栈的例子：
其中采用整型top来描述栈顶指针，它指向下一个入栈元素的存储位置，以C语言为例，top的取值永远等于当前栈中的元素数，如表3-3所示。
表3-3 栈顶指针取值情况表
情 况 | 栈顶指针要求 | 栈中元素数 | 备 注 |
| 栈空 | top = 0 | 0 | |
| 栈满 | top = STACKMAXSIZE | STACKMAXSIZE | |
| 入栈元素存储位置 | Elem[top] | top | 栈未满时有效 |
| 出栈元素位置 | Elem[top-1] | top | 栈未空时有效 |
在以上结构中，栈的最多数据元素数为定值STACKMAXSIZE，数据元素数量不能随意增加，这是以数组方式描述栈的缺点。为了实现栈可变最大存储数据元素数，可以使用一个动态分配的数组来取代上面的固定长度数组，如下所示：
如果在栈满时（top = nStackSize）执行入栈操作，栈将自动增加分配STACKSTEP个数据元素存储空间，并修改nStackSize取值“nStackSize = nStackSize + STACKSTEP”，从而满足无限增加数据元素的要求。
2．有关栈的判断
（1）在C语言中，栈空判断为：“top == 0”。
（2）在C语言中，栈满判断为：“top == STACKMAXSIZE”或“top == nStackSize”。
（3）在C语言中，栈中元素数为：“top”。
3．入栈操作
栈的入栈操作过程可分为三个步骤：
①判断栈未满。
②将数组元素Elem[top]赋值为入栈元素。
③ top++。
以下代码实现栈S的入栈操作：
4．出栈操作
栈的出栈操作过程可分为三个步骤：
①判断栈未空。
②top–。
③返回数组元素Elem[top]。
以下代码实现栈S的出栈操作：
5．栈顺序存储结构的特点
（1）由于只在线性表尾执行读取、插入和删除操作，不用数据移动，因此其算法的时间复杂度为常数。
（2）需要一次性分配所需的存储空间，因此当线性表未到达最大数据元素数时浪费了存储空间。
因此以顺序结构存储的栈适用于数据元素总数固定、程序设计简单的应用中。
3.3 的顺序存储结构★2◎3