武汉软件工程职业学院数据结构讲义第08讲_栈.doc

《武汉软件工程职业学院数据结构讲义第08讲_栈.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、...第八讲栈1．掌握栈的定义及其运算。2．了解俄栈的顺序存储结构。3.掌握栈的链式存储结构。Ø教学重点：栈的链式储表示与实现方法Ø教学难点：栈的定义及两种存储结构，尤其注意栈满和栈空的概念Ø授课容第三章栈和队列栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故称运算受限制的线性表。3．1栈３.１.１栈的定义及基本运算栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。

2、当表中没有元素时称为空栈。如图3.1.1所示栈中有三个元素，进栈的顺序是a1、a2、a3，当需要出栈时其顺序为a3、a2、a1，所以栈又称为后进先出的线性表（LastInFirstOut），简称LIFO表。入栈出栈a3a2a1top.......图3.1栈示意图3.1.2栈的顺序存储结构1、栈的主要算法在日常生活中，有很多后进先出的例子，读者可以列举。在程序设计中，常常需要栈这样的数据结构，使得与保存数据时相反顺序来使用这些数据，这时就需要用一个栈来实现。对于栈，常做的基本运算有：⑴栈初始化：Init_Stack(s)初始

3、条件：栈s不存在操作结果：构造了一个空栈。⑵判栈空：Empty_Stack(s)初始条件：栈s已存在操作结果：若s为空栈返回为1，否则返回为0。⑶入栈：Push_Stack(s，x)初始条件：栈s已存在操作结果：在栈s的顶部插入一个新元素x，x成为新的栈顶元素。栈发生变化。⑷出栈：Pop_Stack(s)初始条件：栈s存在且非空操作结果：栈s的顶部元素从栈中删除，栈中少了一个元素。栈发生变化。⑸读栈顶元素：Top_Stack(s)初始条件：栈s存在且非空操作结果：栈顶元素作为结果返回，栈不变化。2、顺序栈的存储实现和运算实

4、现由于栈是运算受限的线性表，因此线性表的存储结构对栈也是适用的，只是操作不同而已。利用顺序存储方式实现的栈称为顺序栈。类似于顺序表的定义，栈中的数据元素用一个预设的足够长度的一维数组来实现：datatypedata[MAXSIZE]，栈底位置可以设置在数组的任一个端点，而栈顶是随着插入和删除而变化的，用一个inttop来作为栈顶的指针，指明当前栈顶的位置，同样将data和top封装在一个结构中，顺序栈的类型描述如下：#defineMAXSIZE1024typedefstruct{datatypedata[MAXSIZE];

5、inttop;}SeqStack定义一个指向顺序栈的指针：SeqStack*s;通常0下标端设为栈底，这样空栈时栈顶指针top=-1;入栈时，栈顶指针加１，即.......s->top++;出栈时，栈顶指针减１，即s->top--。栈操作的示意图如图3.2所示。图(a)是空栈，图(c)是A、B、C、D、E5个元素依次入栈之后，图(d)是在图(c)之后E、D相继出栈，此时栈中还有3个元素，或许最近出栈的元素D、E仍然在原先的单元存储着，但top指针已经指向了新的栈顶，则元素D、E已不在栈中了，通过这个示意图要深刻理解栈顶指针

6、的作用。在上述存储结构上基本操作的实现如下：top=-1top=0top=4top=2top=-1(a)空栈(b)一个元素(c)5个元素(d)3个元素(e)空栈图3.2栈顶指针top与栈中数据元素的关系⑴置空栈：首先建立栈空间，然后初始化栈顶指针。SeqStack*Init_SeqStack(){SeqStack*s;s=malloc(sizeof(SeqStack));s->top=-1;returns;}⑵判空栈intEmpty_SeqStack(SeqStack*s){if(s->top==-1)return1;el

7、sereturn0;}⑶入栈intPush_SeqStack(SeqStack*s,datatypex){if(s->top==MAXSIZE-1)return0;/*栈满不能入栈*/else{s->top++;s->data[s->top]=x;return1;}}⑷出栈.......intPop_SeqStack(SeqStack*s,datatype*x){if(Empty_SeqStack(s))return0;/*栈空不能出栈*/else{*x=s->data[s->top];s->top--;return1;}

8、/*栈顶元素存入*x，返回*/}⑸取栈顶元素datatypeTop_SeqStack(SeqStack*s){if(Empty_SeqStack(s))return0;/*栈空*/elsereturn(s->data[s->top]);}以下几点说明：1.对于顺序栈，入栈时，首先判栈是否满了，栈满的条件