栈和队列7.ppt

《栈和队列7.ppt》由会员分享，可在线阅读，更多相关《栈和队列7.ppt（75页珍藏版）》请在三一文库上搜索。

1、第3章 栈和队列,张成文 北京邮电大学计算机学院,概述,两种特殊的线性表。 逻辑结构和线性表相同。 比起线性表其运算受限制，故又称它们为运算受限的线性表。,1. 栈,1.1 栈的定义 1.2 顺序栈 1.3 链栈,1.1 栈的定义,栈是限制仅在表的一端进行插入和删除运算的线性表。 (1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。 (2)当表中没有元素时称为空栈。 (3)栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。,每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。因此，栈又称为后进先出的

2、线性表。简称为LIFO表。,栈的示意图,a1,a2,an,栈顶（表尾）,栈底,bottom,top,入栈push,出栈pop,栈的示意图,bottom,top,栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。 顺序存储的栈为顺序栈 链式存储的栈为链栈,栈的存储方式,1.2 顺序栈,栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。 顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。,顺序栈的类型定义,#define TRUE 1 #define FALSE 0 #define Stack_Size 50 typedef struct StackElementT

3、ype elemStack_Size; /* 一维数组*/ int top; /*用来存放栈顶元素的下标*/ SeqStack;,top,空栈,top,top,top,top,top,a 进栈,b 进栈,a,a,b,a,b,c,d,e,e 进栈,a,b,c,d,e,f 进栈溢出,a,b,d,e,e 退栈,c,top,c 退栈,b 退栈,a,b,a,a 退栈,空栈,top,a,b,d,d 退栈,c,top,a,b,c,top,top,注意,顺序栈中元素用向量存放 栈底位置是固定不变的，可设置在向量两端的任意一个端点 栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针

4、）来指示当前栈顶位置,顺序栈的基本运算,（1） 置栈空（初始化） （2） 判栈空 （3） 判栈满 （4） 进栈操作 （5） 退栈操作 （6） 取栈顶元素,（1）置栈空（初始化）,void InitStack（SeqStack *S） /将顺序栈置空 S-top=-1; ,(2) 判栈空,int StackEmpty（SeqStack *S） /*判栈S为空栈时返回值为真，反之为假*/ return S-top=-1; ,（3）判栈满,int StackFull（SeqStack *S） /*判栈S为满时返回真，否则返回假*/ return S-top=StackSize-1; ,（4）进栈,进

5、栈时，需要将S-top加1 注意： S-top=StackSize-1表示栈满 “上溢”现象-当栈满时，再做进栈运算产生空间溢出的现象。 上溢是一种出错状态，应设法避免。 void Push（SeqStack *S，DataType x） if (StackFull(S) Error(“Stack overflow”); /上溢，退出运行 S-data+S-top=x;/栈顶指针加1后将x入栈 ,（5）退栈,退栈时，需将S-top减1 注意： S-topdataS-top-;/栈顶元素返回后将栈顶指针减1 ,（6）取栈顶元素,DataType StackTop（S） if(StackEmpty

6、(S) Error(“Stack is empty“); return S-dataS-top; ,1.4 链栈,链栈是采用链表作为存储结构实现的栈，是线性链表的特例。因为栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针。,top为栈顶指针，始终指向当前栈顶元素结点。若top=NULL，则代表空栈。 注意：链栈在使用完毕时，应该释放其空间。,typedef struct stacknode DataType data struct stacknode *next StackNode; StackNode *head=NULL; typedef struct StackN

7、ode *top; /栈顶指针 LinkStack;,链栈的基本运算,(1) 置栈空 (2) 判栈空 (3) 进栈 (4) 退栈 (5) 取栈顶元素,（1） 置栈空,void InitStack(LinkStack *S) S-top=NULL; ,(2) 判栈空,int StackEmpty(LinkStack *S) return S-top=NULL; ,（3） 进栈,void Push(LinkStack *S,DataType x) /将元素x插入链栈头部 StackNode *p= (StackNode *)malloc(sizeof(StackNode); if(p=NULL)

8、printf(“内存空间不够分配”); exit(0);/return p-data=x; p-next=S-top;/将新结点*p插入链栈头部 S-top=p; ,（4） 退栈,DataType Pop(LinkStack *S) DataType x; StackNode *p=S-top;/保存栈顶指针 if(StackEmpty(S) Error(“Stack underflow.“); /下溢 x=p-data; /保存栈顶结点数据 S-top=p-next; /将栈顶结点从链上摘下 free(p); return x; ,将x入栈，修改栈顶指针:top=p,an出栈，修改栈顶指针:

9、top=top-next,链栈的入栈操作和出栈操作,（5） 取栈顶元素,DataType StackTop(LinkStack *S) if(StackEmpty(S) Error(“Stack is empty.“) return S-top-data; ,注意,链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull运算。,2. 队列,2.1 队列的定义 2.2 顺序队列 2.3 链队列,队列是一种特殊的线性表，限定插入和删除操作分别在表的两端进行。 a1 a2 ai an,2.1 队列的定义和基本运算,队列的性质,（1）允许删除的一端称为队头（Front）。 （2）允许插

10、入的一端称为队尾（Rear）。 （3）当队列中没有元素时称为空队列。 （4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表,队列的进队和出队,front,rear,空队列,front,rear,A进队,A,front,rear,B进队,A B,front,rear,C, D进队,A B C D,front,rear,A退队,B C D,front,rear,B退队,C D,front,rear,E,F,G进队,C D E F G,C D E F G,front,rear,H进队,溢出,队列的进队和出队原则,进队时队尾指针先进一 rear = rear +

11、1， 再将新元素按 rear 指示位置加入。 出队时队头指针先进一 front = front + 1， 再将下标为 front 的元素取出。 队满时再进队将溢出出错； 队空时再出队将队空处理。 解决办法之一：将队列元素存放数组首尾 相接，形成循环(环形)队列。,队列在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。 顺序存储的队列为顺序队列 链式存储的队列为链队列,队列的存储方式,2.2 顺序队列,2.2.1 顺序队列的定义 2.2.2 顺序队列的基本运算 2.2.3 循环队列,2.2.1 顺序队列的定义,队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表,顺序队

12、列的表示,和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。 由于队列的队头和队尾的位置是变化的，设置两个“指针”front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。,2.2.2 顺序队列的基本运算,入队时：将新元素插入rear所指的位置，然后将rear加1。 出队时：删去front所指的元素，然后将front加1并返回被删元素。 注意： 当头尾指针相等时，队列为空。 在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。,当Q-front= Q-rear 时,队列空。 当Q-rear+1MaxSize 时,队列满

13、(即上溢出),但此时头指针指示的元素之前可能还有空单元,此现象称为假溢出;若把这样的顺序结构设想为一个循环表, 插入时就可以利用这些空单元, 这样就构成循环队列。,假上溢,2.2.3 循环队列,为充分利用向量空间，克服“假上溢”现象的方法： 将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。,ENQUEUE1,ENQUEUE2,ENQUEUE3,DEQUEUE1,ENQUEUE4,DEQUEUE2,ENQUEUE5,ENQUEUE6,ENQUEUE7,ENQUEUE8,q1,q2,q3,q4,q5,q6,q7,q8,循环队列 （circular queue）,F,R,F,R,F,R,

14、R,R,R,R,R,R,入队操作时的尾指针运算: rear=(rear+1)%Maxsize 出队操作时的头指针运算: front=(front+1)%Maxaize 问题：在循环队列中，由于队空时有front=rear；队满时也有front=rear；因此我们无法通过front=rear来判断队列是“空”还是“满”。,循环队列示意图,循环队列的几种状态,循环队列队满和队空的描述方法,队空:,队满:,rear=front（?）,rear=front,判断循环队列满和空的三种方法,如何判断是“空”还是“满”。 解决这个问题的方法至少有三种： 设一布尔变量以区别队列的空和满，设置标志flag- f

15、lag=0 表示空，flag=1 表示满， front 追上 rear 则 flag=0， rear 追上 front 则 flag=1 ； 留下一个单元不使用。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满，则 rear 永远也追不上 front ； 使用一个计数器记录队列中元素的总数（即队列长度）。,顺序循环队列的类型定义,#define QueueSize 100 /应根据具体情况定义该值 typedef char DataType; /DataType的类型依赖于具体的应用 typedef struct int front; /头指针，队非空时指向队头元素 i

16、nt rear; /尾指针，队非空时指向队尾元素的下一位置 int count; /计数器，记录队中元素总数 DataType dataQueueSize CirQueue;,顺序循环队列的基本运算,1.置队空 2.判队空 3.判队满 4.入队 5.出队 6.取队头元素, 置队空,void InitQueue(CirQueue *Q) Q-front=Q-rear=0; Q-count=0; /计数器置0 , 判队空,int QueueEmpty(CirQueue *Q) /队列无元素为空，属第三种方法 return Q-count=0; int QueueEmpty(CirQueue *Q)

17、 /属第二种方法 return Q-rear=Q-front; , 判队满,int QueueFull(CirQueue *Q) return Q-count=QueueSize; /队中元素个数等于QueueSize时队满，属第三种方法 int QueueFull(CirQueue *Q) return (Q-rear+1)%QueueSize=Q-front ; /队中元素个数等于QueueSize时队满，属第二种方法 , 入队,void EnQueue(CirQueue *Q,DataType x) if(QueueFull(Q) Error(“Queue overflow“); /队满

18、上溢 Q-count +; /队列元素个数加1 Q-dataQ-rear=x; /新元素插入队尾 Q-rear=(Q-rear+1)%QueueSize; /循环意义下将尾指针加1 , 出队,DataType DeQueue(CirQueue *Q) DataType temp; if(QueueEmpty(Q) Error(“Queue underflow“); /队空下溢 temp=Q-dataQ-front; Q-count-; /队列元素个数减1 Q-front=(Q-front+1)%QueueSize; /*循环意义下的头指针加1*/ return temp; ,取队头元素,Dat

19、aType QueueFront(CirQueue *Q) if(QueueEmpty(Q) Error(“Queue if empty.“); return Q-dataQ-front; ,2.3链队列,2.3.1 链队列的定义 2.3.2 链队列的基本运算,2.3.1 链队列的定义,队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。,队头在链头，队尾在链尾。,q.front q.rear,q.front q.rear,空队列,链队列的几种状态示意图,此时，front=rear,修改rear指针,修改头结点的指针域,链队列为空的特征：front=rear, 链队列会满吗

20、？,一般不会，因为删除时有free动作，除非内存不足！,修改rear指针,注意,增加指向链表上的最后一个结点的尾指针，便于在表尾做插入操作,和链栈类似，无须考虑判队满的运算及上溢。 在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。 以上讨论的是无头结点链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增加头结点的链队列的基本运算,链队列的存储结构,typedef char DataType; typedef struct queuenode DataType dat

21、a; struct queuenode *next; QueueNode; typedef struct QueueNode * front; QueueNode *rear; LinkQueue;,2.3.2 链队列的基本运算,1.置空队 2.判队空 3.入队 4.出队 5.取队头元素,（1） 置空队,int InitQueue( LinkQueue *Q ) /构造一个空队列 *Q Q-front = (LQnode *)malloc(sizeof(LQnode); if( Q-front = NULL ) return FALSE; /申请内存失败返回 Q-rear = Q-front;

22、 Q-front- next = NULL; return TRUE; /申请内存成功返回 ,（2） 判队空,int QueueEmpty(LinkQueue *Q) return Q- front- next =NULL /*实际上只须判断队头指针是否为空即可*/ ,（3） 入队,void EnQueue(LinkQueue *Q,DataType x) /将元素x插入链队列尾部 QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode); /申请新结点 p-data=x; p-next=NULL; if(QueueEmpty(Q) Q-front-

23、next=p; Q-rear=p; /将x插入空队列 else /x插入非空队列的尾 Q-rear-next=p; /*p链到原队尾结点后 Q-rear=p; /队尾指针指向新的尾 ,（4） 出队,DataType DeQueue (LinkQueue *Q) DataType x; QueueNode *p; if(QueueEmpty(Q) Error(“Queue underflow”);/下溢 p=Q-front-next; /指向队头结点 x=p-data; /保存队头结点的数据 Q-front-next=p-next; /将队头结点从链上摘下 if(Q-rear=p)/原队中只有一

24、个结点，删去后队列变空，此时队头指针已为空 Q-rear= Q-front; free(p); /释放被删队头结点 return x; /返回原队头数据 ,（5） 取队头元素,DataType QueueFront(LinkQueue *Q) if(QueueEmpty(Q) Error(“Queue if empty.“); return Q-front-next-data; ,3. 栈的应用,递归、非递归,数据结构-第3章 栈和队列,66,递归、非递归,递归的含义 函数、过程或者数据结构的内部又直接或者间接地由自身定义。 适合于应用递归的场合 规模较大的问题可以化解为规模较小的问题，且二者

25、处理(或定义)的方式一致； 当问题规模降低到一定程度时是可以直接求解的(终止条件) 例1. 阶乘 n!= 1 n=0 n(n-1)! n0,数据结构-第3章 栈和队列,67,写递归算法应注意的问题,递归算法本身不可以作为独立的程序运行，需在其它的程序中设置调用初值，进行调用； 递归算法应有出口(终止条件) 例1. 求n！,int Factorial(int n) if (n=0) return(1); return n*Factorial(n-1); /Factorial,数据结构-第3章 栈和队列,68,递归算法的实现原理,1,2,3,- 利用栈，栈中每个元素称为工作记录，分成三个部分： 返

26、回地址 实际参数表(变参和值参) 局部变量 - 发生调用时，保护现场，即当前的工作记录入栈，然后 转入被调用的过程 - 一个调用结束时，恢复现场，即若栈不空，则退栈，从 退出的返回地址处继续执行下去,69,递归时系统工作原理示例,int Factorial( int n) L1: if ( n=0 ) L2: return 1; L3: else return n*Factorial(n-1); L4: /Factorial void main(void) L0: N=Factorial(3); /main 返回地址 n Factorial N,L0 3 / /,L3 3 /,L3 2 /,L

27、3 1 /,1,1,2,6,数据结构-第3章 栈和队列,70,递归算法的用途,求解递归定义的数学函数 在以递归方式定义的数据结构上的运算/操作 可用递归方式描述的解决过程 递归算法的特点 递归算法简单明了，直观易懂 时间效率低，空间开销大，算法不易优化,数据结构-第3章 栈和队列,71,递归转换为非递归的方法,1）采用迭代算法 递归从顶到底 迭代从底到顶 例：求n！ int fact(int n) m=1; for ( i=1; i= n; i+) m=m*i; return m; /fact,数据结构-第3章 栈和队列,72,2）消除尾递归,例：顺序输出单链表中的结点数据 void link

28、list_output(LNode *p); if (p) printf(p-data); linklist_output(p-next) /linklist_output,使用跳转语句： void linklist_output1(LNode *p) 1: if ( p ) printf(p-data); p=p-next; goto 1 /linklist_output1,使用循环语句： void linklist_output2(LNode *p) while ( p ) printf(p-data); p=p-next; /linklist_output2,p,an,a 2,a1,数据

29、结构-第3章 栈和队列,73,3)对递归算法改写通用方法（利用栈模拟递归）,如果是递归函数，需改写为递归过程 例：求n! void fact(int n, int 2: f=n*f /fact,InitStack(S);,Push( S, (2, n, f ); n=n-1; goto 0;,if ( !StackEmpty(S) ) (S.top-1)-f=f; /还原本层变参值 Pop(S, (rd, n, f) ); goto rd ; ,74,自设栈模拟系统工作栈,例：typedef struct int rd; int n; int f; SElemType; 改写算法 在程序开头增加栈的初始化语句 改写递归调用语句 入栈处理； 确定调用的参数值； 转至调用的开始语句 改写所有递归出口 退栈还原参数； 转至返回地址处,S,rd n f,top,void fact(int n; int /fact,void fact(int n; int /fact,注：此时可确定栈中只 存放n值即可。 typedef int SElemType;,