数据结构与算法课程数据结构03

S.top

S.base S.stacksize

n n-1 i-1 i-2 1 0

an ai ai-1 a2 a1 STACK_INIT_SIZE 顺序栈的图示

3. 顺序栈基本操作的算法

1）初始化操作InitStack_Sq((SqStack &S) 参数：S是存放栈的结构变量； 功能：建一个空栈S；

算 法 Status InitStack_Sq(SqStack &S) { //构造一个空栈S S.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType)); //为顺序栈动态分配存储空间 if (! S. base) exit(OVERFLOW); //存储分配失败 S.top=S.base;

S.stacksize=STACK_INIT_SIZE; return OK;

初始化操作演示 }//InitStack_Sq

S.top S.base

n n-1 i-1 i-2 1 0

STACK_INIT_SIZE S.stacksize

初始化操作图示

2） 销毁栈操作 DestroyStack_Sq(SqStack &S ) 功能：销毁一个已存在的栈;

算 法 Status DetroyStack_Sq ( SqStack &S) {

if (!S.base) return ERROR; // 若栈未建立（尚未分配栈空间） free (S.base); // 回收栈空间 S.base = S.top = null; S.stacksize = 0; return OK; }// DetroyStack_Sq

S.top

S.base

n n-1 i-1 i-2 1 0

an ai ai-1 a2 a1 STACK_INIT_SIZE S.top =null S.base =null S.stacksize 0 销毁后

S.stacksize

销毁前

销毁栈操作图示