第3章1 栈和队列 (数据结构教程PPT课件)

《第3章1 栈和队列 (数据结构教程PPT课件)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章栈和队列本章主要介绍以下内容：栈的概念、存储结构及其基本操作队列的概念、存储结构及其基本操作栈与队列的应用举例退出诚昊工作室3.1栈3.2栈的应用举例3.3队列3.4队列的应用举例3.1栈3.1.1栈的定义栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底。我们经常将栈用下图3-1的形式描述：a1,a2,a3,...,an插入和删除端图3-1结论：后进

2、先出（LastInFirstOut），简称为LIFO线性表。举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：死胡同。举例3：对一栈，给定的输入项目A,B,C,若输入的顺序是A,B,C，试给出全部的可能的输出序列。下面我们先给出栈结构的基本操作：（1）初始化栈Init_Stack(S)（2）入栈Push_Stack(S,x)（3）出栈Pop_Stack(S)（4）获取栈顶元素内容Top_Stack(S)（5）

3、判断栈是否为空Empty_Stack(S)3.1.2栈的顺序存储栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。类型定义如下所示：#defineMAXSIZE100typedefstruct{datatypedata[MAXSIZE];inttop;}SeqStack定义一个指向顺序栈的指针：SeqStack*s;基本操作算法：⑴置空栈：首先建立栈空间，然后初始化栈顶指针。SeqStack*Init_SeqStack(){SeqStack*s;s=malloc(siz

4、eof(SeqStack));s->top=-1;returns;}⑵判空栈intEmpty_SeqStack(SeqStack*s){if(s->top==-1)return1;elsereturn0;}图3-2⑶入栈intPush_SeqStack(SeqStack*s,datatypex){if(s->top==MAXSIZE-1)return0;/*栈满不能入栈*/else{s->top++;s->data[s->top]=x;return1;}}⑷出栈intPop_SeqStack(SeqSta

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

6、>top==MAXSIZE-1，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。2.出栈和读栈顶元素操作，先判断栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。3.1.3栈的链式存储若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图3-3所示。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将

7、单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。链式栈:栈的链接表示链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作top如图3-3栈的链式存储结构在C语言中可用下列类型定义实现：typedefstructnode{datatypedata;structnode*next;}StackNode，*LinkStack;说明top为栈顶指针：LinkStacktop;下面我们将给出链栈各项基本操作的算法。⑴置空栈Init_LinkStack（LinkStacktop

8、）{top＝NULL;}⑵判栈空intEmpty_LinkStack（LinkStacktop）{if（top==NULL）return1;elsereturn0;}⑶入栈LinkStackPush_LinkStack（LinkStacktop,datatypex）{StackNode*s;s=malloc（sizeof（StackNode））;s->data=x;s->next=top;top=s;returntop;}⑷出