《三章节栈和队列.ppt》由会员分享，可在线阅读，更多相关《三章节栈和队列.ppt（116页珍藏版）》请在三一办公上搜索。
1、第三章 栈和队列,引言,栈和队列是一类特殊的线性表。其特殊性表现在其删除和插入操作受限制。对于栈，用户只能在一个端点进行插入和删除操作。对于队列，允许在一个端点进行插入操作，在另一个端进行删除操作。栈的最重要特性是先进后出，或者后进先出。这在程序设计中非常有用。队列的重要特性是先到先服务。栈和队列广泛应用于程序设计中。特别是栈，在表达式处理、函数调用等方面有广泛的应用。,3.1 栈,栈的定义顺序栈链栈栈的应用举例,3.1.1 栈的定义,只允许在某一端进行插入或删除操作的线性表称为栈。允许插入和删除的一端被称为栈顶。另一端为栈底。大家不妨去思考一下，只允许一端插入和删除操作，会有什么好处，也会带
2、来哪些问题？,栈的图示,栈底,栈顶,栈的性质,(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。(2)当表中没有元素时称为空栈。(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表,先进后出(FILO),栈的示意图,元素是以a1，a2，an的顺序进栈，退栈的次序却是an，an-1，a1。,栈的基本运算,（1）InitStack（S）构造一个空栈S。（2）ClearStack（S）（3）IsEmpty（S）判栈空。若S为空栈，则返回TRUE，否则返回FALSE。（4）IsFull（S）判栈满。若S为满栈，则返回TRUE，否则返回FALS
3、E。注意：该运算只适用于栈的顺序存储结构。,栈的基本操作（续）,（5）Push（S，x）进栈。若栈S不满，则将元素x插入S的栈顶。（6）Pop（S,x）退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。（7）GetTop（S）取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。,3.1.2栈的表示和实现,顺序栈栈链,顺序栈,顺序栈的定义存储类型定义 上溢与下溢基本操作,顺序栈,栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。,顺序栈的类型定义,#define Stack_Size 100/假定预分配的栈空间最多为100个元素typedef char DataType;/假定栈元素
4、的数据类型为字符typedef struct StackElementType elemStack_Size;int top;SeqStack;,进栈的基本操作,进栈时，需要将S-top加1，并把元素保存到栈顶位置。注意：S-top=StackSize-1表示栈满上溢现象-当栈满时，再做进栈运算产生空间溢出的现象。上溢是一种出错状态，应设法避免。,退栈操作,退栈时，需将S-top减1，并把栈顶元素取出。注意：S-top0表示空栈 下溢现象当栈空时，做退栈运算产生的溢出现象。下溢是正常现象，常用作程序控制转移的条件。,置栈空（初始化）,void InitStack（SeqStack*S）/将顺序
5、栈置空 S-top=-1;,判栈空,int IsEmpty（SeqStack*S）return S-top=-1;,（3）判栈满,int IsFull（SeqStack*S）return S-top=StackSize-1;,（4）进栈,void Push（SeqStack*S，StackElementType x）if(IsFull(S)Error(Stack overflow);/上溢，退出运行 S-elem+S-top=x;/栈顶指针加1后将x入栈,退栈操作,int Pop(SeqStack*s,StackElementType*x)if(IsEmpty(S)Error(“Stack u
6、nderflow”);/下溢，退出运行*x=S-dataS-top-;return true;,（6）取栈顶元素,int StackTop(SeqStack*S,StackElementType*x）if(IsEmpty(S)Error(Stack is empty);else*x=S-dataS-top;return true;,4.两个栈共享同一存储空,当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。只有当整个向量空间被两个栈占满（即两个栈顶相遇
7、）时，才会发生上溢。因此，两个栈共享一个长度为m的向量空间和两个栈分别占用两个长度为 m/2和m/2的向量空间比较，前者发生上溢的概率比后者要小得多。,二个栈共享空间的示意图,思考题,如何判断栈空？如何判断栈满？存储结构？,二个栈共享存储空间的存储结构,define M 100typedef struct StackElementType StackM;int top2;DqStack;,练习,void InitStack(DqStack*s);int Push(DqStack*s,StackElementType x,int i);,链栈,栈的链式存储结构称为链栈。,链栈的存储结构,type
8、def struct node StackElementType data struct node*next LinkStackNode;typedef LinkStackNode*LinkStack;,进栈操作,int Push(LinkStack top,StackElementtype x)temp=(LinkStackNode*)malloc(sizeof(LinkstackNode);if(temp=NULL)return FALSE;temp-data=x;temp-next=top-next;top-next=temp;return TRUE;,退栈操作,Int Pop(Link
9、Stack top,StackElementType*x)LinkStackNode*temp;temp=top-next;if(temp=NULL)return FALSE;top-next=temp-next;*x=temp-data;free(temp);return TRUE;,栈的应用,1.括号匹配2.中缀表达式，后缀表达，前缀表达式相互转换。3.老鼠闯迷宫4.栈与函数递归调用,括号匹配,int BrackMatch(char*str)Stack s;int I;char ch;InitStack(i+),switch(stri)case(:case:case:Push(,else
10、GetTop(,if(IsEmpty(,栈的应用数制转换,将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题，很容易通过“除B取余法”来解决【例】将十进制数13转化为二进制数。解答：按除2取余法，得到的余数依次是1、0、1、1，则十进制数转化为二进制数为1101。分析：由于最先得到的余数是转化结果的最低位，最后得到的余数是转化结果的最高位，因此很容易用栈来解决。,typedef int DataType;/应将顺序栈的DataType定义改为 void MultiBaseOutput(int N,int B)/假设N是非负的十进制整数，输出等值的B进制数int i;SeqStac
11、k S;InitStack(,例：数制的转换,数制转换 将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题，很容易通过“除B取余法”来解决。,例,【例】将十进制数13转化为二进制数。解答：按除2取余法，得到的余数依次是1、0、1、1，则十进制数转化为二进制数为1101。分析：由于最先得到的余数是转化结果的最低位，最后得到的余数是转化结果的最高位，因此很容易用栈来解决。,转换算法如下,typedef int DataType;/应将顺序栈的DataType定义改为整型void MultiBaseOutput(int N,int B)/假设N是非负的十进制整数，输出等值的B进制数in
12、t i;SeqStack S;InitStack(,表达式处理,把中置表达式转化为后置表达式a=5,b=4,c=3 d=2,e=5(a+b*c)/d-e 是中置表达式后置表达式 abc*+d/e-问题1如何把中置表达式转换为后置表达式利用求后置表达式的值,栈的应用之二表达式求值,表达式求值是计算机程序设计中一个经常遇到而且非常重要的问题。它广泛用在编译程序、操作系统和脚本程序中。,表达式的求值过程,表达式字符串,后置表达式,求后置表达式的值,（中置表达式）,一.中置表达式转换为后置表达式,设置一个专门保存运算符的栈，保存暂时不能处理的运算符，我们称它为运算符栈。规定运算符的优先级别。,运算符的
13、优先级别,我们假定表达式中只有+-*/四个运行符和括号，而且括号也是运算符。为了处理方便，人为规定一个特殊的字符$，在处理表达式之前，先把它压入栈里它在栈内的优先级是最低。因此它们的优先级别如下表,转换过程,1.从左到右逐个扫描整个表达式，若当前的运算符比栈顶的运算符优级高，进栈，否则出栈。2.如果当前字符是左括号，进栈（请大家讨论，为什么）。3.如果当前字符是右括号，则出栈，直到遇到左括号为止。4.如果当前字符是操作数，直接输出。,转换过程举例,得到后置表达为 abc*+d/e-,有表达(a+b*c)/d-e,算法描述,详细描述算法ExpressTrans.txt,思考题,在这个算法里，我们
14、假定表达式是正确的，如果不正确，如括号不匹配，运算符不正确或缺少操作数，怎么办？实际中，表达式远比这个复杂，但是处理方法还是一样的。,说明,把中缀表达式转换为后置表达式实质就是去括号，同时重新排列表达。把运算符放在运算数后面。那么如何求后置表达式的值呢？,二.对后置表达式求值,设置一个操作数栈，对后置表达式进行扫描，遇到操作数进栈，遇到操作符退栈(退2次，以除为例，第一次退出是除数，第二次被除数），进行运算，并把运算结果再进栈。当表达式处理完毕时，得到的结果就是表达式的值值。,举例说明,后置表达为abc*+d/e-变量的值为a=6,b=4,c=3 d=2,e=5,算法,后置表达式求值算法算法后
15、置表达式求值.txt,思考题,当运算中存在错误，如除数为零，怎么办？,迷宫问题,有一个迷宫，一个老鼠从入口进来，在迷宫里找出一个出口。,迷宫,出口,入口,白色表示通路，蓝色的表示墙,解题的思路,当老鼠走到某个位置，前面没有路可走时，怎么办？要沿着老路回去。退回到哪里呢？退回到刚走的位置。这正好符合栈的特征，最近的最先出来。,需要解决的几个问题,迷宫如何表示？位置如何保存在栈里？如何确定当前位置是否有出路？如何表示已经走过的位置？,迷宫的表示,用一个比较大的二维数组表示迷宫，每一格子相当于一个元素，除了入口和出口外，最外层的元素置1，随机地给其他元素置1或置0。1表示障碍，0表示通路。,栈里的元
16、素,栈里的元素表示某个位置，某个位置用行和列表示，因此要定义typedef struct int x;int y;CELL;typedef CELL StackElementType;./书上关于栈基本运算,程序框架,typedef struct int x;int y;CELL;typedef CELL DataType;main()int Maze1010=1,1,1,1,1,1,1,1,1,1,.;SeqStack S;CELL start=1,0,end=8,9;,Push(S,start);while(1)p=Pop(S);if(p=end)printf(“成功”):输出迷宫 找出p
17、的下一个格位置 如果找到的话，把该格置1，同时入栈 如果找不到，如果栈是空，根本不存在通路 如果栈不空，退栈,栈与函数,栈与函数调用系统栈，专门用来保存与函数调用有关的信息，保证函数调用的正确性。,main()f1();addr1:.f2();addr2:,void f1(.)int a=23;f2();addr3:.f3();addr4,f3()f2();addr5:,f2(),栈与函数,在调用函数之前，把相应的数据入栈，同时把下一语句的地址入栈。在函数结束时，把栈里的地址出栈，同时把相应的数据也出栈。,3.2 队列,队列的定义队列的表示与实现队列的应用,1.队列的定义,队列（Queue）是
18、只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。,2.队列的性质,（1）允许删除的一端称为队头（Front）（2）允许插入的一端称为队尾（Rear）（3）当队列中没有元素时称为空队列（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表,(1)初始化队列,InitQueue（&Q）,构造一个空队列Q。,(2).判队空,IsEmpty（Q）判队空。若队列Q为空，则返回真值，否则返回假值,（3）判队满,IsFull（Q）若队列Q为满，则返回真值，否则返回假值。,（4）入队,EnterQueue（&Q，x）若队列Q非满，则将元素x插入Q的队尾。此操作简
19、称入队。,（5）出队,DeleteQueue（&Q,&x）若队列Q非空，则删去Q的队头元素，并返回该元素。此操作简称出队。,（6）取队首元素,GetHead（Q,&x）若队列Q非空，则返回队头元素，但不改变队列Q的状态。,（7）队列清空,ClearQueue（&Q）队列置空操作，把队列Q置为空队列。,（8）销毁队列,DestroyQueue（&Q）队列销毁操作，释放队列空间。,队列的存储表示,顺序队列链队列,3.2.2顺序队列,顺序队列的定义顺序队列的实现,（1）顺序队列的定义,队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表,（2）顺序队列的表示,和顺序表一样，顺序队列用一个
20、向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，设置两个“指针”front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。,假溢出,front,rear,顺序队列的基本操作,入队时：将新元素插入rear所指的位置，然后将rear加1。出队时：删去front所指的元素，然后将front加1并返回被删元素。注意：当头尾指针相等时，队列为空。在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。顺序队列基本操作,2、循环队列,为充分利用向量空间，克服假上溢现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量
21、为循环向量。存储在其中的队列称为循环队列（Circular Queue）。,循环队列示意图,循环队列举例,G,F,D,E,H,I,J,%rear=(rear+1)%8rear=front?(rear+1)%8=front count=0,（2）循环队列边界条件处理,如何判断是“空”还是“满”。解决这个问题的方法至少有三种：另设一布尔变量以区别队列的空和满；少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；使用一个计数器记录队列中元素的总数（即队列长度）。,循环队列的类型定义,#define MAXSIZE 100/
22、应根据具体情况定义该值typedef struct QueueElementType elementMAXSIZE;int front;int rear;SeqQueue;,循环队列的基本运算,置队空,void InitQueue(SeqQueue*Q)Q-front=Q-rear=0;,判队空,int IsEmpty(SeqQueue*Q)return Q-rear=Q-front;,判队满,int IsFull(SeqQueue*Q)return(Q-rear+1)%MAXSIZE=Q-front;,入队,int EnterQueue(SeqQueue*Q,QueueElementType
23、 x)if(IsFull(Q)return falseQ-dataQ-rear=x;/新元素插入队尾Q-rear=(Q-rear+1)%MAXSIZE;/循环意义下将尾指针加 return true;,出队,int DeleteQueue(SeqQueue*Q,QueueElementType*x)if(IsEmpty(Q)return false;*x=Q-dataQ-front;Q-front=(Q-front+1)%MAXSIZE;return true;,写一个函数求队列的元素的个数,int QueueNumber（CirQueue*Q)return(Q-rear-Q-front+MA
24、XSIZE)%MAXSIZE;/某一年的考试题目,3.2.3链队列,删除（出队）,插入（入队）,1、链队列的定义,队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。,2、链队列的结构类型说明,注意,增加指向链表上的最后一个结点的尾指针，便于在表尾做插入操作,注意：和链栈类似，无须考虑判队满的运算及上溢。在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。以上讨论的是无头结点链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增加头结点的链队列的基本运
25、算,定义链队列的存储结构,typedef char DataType;typedef struct queuenode DataType data;struct queuenode*next;QueueNode;typedef struct QueueNode*front;QueueNode*rear;LinkQueue;,（1）置空队,void InitQueue(LinkQueue*Q)Q-front=Q-rear=NULL;,（2）判队空,int QueueEmpty(LinkQueue*Q)return Q-front=NULL/实际上只须判断队头指针是否为空即可,（3）入队,void
26、 EnQueue(LinkQueue*Q,DataType x)/将元素x插入链队列尾部 QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode);/申请新结点p-data=x;p-next=NULL;if(QueueEmpty(Q)Q-front=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)Err
27、or(“Queue underflow”);/下溢 p=Q-front;/指向对头结点 x=p-data;/保存对头结点的数据 Q-front=p-next;/将对头结点从链上摘下 if(Q-rear=p)/原队中只有一个结点，删去后队列变空，此时队头指针已为空 Q-rear=NULL;free(p);/释放被删队头结点 return x;/返回原队头数据,（5）取队头元素,DataType QueueFront(LinkQueue*Q)if(QueueEmpty(Q)Error(Queue if empty.);return Q-front-data;,（1）置空队,void InitQue
28、ue(LinkQueue*Q),（2）判队空,int QueueEmpty(LinkQueue*Q),（3）入队,void EnQueue(LinkQueue*Q,DataType x)/将元素x插入链队列尾部,（4）出队,DataType DeQueue(LinkQueue*Q),（5）取队头元素,DataType QueueFront(LinkQueue*Q),（1）置空队,void InitQueue(LinkQueue*Q)Q-front=Q-rear=NULL;,（2）判队空,int QueueEmpty(LinkQueue*Q)return Q-front=NULL/实际上只须判断
29、队头指针是否为空即可,（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=Q-rear=p;/将x插入空队列else/x插入非空队列的尾 Q-rear-next=p;/*p链到原队尾结点后 Q-rear=p;/队尾指针指向新的尾,（4）出队,DataType DeQueue(LinkQueue*Q)DataType x;QueueNode*
30、p;if(QueueEmpty(Q)Error(“Queue underflow”);/下溢 p=Q-front;/指向对头结点 x=p-data;/保存对头结点的数据 Q-front=p-next;/将对头结点从链上摘下 if(Q-rear=p)/原队中只有一个结点，删去后队列变空，此时队头指针已为空 Q-rear=NULL;free(p);/释放被删队头结点 return x;/返回原队头数据,（5）取队头元素,DataType QueueFront(LinkQueue*Q)if(QueueEmpty(Q)Error(Queue if empty.);return Q-front-data;,
