c语言课件：栈和队列.ppt
1/16/20231栈和队列栈抽象数据类型栈的定义栈的表示和实现栈的应用举例数制转换表达式求解队列1/16/20232是限制仅在线性表的一端进行插入和删除运算的线性表。an.a2a1 栈顶 TOP 栈底 Bottom 栈顶（TOP）允许插入和删除的一端。栈底（bottom)不允许插入和删除的一端。空栈 表中没有元素。栈(Stack)1/16/20233an.a2a1进栈 退栈 栈顶 栈底进栈最先插入的元素放在栈的底部。退栈最后插入的元素最先退栈。栈的基本概念栈:又称为后进先出的线性表（LIFO表，Last In First Out）一叠书或一叠盘子。1/16/20234栈与子程序调用调用子程序时，计算机将子程序要用到的参数及返回地址等信息存放在栈里子程序返回时，从栈顶取回返回地址，转回主调程序继续运行。处理递归调用1/16/20235顺序栈用数组定义（类似于顺序表），将栈底位置设置在向量两端的任意一个端点；用top（整型量，栈顶指针）来指示栈当前栈顶位置。定义：typedef(type)Element;/*栈元素的数据类型*/#define maxsize 100/*栈初始的容量*/typedef struct stackElement datamaxsize;int top;Stack;/*顺序栈类型定义*/Stack*s;/*s是顺序栈类型指针*/1/16/20236 3 2 1 0Top=-1空栈空栈A 3 2 1 0TOP A进栈进栈 3 2 1 0DCBAB、C、D依次进栈依次进栈TOP 3 2 1 0BATOPD、C依次退栈依次退栈 3 2 1 0Top=-1，B、A退退栈栈顺序栈：栈顶指针与栈中元素间的关系1/16/20237顺序栈栈底位置固定在数组的低端，即：S-data0-表示栈底元素；进栈：S-TOP加1（正向增长）。退栈：S-TOP减1。空栈：S-TOP TOP=maxsize-1上溢：栈满时再做进栈运算（一种出错状态，应设法避免）。1/16/20238顺序栈的几种基本运算置空栈判栈空进栈退栈取栈顶元素1/16/20239 顺序栈的几种基本运算置空栈：Create(Stack&S)void Create(Stack&S)/*将顺序栈S置为空*/S.top=-1 1/16/202310顺序栈的几种基本运算判栈空：Bool Empty(Stack&S)/*判定顺序栈S是否为空*/if(S.top=0)return False;else return True;/*Empty*/1/16/202311void Push(Stack&S,Element e)/*将元素e插入栈S顶部*/if(S.top=maxsize-1)Serr=StackOverflow;else S.top+;S.dataS.top=e;/*Push*/顺序栈的几种基本运算进栈：1/16/202312/*若栈S非空，取出栈顶元素删除*/void Pop(Element&e,Stack&S)/*Pop*/if(Empty(S)Serr=StackUnderflow;else e=S.dataS.top;S.top-;退栈：Pop(S)顺序栈的几种基本运算1/16/202313/*取顺序栈S的栈顶*/Element Top(Stack&S)/*Top*/if(Empty(S)输出“栈空”;return NULL;else return(S.dataS.top);取栈顶：Top(S)顺序栈的几种基本运算1/16/202314链栈栈的链式存储结构（当顺序栈的最大容量事先无法估计时，可采用链栈结构）。TOP e1 next栈顶栈顶 .链栈的定义：typedef struct cell*Position;typedef struct cell Element e1;Position next;Cell;typedef struct stack Position*top;Stack;1/16/202315链栈的特点插入和删除（进栈/退栈）仅能在表头位置上（栈顶）进行。链栈中的结点是动态产生的，可不考虑上溢问题。不需附加头结点，栈顶指针就是链表（即链栈）的头指针。1/16/202316void Push(Element e,Stack&S)Position p;p=new(Cell);p-e1=e;p-next=S.top;S.top=p;.栈底栈底xs.top链栈进栈运算1/16/202317链栈退栈运算void Pop(Element&e,Stack&S)Position p;if(S.top=NULL)SErr=StackUnderflow;elsee=S.top-e1;p=S.top;S.top=S.top-next;free(p);top .栈底topq1/16/202318栈小结顺序栈有发生上溢 的可能，而链栈通常不会发生栈满（除非整个空间均被占满）只要满足LIFO原则，均可采用栈结构。栈的应用实例：递归调用。1/16/202319栈的应用举例一数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(n div d)*d+(n mod d)（185185）1010=（？）8 8（1 8 51 8 5）10 10 =（2 7 12 7 1）8 88 82 72 78 80 20 21 8 5 1 8 5 8 82 3 12 3 1余数余数1/16/202320 例 把十进制数159转换成八进制数。(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732栈的应用举例一数制转换1/16/202321void conversion()/conversion Initstack(S);scanf(“%d”,&N);while(N)Push(S,N%8);N=N/8;while(!Stackempty(s)Pop(S,e);Printf(“%d”,e);栈的应用举例一数制转换1/16/202322栈的应用举例一算术表达式建立2个栈：操作数栈及运算符栈，初始为空从左到右读取表达式，如果读到操作数则置入操作数栈中，若读到运算符时则置入运算符栈。当读到的运算符优先级比栈中的运算符高，则存入栈当读到的运算符优先级比堆栈中的运算符低或相等，则取出该运算符并从操作数栈取出相应的操作数运算，并将结果存回操作数栈；同时新运算符入栈；堆栈非空从运算符栈中取出一个运算符从操作数栈中取出所需操作数计算其值后将结果存回操作数栈例 计算 2+4-3*61/16/202323例 计算 2+4-3*6操作数运算符24+操作数运算符6-操作数运算符6-36*操作数运算符6-18操作数运算符12栈的应用举例一算术表达式1/16/202324队列只允许在表的一端进行插入，而在表的另一端进行删除，是一种先入先出的线性表（FIFO）。1/16/202325队列的基本概念队头（head):允许删除（出队）的一端队尾（tail):允许插入的一端空队列：队列中没有元素进队：队的插入运算，即插入新的队尾元素出队：队的删除运算，删除队首元素1/16/202326队列的基本运算入队出队取队头元素置空队列判队列是否为空1/16/202327顺序队列队列的顺序存储结构，用一组连续的存储单元依次存放队列中的元素顺序队列的类型说明：typedef struct datatype datam;int head,tail;/*队首、队尾*/queue;queue*sq;1/16/202328BADC 3 2 1 0sq-headsq-tailsq-headsq-tailsq-headsq-tailsq-tailsq-head空队列空队列A、B相继入队相继入队A、B相继出队相继出队C、D相继入队相继入队顺序队列运算时的头、尾指针变化1/16/202329顺序队列的约定和主要运算队头指针:head总是指向当前队头元素队尾指针:tail指向当前队尾元素的下一个位置。初始状态：head=tail=0入队运算：sq-tail+;/*尾指针加1*/sq-datasq-tail=x;/*x入队*/出队运算：sq-head+;/*头指针加1 */1/16/202330顺序队列的约定和主要运算队列长度：(sq-tail)-(sq-head)队空：(sq-tail)=(sq-head)下溢：队空时再作出队操作。队满：(sq-tail)-(sq-head)=m上溢：队满时再作入队操作。1/16/202331顺序队列的上溢队上溢：真上溢（r-f=m)：队列真正满时再入队。假上溢：r已指向数组尾端，但队列前端仍有空位置。解决假上溢的方法：方法一：每次删除队头一个元素后，把整个队列往前移一个位置（造成时间浪费）。方法二：循环队列1/16/202332Setnull(queue*sq)sq-head0;sq-tail0;顺序队列置队空1/16/202333Bool Empty(queue*sq)if(sq-tail=sq-head)return (True);else return (False);顺序队列判队空1/16/202334datatype Front(queue*sq)datatype temp;if(Empty(sq)printf(“queue is emptyn”);return NULL;else temp=sq-data sq-head;return temp;顺序队列取队头元素1/16/202335Bool 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);顺序队列入队1/16/202336datetype Dequeue(queue*sq)if(Empty(sq)printf(“queue is emptyn”);return NULL;else sq-head(sq-head+1);return(sq-datasq-head);顺序队列出队1/16/202337循环队列(Circular Queue)当队尾指针tail等于MaxSize时，无论有否空间，都无法再将数据存于队列中将所用的数组sq-datam设想为首尾相接的循环数组（即：data0连在datam-1之后)。tailhead1/16/202338循环队列的进队和出队0107654321headtail空队列空队列A107654321headtailA入队入队A1076543CBheadtailBC入队入队01076543CBheadtailA出队出队1/16/202339循环队列(Circular Queue)队列入队：若尾指针 r 等于向量的上界，再入队，令尾指针等于向量的下界，即：在循环意义下的尾指针的加1操作可描述为：if(sq-tail+1=m)sq-tail=0;else sq-tail+;1/16/202340循环队列(Circular Queue)存储队列的数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:head=(head+1)%maxSize;队尾指针进1:tail=(tail+1)%maxSize;队列初始化：head=tail=0;队空条件：head=tail;队满条件：(tail+1)%maxSize=head1/16/202341 Q-head data next队头队头 .Q-tail队尾队尾队列的链接表示 链式队列队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为 head=NULL1/16/202342Q-headQ-tail空队列Q-headQ-tail元素 x 入队列x元素 y 入队列Q-headQ-tailxyQ-headQ-tailxy元素x 出队列队列的链接表示 链式队列1/16/202343typedef struct linklist*head,*tail;linkqueue;链队列结点类型定义1/16/202344Setnull(linkqueue*q)q-headmalloc(sizeof(linklist);q-head-nextNULL;q-tailq-head;链队列置队空1/16/202345int Empty(linkqueue*q)if(q-head=q-tail)return(True);else return(False);链队列判队空1/16/202346datatype Front(linkqueue*q)if(Empty(q)printf(“queue is emptyn”);return NULL;else return(q-head-next-data);链队列取队头结点1/16/202347Enqueue(linkqueue*q,datatype x)pmalloc(sizeof(linklist);p-data=x;p-next=null;q-tail-nextp;q-tailp;链队列入队1/16/202348datatype Dequeue(linkqueue*q,datatype e)linklist*p;if(Empty(q)printf(“queue is emptyn”);return NULL;else pq-head-next;ep-data;q-head-next=p-next free(p);return(p);链队列出队1/16/202349栈和队列作业1、用栈实现以下功能：（1）实现任意十进制数转换为二进制数，并测试；（2）实现表达式计算，并测试；2、用循环队列模拟舞伴配对问题：在舞会上，男、女各自排成一队。舞会开始时。依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等，则较长的那一队中未配对者等待下一轮舞曲。假设初始男、女人数及性别已经固定，舞会的轮数从键盘输入。试模拟解决上述舞伴配对问题。要求：从屏幕输出每一轮舞伴配对名单，如果在该轮有未配对的，能够从屏幕显示下一轮第一个出场的未配对者的姓名。
