栈和队列数据结构教程

3.1栈3.2栈的应用举例3.3队列3.4队列的应用举例第1页/共22页第一页，共23页。3.1栈

3.1.1栈的定义

栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：

进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底。我们经常将栈用下图3-1的形式描述：a1,a2,a3,...,an插入和删除端第2页/共22页第二页，共23页。图3-1第3页/共22页第三页，共23页。

结论：后进先出（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）判断栈是否为空Empty_Stack(S)

第4页/共22页第四页，共23页。

3.1.2栈的顺序存储

栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。

类型定义如下所示：#defineMAXSIZE100typedefstruct{datatypedata[MAXSIZE];inttop;}SeqStack

定义一个指向顺序栈的指针：SeqStack*s;第5页/共22页第五页，共23页。基本操作算法：⑴置空栈：首先建立栈空间，然后初始化栈顶指针。SeqStack*Init_SeqStack(){SeqStack*s;s=malloc(sizeof(SeqStack));s->top=-1;returns;}⑵判空栈intEmpty_SeqStack(SeqStack*s){if(s->top==-1)return1;elsereturn0;}第6页/共22页第六页，共23页。图3-2第7页/共22页第七页，共23页。

⑶入栈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;}/*栈顶元素存入*x，返回*/}第8页/共22页第八页，共23页。⑸取栈顶元素datatypeTop_SeqStack(SeqStack*s){if(Empty_SeqStack(s))return0;/*栈空*/elsereturn(s->data[s->top]);}

以下几点说明：

1.对于顺序栈，入栈时，首先判断栈是否满了，栈满的条件为：s->top==MAXSIZE-1，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。2.出栈和读栈顶元素操作，先判断栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。

第9页/共22页第九页，共23页。

3.1.3栈的链式存储

若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图3-3所示。

由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。第10页/共22页第十页，共23页。链式栈:栈的链接表示

链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作top如图3-3第11页/共22页第十一页，共23页。栈的链式存储结构在C语言中可用下列类型定义实现：typedefstructnode{datatypedata;structnode*next;}StackNode，*LinkStack;

说明top为栈顶指针：LinkStacktop;第12页/共22页第十二页，共23页。下面我们将给出链栈各项基本操作的算法。⑴置空栈Init_LinkStack（LinkStacktop）{top＝NULL;}⑵判栈空intEmpty_LinkStack（LinkStacktop）{if（top==NULL）return1;elsereturn0;}第13页/共22页第十三页，共23页。⑶入栈LinkStackPush_LinkStack（LinkStacktop,datatypex）{StackNode*s;s=malloc（sizeof（StackNode））;s->data=x;s->next=top;top=s;returntop;}第14页/共22页第十四页，共23页。⑷出栈LinkStackPop_LinkStack(LinkStacktop,datatype*x){StackNode*p;if（top==NULL）returnNULL;else{*x=top->data;p=top;top=top->next;free(p);returntop;}}第15页/共22页第十五页，共23页。例3.1简单应用：数制转换问题将十进制数N转换为r进制的数，其转换方法利用辗转相除法：以N=3467，r=8为例转换方法如下：NN/8（整除）N%8（求余）34674333低4335415466606高

所以：（3467）10=（6613）83.2栈的应用举例第16页/共22页第十六页，共23页。

我们看到所转换的8进制数按低位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。

算法思想如下：当N>0时重复1，21．若N≠0，则将N%r压入栈s中，执行2;若N=0，将栈s的内容依次出栈，算法结束。2．用N/r代替N

第17页/共22页第十七页，共23页。#defineL10voidconversion(intN，intr){ints[L],top;/*定义一个顺序栈*/intx;top=-1;/*初始化栈*/while(N){s[++top]=N%r;/*余数入栈*/N=N/r;/*商作为被除数继续*/}while(top!=-1){x=s[top--];printf(“%d”,x);}}第18页/共22页第十八页，共23页。课堂练习：I表示入栈，O表示出栈，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的I和O的操作串是什么？

I1O1I2I3O3I4O4O2第19页/共22页第十九页，共23页。main(){ inti,e,a[]={1,2,3,4,5,6,7,8,9}; SeqStacks; Initstack(s); for(i=0;i<9;i++) push(s,a[i]);//入栈while(!Stackempty(s)) { pop(s,e);//出栈 printf(“%2d”,e) } }课堂练习：