数据结构第四章栈.pptx

第四章 栈主要内容定义栈的表示和实现顺序栈链栈栈 ( Stack )只允许在线性表的一端进行插入和删除允许插入和删除的一端 称为栈顶(top)，另一 端称为栈底(bottom)。特点 后进先出 (LIFO)退栈进栈topanan-1?a1bottom课堂习题设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列____。A．A, B, C, D, E B．B, C, D, E, AC．E, A, B, C, D D．E, D, C, B, A 5 4 3 2 1 0EDCDBCEBAABCEDA-1 课堂习题二设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push后，输出序列是_________。2，3，5，4，154231常用的栈运算ADT Stack { 数据元素:可以是任意类型的数据，但必须属于同一个数据对象 结论关系：栈中数据元素之间是线性关系 基本操作： InitStack(S);//将S初始化为空栈Push(S,x);//进栈Pop(S,x);//出栈……}栈的表示和实现顺序栈链栈用数组实现栈数组elem存储栈元素elem[0]为最早入栈的元素，即为数组的底部数组向下标增大方向扩展栈底elem[0]0 1 2 3 4 5 6 7 8 9 　Stack_Size elemconst STACK_INIT_SIZE=100;const STACKINCREMENT=10;typedef struct { SElemType *elem; int top; /*栈顶位置(下标),top=-1时，表示空栈*/ int stacksize; //int incrementsize;}SqStack; 栈底elem[0]栈顶elem[top]0 1 2 3 4 5 6 7 8 9 　Stack_Size elemtop (栈空)//初始化一个空的顺序栈void InitStack_Sq ( SqStack *S, int maxsize=STACK_INIT_SIZE, int incresize=STACKINCREMENT) { S-elem=new SElemType[maxsize]; S-top = -1; S-stacksize=incresize; //S-incrementsize=incresize;}//进栈--若栈满则结束, 否则新元素 e进栈void Push_Sq (SqStack ＊S, SElemType e) { if (S-top == S-stacksize-1) return; S-top++; S-elem[S-top] = e; //加入新元素}//出栈--删除栈顶元素bool Pop(SqStack *S, SElemType *e) {//将栈S的栈顶元素弹出，放到e所指的存储空间中 if( S-top ==－1) return FALSE; *e= S-elem[S-top]; S-top--; return TRUE;}//读栈顶元素int GetTop_Sq (SqStack S, SElemType *e) {//将栈S的栈顶元素弹出，放到e所指的存储空间中//但栈顶指针保持不变 if( S-top ==－1) return FALSE; *e=S-elem[S-top]; return TRUE;}栈的应用非常广泛，经常会出现在一个程序中需要同时使用多个栈的情况若使用顺序栈，会因为对栈空间难以估计而产生有的栈溢出、有的栈空间还很空闲的情况。解决方案：让多个栈共享一个足够大的数组空间最常用的是两个栈的共享技术－－双端栈双栈共享一个栈空间0M-10 n-1Stack　top[0] top[1]两个栈共享一个数组空间Stack[0:M-1]两栈栈底分别放在一维数组的两端,分别是0和M-1两个栈顶动态变化初始情况：top[0] =-1, top[1] = M 栈满条件：top[0]+1 == top[1] //两个栈顶指针相遇用指针实现栈— 链(式)栈栈顶栈底Sana10an-1栈顶栈底Sana10an-1插入与删除仅在栈顶处执行即：在链表的表头进行！链表的表头指针就作为栈顶指针链(式)栈的定义栈顶栈底Sana10an-1栈顶栈底Sana10an-1typedef LinkList LinkStack