教黎 栈和队列 程序设计—数据结构 基本概念及应用 3.1.2顺序栈 1、增量式顺序栈的定义 #define STACK INIT_SIZE 100 体存储空间的初始分配量*/ #define STACKINCREMENT 10 体存储空间的分配增量*/ typedef struct ElemType *base; /*栈底指针 ElemType *top, /*栈顶指针（栈顶元素的下一个位置）/ int stacksize; 体当前分配的存储容量制 SqStack; 1)和顺序表一样采用增量式的空间分配： 2)操作和栈顶相关： 插入操作（入栈）：将待插元素插入到栈顶元素的下一个位置： 删除操作（出栈）：删除栈顶元素： 取元素操作：取栈顶元素的值。 各操作的操作位置与栈顶元素的位置或其下一个位置相关，希望在O(1)时间内能获取 操作位置，故可设置专门的栈顶指针top。 3)约定：top指向栈顶元素的下一个位置（便于表示空栈）。 4)栈顶的初始化：S.top=S.base(在上述3)约定下的空栈形式) 5)栈空：S.base=S.top,栈满：S.top-S.base>=S.stacksize 6)入栈：S.top+=e,出栈：e=-S.top 注意：4)，5)，6)步受3)制约。约定不同，相应的判定和处理也不一样。 如假设top就指向栈顶元素，此时4)，5)，6)如何？ 2、取栈顶元素GetTop_Sq 1)算法设计 参数：顺序栈S、取得的栈顶元素&e 分析：由于top指向栈顶元素的下一个位置，因此实际的栈顶元素的位置应是top-1: 栈非空时，此操作有效。 算法1 Status GetTop Sq(SqStack S,Elem Type &e){ 体判断栈是否为空*/ if(S.base ==S.top)return ERROR; e=*(S.top-1); return OK: } 3、入栈操作Push_Sq 1)算法设计 参数：顺序栈&S、插入元素e 分析：插入位置为栈顶元素的下一个，无须判断位置的合法性： 上溢即栈满的条件需要判断，由于是增量式分配，故栈满时需要重新申请空间； 算法2 Status Push_Sq(SqStack &S,ElemType e ) 体判断栈是否为满*/ if (S.top-S.base >=S.stacksize ) 体栈满，追加空间/ 文档编号 完成时间 完成人张昱 修改时间 第3页程序设计——数据结构 栈和队列 基本概念及应用 文档编号 完 成 人 张 昱 完成时间 修改时间 第 3 页 3.1.2 顺序栈 1、增量式顺序栈的定义 #define STACK_INIT_SIZE 100 /* 存储空间的初始分配量 */ #define STACKINCREMENT 10 /* 存储空间的分配增量 */ typedef struct{ ElemType *base; /* 栈底指针 */ ElemType *top; /* 栈顶指针(栈顶元素的下一个位置) */ int stacksize; /* 当前分配的存储容量 */ }SqStack; 1）和顺序表一样采用增量式的空间分配； 2）操作和栈顶相关： 插入操作（入栈）：将待插元素插入到栈顶元素的下一个位置； 删除操作（出栈）：删除栈顶元素； 取元素操作：取栈顶元素的值。 各操作的操作位置与栈顶元素的位置或其下一个位置相关，希望在 O(1)时间内能获取 操作位置，故可设置专门的栈顶指针 top。 3）约定：top 指向栈顶元素的下一个位置（便于表示空栈）。 4）栈顶的初始化：S.top = S.base(在上述 3)约定下的空栈形式)， 5）栈空：S.base == S.top，栈满：S.top - S.base >= S.stacksize 6）入栈：*S.top ++ = e，出栈：e = *--S.top 注意：4), 5), 6)步受 3)制约。约定不同，相应的判定和处理也不一样。 如假设 top 就指向栈顶元素，此时 4),5),6)如何？ 2、取栈顶元素 GetTop_Sq 1) 算法设计 参数：顺序栈 S、取得的栈顶元素&e 分析：由于 top 指向栈顶元素的下一个位置，因此实际的栈顶元素的位置应是 top -1； 栈非空时，此操作有效。 算法 1 Status GetTop_Sq(SqStack S, ElemType &e){ /* 判断栈是否为空 */ if ( S.base == S.top) return ERROR; e = *( S.top -1); return OK; } 3、入栈操作 Push_Sq 1) 算法设计 参数：顺序栈&S、插入元素 e 分析：插入位置为栈顶元素的下一个，无须判断位置的合法性； 上溢即栈满的条件需要判断，由于是增量式分配，故栈满时需要重新申请空间; 算法 2 Status Push_Sq( SqStack &S, ElemType e ){ /* 判断栈是否为满 */ if ( S.top – S.base >= S.stacksize ){ /* 栈满，追加空间 */