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