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

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


3.3 栈的顺序存储结构★2◎3
  栈是线性表的一种,因此可以采用顺序结构存储。

  1.栈顺序存储结构表示

  一般…

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

    关于作者: admin

    这里可以再内容模板定义一些文字和说明,也可以调用对应作者的简介!或者做一些网站的描述之类的文字活着HTML!

    为您推荐

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    评论列表 人参与

    联系我们

    联系我们

    8888-88888888

    在线咨询: QQ交谈

    邮箱: email@admin.com

    工作时间:周一至周五,9:00-17:30,节假日休息

    关注微信
    微信扫一扫关注我们

    微信扫一扫关注我们

    关注微博
    返回顶部