2.2 和队列的顺序存储结构

2.2 和队列的顺序存储结构

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

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

2.2.1 顺序栈

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

2.2 和队列的顺序存储结构