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