3.3 的顺序存储结构★2◎3

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