3.12顺序存储结构及其基本运算实现 利用一组地址连续的存储单元依次存放自 栈底到栈顶的数据元素; 在数组上实现时,栈底位置可以设置在数 组的任一个端点(通常设置在0下标处),而 栈顶是随着插入和删除而变化的,可以用 个整形变量top指示栈顶元素在顺序栈中的位 置 数据入栈或出栈时,整形变量top分别执行 加1或减1的操作
11 • 利用一组地址连续的存储单元依次存放自 栈底到栈顶的数据元素； • 在数组上实现时，栈底位置可以设置在数 组的任一个端点（通常设置在0下标处），而 栈顶是随着插入和删除而变化的，可以用一 个整形变量top指示栈顶元素在顺序栈中的位 置； • 数据入栈或出栈时，整形变量top分别执行 加1或减1的操作。 3.1.2 顺序存储结构及其基本运算实现
MaxSize=5 4 432 3210 dcba 321 432 cba (a)空栈()元素a入栈(o)元素b、c、d入栈(d元素d出栈 顺序栈进栈和出栈示意图 12
12 顺序栈进栈和出栈示意图
顺序栈的类型定义 tyl pede struct ElemType data Maxsize] Int top; /栈顶指针 Sqstack 采用栈指针的方式建立和使用顺序表 Sastack *s
13 顺序栈的类型定义 typedef struct { ElemType data[MaxSize]； int top； /*栈顶指针*/ } SqStack； • 采用栈指针的方式建立和使用顺序表 SqStack *s；
在顺序栈中实现栈的基本运算 (1)初始化栈 Initstack(s) 建立一个新的空栈s,实际上是将栈顶指针指向 1即可。 void InitStack(Sqstack*&s) s=(SqStack")malloc(sizeof(sqstack) >top=-1
14 (1) 初始化栈InitStack(s) 建立一个新的空栈s，实际上是将栈顶指针指向- 1即可。 void InitStack(SqStack *&s) { s=(SqStack *)malloc(sizeof(SqStack)); s->top=-1; } 在顺序栈中实现栈的基本运算
(2)销毁栈 DestroyStack(s) 释放栈s占用的存储空间。 void DestroyStack(sqstack *&s) free(s); 15
15 (2) 销毁栈DestroyStack(s) 释放栈s占用的存储空间。 void DestroyStack(SqStack *&s) { free(s); }