c语言课件：栈和队列.ppt

栈和队列,栈 抽象数据类型栈的定义 栈的表示和实现 栈的应用举例 数制转换 表达式求解 队列,是限制仅在线性表的一端进行插入和删除运算的线性表。,栈顶（TOP） 允许插入和删除的一端。 栈底（bottom) 不允许插入和删除的一端。 空栈 表中没有元素。,栈(Stack),进栈 最先插入的元素放在栈的底部。 退栈 最后插入的元素最先退栈。,栈的基本概念,栈:又称为后进先出的线性表（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空栈,顺序栈：栈顶指针与栈中元素间的关系,顺序栈,栈底位置固定在数组的低端，即： 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 /* Empty */,void Push(Stack /* Push */,顺序栈的几种基本运算,进栈：,/*若栈S非空，取出栈顶元素删除*/ void Pop(Element ,退栈： Pop(S),顺序栈的几种基本运算,/*取顺序栈S的栈顶*/ Element Top(Stack ,取栈顶： 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 ,.,栈底,x,s.top,链栈进栈运算,链栈退栈运算,void Pop(Element ,栈小结,顺序栈有发生上溢 的可能，而链栈通常不会发生栈满（除非整个空间均被占满） 只要满足LIFO原则，均可采用栈结构。 栈的应用实例：递归调用。,栈的应用举例一数制转换,十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d + (n mod d),（185）10 =（ ？ ）8,（1 8 5）10 = （2 7 1）8,栈的应用举例一数制转换,void conversion( ) /conversion Initstack(S); scanf(“%d”, ,栈的应用举例一数制转换,栈的应用举例一算术表达式,建立2个栈：操作数栈及运算符栈，初始为空 从左到右读取表达式，如果读到操作数则置入操作数栈中，若读到运算符时则置入运算符栈。 当读到的运算符优先级比栈中的运算符高，则存入栈 当读到的运算符优先级比堆栈中的运算符低或相等，则取出该运算符并从操作数栈取出相应的操作数运算，并将结果存回操作数栈；同时新运算符入栈； 堆栈非空 从运算符栈中取出一个运算符 从操作数栈中取出所需操作数 计算其值后将结果存回操作数栈,例 计算 2+4-3*6,例 计算 2+4-3*6,栈的应用举例一算术表达式,队列,只允许在表的一端进行插入，而在表的另一端进行删除，是一种先入先出的线性表（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,循环队列的进队和出队,空队列,循环队列 (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,队列的链接表示 链式队列,typedef struct linklist *head,*tail; linkqueue;,链队列结点类型定义,Setnull (linkqueue *q) q-headmalloc(sizeof(linklist); q-head-nextNULL; q-tailq-head; ,链队列置队空,int Empty(linkqueue *q) if ( q-head = q-tail ) return(True); else return(False); ,链队列判队空,datatype Front(linkqueue *q) if (Empty(q) printf(“queue is emptyn”); return NULL; else return(q-head-next-data); ,链队列取队头结点,Enqueue(linkqueue *q, datatype x) pmalloc(sizeof(linklist); p -data=x; p -next=null; q-tail-nextp; q-tailp; ,链队列入队,datatype 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); ,链队列出队,栈和队列作业