《零基础学数据结构-第4章-栈》由会员分享，可在线阅读，更多相关《零基础学数据结构-第4章-栈（68页珍藏版）》请在金锄头文库上搜索。
1、第4章 栈,栈是一种操作受限的线性表。栈具有线性表的结构特点，即每一个元素只有一个前驱元素和后继元素（除了第一个元素和最后一个元素外），但它只允许在表的一端进行插入和删除操作。本章重点和难点：1、栈的顺序表示与算法实现2、栈的链式表示与算法实现3、求算术表达式的值4、迷宫求解问题5、递归的消除,4.1 栈的定义与抽象数据类型,4.1.1 什么是栈栈（stack），也称为堆栈，它是限定仅在表尾进行插入和删除操作的线性表。对栈来说，表尾（允许操作的一端）称为栈顶（top），另一端称为栈底（bottom）。栈顶是动态变化的，它由一个称为栈顶指针（top）的变量指示。当表中没有元素时，称为空栈。栈的插
2、入操作称为入栈或进栈，删除操作称为出栈或退栈。,4.1 栈的定义与抽象数据类型,在栈S=(a1,a2,an)中，a1称为栈底元素，an称为栈顶元素，由栈顶指针top指示。栈中的元素按照a1，a2，an的顺序进栈，当前的栈顶元素为an。如图4.1所示。最先进栈的元素一定是栈底元素，最后进栈的元素一定是栈顶元素。每次删除的元素是栈顶元素，也就是最后进栈的元素。因此，栈是一种后进先出（last in first out，简称LIFO）的线性表。,4.1 栈的定义与抽象数据类型,若将元素a、b、c和d依次入栈，最后将栈顶元素出栈，栈顶指针top的变化情况如图4.2所示。,4.1 栈的定义与抽象数据类型
3、,4.1.2 栈的抽象数据类型1数据对象集合栈的数据对象集合为a1，a2，an，每个元素都有相同的类型DataType。栈中数据元素之间是一对一的关系。栈具有线性表的特点：除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。,4.1 栈的定义与抽象数据类型,2基本操作集合（1）InitStack(&S)：初始化操作，建立一个空栈S。（2）StackEmpty(S)：若栈S为空，返回1，否则返回0。（3）GetTop(S,&e)：返回栈S的栈顶元素给e。（4）PushStack(&S,e)：在栈S中插入元素e，使其成为新的栈顶元素
4、。（5）PopStack(&S,&e)：删除栈S的栈顶元素，并用e返回其值。（6）StackLength(S)：返回栈S的元素个数。（7）ClearStack(S)：清空栈S。,4.2 栈的顺序表示与实现,4.2.1 栈的顺序存储结构采用顺序存储结构的栈称为顺序栈。顺序栈是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，可利用C语言中的数组作为顺序栈的存储结构，同时附设一个栈顶指针top，用于指向顺序栈的栈顶元素。当top=0时表示空栈。栈的顺序存储结构类型描述如下：#define StackSize 100typedef structDataType stackStackSize;
5、int top;SeqStack;,4.2 栈的顺序表示与实现,当栈中元素已经有StackSize个时，称为栈满。如果继续进栈操作则会产生溢出，称为上溢。对空栈进行删除操作，称为下溢。顺序栈的结构如图4.3所示。元素a、b、c、d、e、f、g、h依次进栈后，a为栈底元素，h为栈顶元素。在实际操作中，栈顶指针指向栈顶元素的下一个位置。顺序栈涉及的一些基本操作如下：（1）在初始化栈时，将栈顶指针置为0，即令S.top=0。（2）判断栈空条件为S.top=0，栈满条件为S.top=StackSize-1。（3）栈的长度（即栈中元素个数）为S.top。（4）进栈操作时，先判断栈是否已满，若未满，将元素
6、压入栈中，即S.stackS.top=e，然后使栈顶指针加1，即S.top+。出栈操作时，先判断栈是否为空，若为空，使栈顶指针减1，即S.top-，然后元素出栈，即e=S.stackS.top。,4.2 栈的顺序表示与实现,4.2.2 顺序栈的基本运算 （1）初始化栈。 void InitStack(SeqStack *S) /*初始化栈*/ S-top=0; /*把栈顶指针置为0*/ （2）判断栈是否为空。 int StackEmpty(SeqStack S) /*判断栈是否为空，栈为空返回1，否则返回0*/ if(S.top=0) /*如果栈顶指针top为0*/return 1; /*返回
7、1*/else /*否则*/return 0; /*返回0*/ ,4.2 栈的顺序表示与实现,（3）取栈顶元素。int GetTop(SeqStack S, DataType *e) if(S.toptop=StackSize) /*如果栈已满*/printf(“栈已满，不能将元素进栈！n”);return 0;else /*否则*/S-stackS-top=e; /*元素e进栈*/S-top+; /*修改栈顶指针*/return 1;,4.2 栈的顺序表示与实现,（5）将栈顶元素出栈。int PopStack(SeqStack *S,DataType *e)if(S-top=0) /*如果栈
8、为空*/printf(“栈中已经没有元素，不能进行出栈操作!n”);return 0;else /*否则*/S-top-; /*先修改栈顶指针，即出栈*/*e=S-stackS-top; /*将出栈元素赋给e*/return 1;,4.2 栈的顺序表示与实现,（6）求栈的长度。int StackLength(SeqStack S)/*求栈的长度*/return S.top; （7）清空栈。void ClearStack(SeqStack *S) /*清空栈*/S-top=0; /*将栈顶指针置为0*/,4.2 栈的顺序表示与实现,4.2.3 顺序栈应用举例【例4_1】利用顺序栈的基本操作，将元
9、素A、B、C、D、E、F依次进栈，然后将F和E出栈，再将G和H进栈，最后将元素全部出栈，并依次输出出栈元素。,4.2 栈的顺序表示与实现,【例4_2】有两个栈S1和S2都采用顺序结构存储，并且共享一个存储区。为了尽可能利用存储空间，减少溢出的可能，采用栈顶相向，迎面增长的方式，试设计S1和S2有关入栈和出栈算法。【分析】该题是哈尔滨工业大学的考研试题，主要考察共享栈的算法设计。1什么是栈的共享在使用顺序栈时，因为栈空间的大小难以准确估计，可能会出现有的栈还有空闲空间。为了能充分利用栈的空间，可以让多个栈共享一个足够大的连续存储空间，通过利用栈顶指针能灵活移动的特性，使多个栈存储空间互相补充，存
10、储空间得到有效利用，这就是栈的共享。,4.2 栈的顺序表示与实现,共享栈的数据结构类型描述如下。typedef structDataType stackStackSize;int top2;SSeqStack;其中，top0和top1分别是两个栈的栈顶指针。用一维数组表示的共享栈如图4.5所示。,4.2 栈的顺序表示与实现,2共享栈的基本运算 （1）初始化栈。 void InitStack(SSeqStack *S) /*共享栈的初始化*/ S-top0=0;S-top1=StackSize-1; ,4.2 栈的顺序表示与实现,（2）取栈顶元素。 int GetTop(SSeqStack S,
11、 DataType *e,int flag) /*取栈顶元素。将栈顶元素值返回给e，并返回1表示成功；否则返回0表示失败。*/ switch(flag)case 1: /*为1，表示要取左端栈的栈顶元素*/if(S.top0=0)return 0;*e=S.stackS.top0-1;break;case 2: /*为2，表示要取右端栈的栈顶元素*/if(S.top1=StackSize-1)return 0;*e=S.stackS.top1+1;break;default:return 0; return 1; ,4.2 栈的顺序表示与实现,（3）将元素e入栈。 int PushStack(
12、SSeqStack *S,DataType e,int flag) /*将元素e入共享栈。进栈成功返回1，否则返回0*/ if(S-top0=S-top1) /*如果共享栈已满*/return 0; /*返回0，进栈失败*/switch(flag)case 1: /*当flag为1，表示将元素进左端的栈*/S-stackS-top0=e; /*元素进栈*/S-top0+; /*修改栈顶指针*/break;case 2: /*当flag为2，表示将元素要进右端的栈*/S-stackS-top1=e; /*元素进栈*/S-top1-; /*修改栈顶指针*/break;default:return
13、0;return 1; /*返回1，进栈成功*/ ,4.2 栈的顺序表示与实现,（4）将栈顶元素出栈。int PopStack(SSeqStack *S,DataType *e,int flag)switch(flag) /*在出栈操作之前，判断哪个栈要进行出栈操作*/case 1: /*为1，表示左端的栈需要出栈操作*/if(S-top0=0) /*左端的栈为空*/return 0; /*返回0，出栈操作失败*/S-top0-; /*修改栈顶指针，元素出栈操作*/*e=S-stackS-top0; /*将出栈的元素赋给e*/break;case 2: /*为2，表示右端的栈需要出栈操作*/i
14、f(S-top1=StackSize-1) /*右端的栈为空*/return 0; /*返回0，出栈操作失败*/S-top1+; /*修改栈顶指针，元素出栈操作*/*e=S-stackS-top1; /*将出栈的元素赋给e*/break;default:return 0;return 1; /*返回1，出栈操作成功*/ ,4.2 栈的顺序表示与实现,（5）判断栈是否为空。int StackEmpty(SSeqStack S,int flag)switch(flag)case 1: /*为1，表示判断左端的栈是否为空*/if(S.top0=0)return 1;break;case 2: /*为
15、2，表示判断右端的栈是否为空*/if(S.top1=StackSize-1)return 1;break;default:printf(“输入的flag参数错误!”);return -1; return 0; ,4.3 栈的链式表示与实现,在顺序栈中，由于顺序存储结构需要事先静态分配，而存储规模往往又难以确定，如果栈空间分配过小，可能会造成溢出；如果栈空间分配过大，又造成存储空间浪费。 4.3.1 栈的存储结构栈的链式存储结构是用一组不一定连续的存储单元来存放栈中的数据元素的。一般来说，当栈中数据元素的数目变化较大或不确定时，使用链式存储结构作为栈的存储结构是比较合适的。人们将用链式存储结构表示的栈称为链栈或链式栈。,
