2.2 和队列的顺序存储结构




2.2 和队列的顺序存储结构

2.2 栈和队列的顺序存储结构

  栈和队列的顺序存储结构是线性表的顺序存储结构的特殊形式,具有顺序存储线性表的一些基本特征,同时,又具有其本身的一些特殊性质。

2.2.1 顺序栈

  顺序栈就是使用顺序存储结构实现的栈,它使用一组地址连续的存储单元依次从栈底到栈顶存放数据元素。
  1.顺序栈的生成方式
  栈的生成方式是指栈在存储空间中的实现方法,按栈顶指针和栈底位置的指示不同分为以下两种。
  ① 向下生成的栈:栈顶在高地址端,栈底在低地址端。
  ② 向上生成的栈:栈顶在低地址端,栈底在高地址端。
  2.顺序栈的存储结构
  顺序栈的存储结构既可以采用静态数组,也可以采用动态数组。
  ① 静态数组定义栈。定义一个数据元素为Elemtype的顺序存储栈的例子如下:
  
  ② 动态数组定义栈。在以上结构中,栈的最多数据元素个数为定值Maxsize,数据元素的数量不能随意增加,这是静态数组描述栈的缺点。为了实现可变的存储数据元素数,可以参考线性表的静态存储方式,使用一个动态分配的数组来取代上述固定长度数组,如下所示:
  
  3.顺序栈的操作
  顺序栈的操作继承了线性表的基本操作,但又有其特殊性。基本操作有初始化、判空栈、入栈、出栈和取栈顶元素等。
  ① 初始化栈算法。初始化一个栈就是建立栈空间,其算法思想是:先申请栈存储空间,然后将栈底和栈顶指针都指向栈的第一个单元。算法描述如下:
  
  ② 判空栈算法。判断一个栈是否为空的条件是“S.top=S.base”,算法很简单,直接返回表达式“S.top= =S.base”的值即可。
  
  ③ 入栈算法。入栈前必须先判断栈是否满,若已满,可以重新申请栈存储空间,若申请失败,应返回出错信息。算法描述如下:
  
  ④ 出栈算法。出栈前必须先判断栈是否为空,若已空,则返回错误信息。算法描述如下:
  
  ⑤ 取栈顶元素算法。取栈顶元素时应先判断栈是否空,若空,则返回出错信息。算法描述如下:
  

2.2 和队列的顺序存储结构

发表评论

Contact

北京考研中心大厦

Connect

Subscribe

最新考研资料,欢迎联系博主获取。