搜索
第3章栈和队列-栈数据结构讲义信息工程学院魏洪涛Email:greattide@163.com3.1栈（stack）一、栈的定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈的基本操作1.初始化栈：IniStack(&S)将栈S置为一个空栈(不含任何元素)。2.进栈：Push(&S,X)将元素X插入到栈S中，也称为“入栈”、“插入”、“压入”。3.出栈：Pop(&S,&e)删除栈S中的栈顶元素，也称为”退栈”、“删除”、“弹出”。4.取栈顶元素：GetTop(S,&e)取栈S中栈顶元素。5.判栈空：StackEmpty(S)判断栈S是否为空，若为空，返回值为true，否则返回值为false。栈的操作演示注意这两个操作的区别问题一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，只需压入一个立即弹出一个即可。【定理】假定有n个元素1,2,…,n,它们按1,2,…,n的次序进栈，那么出栈构成的排列满足下列规律：该排列中，对任意元素k,若它后面有小于它的元素，则这些小于它的元素必须以逆序出现。出栈规律只须证明，若借助栈由输入序列(1,2,…,n)得到输出序列(p1,p2,…,pn)，那么在输出序列中，不可能出现这种情况：存在ijk，使pjpkpi.这里(p1,p2,…,pn)是(1,2,…,n)的一个全排列，每个元素只能按1,2,…,n的次序进一次栈。参见清华齐德昱版《数据结构与算法》P95提示ijk说明进栈顺序为(…i…j…k…),它们的出栈排列只有6种可能：①ijk,②ikj,③kij,④kji,⑤jik,⑥jki栈的应用：数制转换如十进制数N转换成d进制数C：N=cndn+cn-1dn-1+…+c1d1+c0C=(cncn-1…c0)例如：(14)10=1*23+1*22+1*21+0=(1110)2(1348)10=2*83+5*82+0*81+4=(2504)8(1348)10=2*83+5*82+0*81+4=(2504)8nndiv8nmod8134816841682102125202最后得到的“2”最先输出：2504数制转换程序VoidConversion(){IniStack(S);//构造空栈Scanf(“%d”,N);While(N){Push(S,N%8);//如果是转换成M进制数，将8换成N=N/8;//M即可}While(!StackEmpty(S)){Pop(S,e);printf(“%d”,e);}}栈的应用：迷宫求解东南西北（顺时针）演示求迷宫中一条路径的算法的基本思想是：若当前位置可通，则纳入当前路径，并继续朝下一位置“探索；若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道块，然后朝着除来向之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓下一位置指的是当前位置四周四个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块。纳入路径的操作即为当前位置入栈；从当前路径上删除前一通道块的操作即为出栈。迷宫求解策略栈的顺序实现方法一：顺序栈的静态数组实现#defineStackSize100typedefstruct{ElemTypedata[StackSize];inttop;}SqStack;顺序栈的操作演示方法二：顺序栈的动态数组实现#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{ElemType*base;ElemType*top;intstacksize;}SqStack;栈空：top=-1栈满：top=StackSize-1约定base为栈底指针，Top为栈顶指针指。顺序栈的图示topstacksize-1nn-1n-210anan-1a2a1栈空：栈满：Top=baseTop-base=stacksizebase注意：非空栈中的栈顶指针top总是在栈顶元素的下一个位置。top指向栈顶的上一个元素。top==base表示空栈。top-base=StackSize表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢一般是正常现象，常常用来作为程序控制转移的条件。顺序栈示例代码当一个程序中同时使用多个顺序栈时，为了防止上溢错误，需要为每个栈分配一个较大的空间，但是在某一栈发生上溢的同时，可能其余的栈未用的空间却很多，如果我们将这多个栈安排在一个向量里，即让多个栈共享存储空间，就可相互调节余缺。顺序栈的共享单元顺序栈的共享单元将两个栈配对放在一个向量里，两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。这样当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。栈1栈2栈1顶栈2顶栈1底栈2底………栈的链式实现typedefstructNode{ElemTypeelem;structNode*next;}SNode;可附加一个头节点。插入和删除仅在头节点处进行。没有栈满的限制。链栈示例代码ch3_lstack.c可以看到，主函数和顺序栈时的ch3_sstack.c一模一样。即逻辑结构完全相同，存储结构不同而已。作业1、对于一个栈，给出输入项A、B、C，如果输入项序列由ABC组成，试给出所有可能的输出序列。2、如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？3、设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，b