c语言课件：栈和队列

个人演示ppt设计模板,第一级标题,第二级标题,第三级内容,第四级内容,第五级内容,*,*,栈和队列,栈,抽象数据类型栈的定义,栈的表示和实现,栈的应用举例,数制转换,表达式求解,队列,是限制仅在线性表的一端进行插入和删除运算的线性表。,a,n,.,.,.,a,2,a,1,栈顶,TOP,栈底 Bottom,栈顶（,TOP,）,允许插入和删除的一端。,栈底（,bottom),不允许插入和删除的一端。,空栈,表中没有元素。,栈(Stack),a,n,.,.,.,a,2,a,1,进栈,退栈,栈顶,栈底,进栈,最先插入的元素放在栈的底部。,退栈,最后插入的元素最先退栈。,栈的基本概念,栈:又称为后进先出的线性表（LIFO表，Last In First Out）一叠书或一叠盘子。,栈与子程序调用,调用子程序时，计算机将子程序要用到的参数及返回地址等信息存放在栈里,子程序返回时，从栈顶取回返回地址，转回主调程序继续运行。,处理递归调用,顺序,栈,用,数组,定义（类似于顺序表），将栈底位置设置在向量两端的任意一个端点；用top（整型量，栈顶指针）来指示栈当前栈顶位置。,定义：,typedef(type)Element;/*栈元素的数据类型*/,#define maxsize 100/*栈初始的容量*/,typedef struct stack,Element datamaxsize;,int top;,Stack;/*顺序栈类型定义*/,Stack*s;/*s是顺序栈类型指针*/,3 2 1 0,Top=,-,1空栈,A,3 2 1 0,TOP,A进栈,3 2 1 0,D,C,B,A,B、C、D依次进栈,TOP,3 2 1 0,B,A,TOP,D、C依次退栈,3 2 1 0,Top=,-,1，B、A退栈,顺序,栈：栈顶指针与栈中元素间的关系,顺序,栈,栈底位置固定在数组的低端，即：,S-data0,-,表示栈底元素；,进栈：S-TOP加1（正向增长）。,退栈：S-TOP减1。,空栈：S-TOP,TOP=maxsize-1,上溢：栈满时再做进栈运算（一种出错状态，应设法避免）。,顺序栈的几种基本运算,置空栈,判栈空,进栈,退栈,取栈顶元素,顺序栈的几种基本运算,置空栈：Create(Stack&S),void Create(Stack&S)/*将顺序栈S置为空*/,S.top=-1 ,顺序栈的几种基本运算,判栈空：,Bool Empty(Stack&S)/*判定顺序栈S是否为空*/,if(S.top=0)return False;,else return True;,/*Empty*/,void Push(Stack&S,Element e)/*将元素e插入栈S顶部*/,if(S.top=maxsize-1)Serr=StackOverflow;,else S.top+;S.dataS.top=e;,/*Push*/,顺序栈的几种基本运算,进栈：,/*若栈S非空，取出栈顶元素删除*/,void Pop(Element&e,Stack&S)/*Pop*/,if(Empty(S)Serr=StackUnderflow;,else e=S.dataS.top;S.top-;,退栈：,Pop(S),顺序栈的几种基本运算,/*取顺序栈S的栈顶*/,Element Top(Stack&S)/*Top*/,if(Empty(S)输出“栈空”;return NULL;,else return(S.dataS.top);,取栈顶：,Top(S),顺序栈的几种基本运算,链栈,栈的链式存储结构（当顺序栈的最大容量事先无法估计时，可采用链栈结构）。,TOP,e1 next,栈顶,.,.,链栈的定义：,typedef struct cell*Position;,typedef struct cell,Element e1;,Position next;,Cell;,typedef struct stack,Position*top;,Stack;,链栈的特点,插入和删除（进栈,/,退栈）仅能在表头位置上（栈顶）进行。,链栈中的结点是动态产生的，可不考虑上溢问题。,不需附加头结点，栈顶指针就是链表（即链栈）的头指针。,void Push(Element e,Stack&S),Position p;,p=new(Cell);,p-e1=e;,p-next=S.top;,S.top=p;,.,栈底,x,s.top,链栈进栈运算,链栈退栈运算,void Pop(Element&e,Stack&S),Position p;,if(S.top=NULL),SErr=StackUnderflow;,else,e=S.top-e1;,p=S.top;,S.top=S.top-next;,free(p);,top,.,栈底,top,q,栈小结,顺序栈有发生上溢 的可能，而链栈通常不会发生栈满（除非整个空间均被占满）,只要满足LIFO原则，均可采用栈结构。,栈的应用实例：,递归调用,。,栈的应用举例一,数制转换,十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:,N=(n div d)*d+(n mod d),（185）,10,=（？）,8,（1 8 5）,10,=（2 7 1）,8,8,2 7,8,0 2,1 8 5,8,2 3 1,余数,例 把十进制数159转换成八进制数。,(159),10,=(237),8,159,8,19,8,2,8,0,2 3 7,余 7,余 3,余 2,top,top,7,top,7,3,top,7,3,2,栈的应用举例一,数制转换,void conversion()/conversion,Initstack(S);,scanf(“%d”,while(N),Push(S,N%8);,N=N/8;,while(!Stackempty(s),Pop(S,e);,Printf(“%d”,e);,栈的应用举例一,数制转换,栈的应用举例一,算术表达式,建立,2,个栈：操作数栈及运算符栈，初始为空,从左到右读取表达式，如果读到操作数则置入操作数栈中，若读到运算符时则置入运算符栈。,当读到的运算符优先级比栈中的运算符高，则存入栈,当读到的运算符优先级比堆栈中的运算符低或相等，则取出该运算符并从操作数栈取出相应的操作数运算，并将结果存回操作数栈；同时新运算符入栈；,堆栈非空,从运算符栈中取出一个运算符,从操作数栈中取出所需操作数,计算其值后将结果存回操作数栈,例 计算 2+4-3*6,例 计算 2+4-3*6,操作数,运算符,2,4,+,操作数,运算符,6,-,操作数,运算符,6,-,3,6,*,操作数,运算符,6,-,18,操作数,运算符,12,栈的应用举例一,算术表达式,队列,只允许在表的一端进行插入，而在表的另一端进行删除，是一种先入先出的线性表（FIFO）。,队列的基本概念,队头（,head):允许删除（出队）的一端,队尾（tail):允许插入的一端,空队列：队列中没有元素,进队：队的插入运算，即插入新的队尾元素,出队：队的删除运算，删除队首元素,队列的基本运算,入队,出队,取队头元素,置空队列,判队列是否为空,顺序队列,队列的顺序存储结构，用一组连续的存储单元依次存放队列中的元素,顺序队列的类型说明：,typedef struct,datatype datam;,int head,tail;/*队首、队尾*/,queue;,queue*sq;,B,A,D,C,3,2,1,0,sq-head,sq-tail,sq-head,sq-tail,sq-head,sq-tail,sq-tail,sq-head,空队列,A、B相继入队,A、B相继出队,C、D相继入队,顺序队列运算时的头、尾指针变化,顺序队列的约定和主要运算,队头指针:head总是指向当前队头元素,队尾指针:tail指向当前队尾元素的下一个位置。,初始状态：head=tail=0,入队运算：sq-tail+;/*,尾指针,加1*/,sq-datasq-tail=x;/*x入队*/,出队运算：sq-head+;/*,头指针,加1 */,顺序队列的约定和主要运算,队列长度：(sq-tail)-(sq-head),队空：(sq-tail)=(sq-head),下溢：队空时再作出队操作。,队满：(sq-tail)-(sq-head)=m,上溢：队满时再作入队操作。,顺序队列的上溢,队上溢：,真上溢（,r-f=m)：队列真正满时再入队。,假上溢：r,已指向数组尾端，但队列前端仍有空位置。,解决假上溢的方法：,方法一：每次删除队头一个元素后，把整个队列往前移一个位置（造成时间浪费）。,方法二：循环队列,Setnull(queue*sq),sq-head0;,sq-tail0;,顺序队列置队空,Bool Empty(queue*sq),if(sq-tail=sq-head),return (True);,else,return (False);,顺序队列判队空,datatype Front(queue*sq),datatype temp;,if(Empty(sq),printf(“queue is emptyn”);return NULL;,else,temp=sq-data sq-head;,return temp;,顺序队列取队头元素,Bool Enqueue(queue*sq,datatype x),if(sq-head=(sq-tail+1)%m),printf(“queue is fulln”;return NULL);,else,sq-tail(sq-tail+1);,sq-datasq-tailx;return(True);,顺序队列入队,datetype Dequeue(queue*sq),if(Empty(sq),printf(“queue is emptyn”);return NULL;,else,sq-head(sq-head+1);,return(sq-datasq-head);,顺序队列出队,循环队列(Circular Queue),当队尾指针tail等于MaxSize时，无论有否空间，都无法再将数据存于队列中,将所用的数组sq-,datam设想为首尾相接的循环数组（即：data0连在datam-1之后)。,tail,head,循环队列的进队和出队,0,10,7,6,5,4,3,2,1,head,tail,空队列,A,10,7,6,5,4,3,2,1,head,tail,A入队,A,10,7,6,5,4,3,C,B,head,tail,BC入队,0,10,7,6,5,4,3,C,B,head,tail,A出队,循环队列(Circular Queue),队列入队：,若尾指针,r 等于向量的上界，再入队，令尾指针等于向量的下界，即：在循环意义下的尾指针的加1操作可描述为：,if(sq-tail+1=m)sq-tail=0;,else sq-tail+;,循环队列(Circular Queue),存储队列的数组被当作首尾相接的表处理。,队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。,队头指针进1:head=(head+1)%maxSize;,队尾指针进1:tail=(tail+1)%maxSize;,队列初始化：head=tail=0;,队空条件：head=tail;,队满条件：(tail+1)%maxSize=head,Q-head,data next,队头,.,.,Q-tail,队尾,队列的链接表示 链式队列,队头在链头，队尾在链尾。,链式队列在进队时无队满问题，但有队空问题。,队空条件为 head=NULL,Q-head,Q-tail,空队列,Q-head,Q-tail,元素 x 入队列,x,元素 y 入队列,Q-head,Q-tail,x,y,Q-head,Q-tail,x,y,元素x 出队列