三章节栈和队列.ppt

第三章 栈和队列,引言,栈和队列是一类特殊的线性表。其特殊性表现在其删除和插入操作受限制。对于栈，用户只能在一个端点进行插入和删除操作。对于队列，允许在一个端点进行插入操作，在另一个端进行删除操作。栈的最重要特性是先进后出，或者后进先出。这在程序设计中非常有用。队列的重要特性是先到先服务。栈和队列广泛应用于程序设计中。特别是栈，在表达式处理、函数调用等方面有广泛的应用。,3.1 栈,栈的定义 顺序栈 链栈 栈的应用举例,3.1.1 栈的定义,只允许在某一端进行插入或删除操作的线性表称为栈。允许插入和删除的一端被称为栈顶。另一端为栈底。 大家不妨去思考一下，只允许一端插入和删除操作，会有什么好处，也会带来哪些问题？,栈的图示,栈底,栈顶,栈的性质,(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，否则返回FALSE。 注意： 该运算只适用于栈的顺序存储结构。,栈的基本操作（续）,（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;/假定栈元素的数据类型为字符 typedef struct StackElementType elemStack_Size; int top; SeqStack;,进栈的基本操作,进栈时，需要将S-top加1，并把元素保存到栈顶位置。 注意： S-top=StackSize-1表示栈满 “上溢“现象-当栈满时，再做进栈运算产生空间溢出的现象。 上溢是一种出错状态，应设法避免。,退栈操作,退栈时，需将S-top减1，并把栈顶元素取出。 注意： S-top0表示空栈 “下溢“现象当栈空时，做退栈运算产生的溢出现象。 下溢是正常现象，常用作程序控制转移的条件。,置栈空（初始化）,void InitStack（SeqStack *S） /将顺序栈置空 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 underflow”); /下溢，退出运行 *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.两个栈共享同一存储空,当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。 只有当整个向量空间被两个栈占满（即两个栈顶相遇）时，才会发生上溢。因此，两个栈共享一个长度为m的向量空间和两个栈分别占用两个长度为 m/2和m/2的向量空间比较，前者发生上溢的概率比后者要小得多。,二个栈共享空间的示意图,思考题,如何判断栈空？ 如何判断栈满？ 存储结构？,二个栈共享存储空间的存储结构,define M 100 typedef struct StackElementType StackM; int top2; DqStack;,练习,void InitStack(DqStack *s); int Push(DqStack *s,StackElementType x,int i);,链栈,栈的链式存储结构称为链栈。,链栈的存储结构,typedef 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(LinkStack 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 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; SeqStack 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进制数 int i; SeqStack S; InitStack( ,表达式处理,把中置表达式转化为后置表达式 a=5,b=4,c=3 d=2,e=5 (a+b*c)/d-e 是中置表达式 后置表达式 abc*+d/e- 问题1如何把中置表达式转换为后置表达式 利用求后置表达式的值,栈的应用之二表达式求值,表达式求值是计算机程序设计中一个经常遇到而且非常重要的问题。它广泛用在编译程序、操作系统和脚本程序中。,表达式的求值过程,表达式字符串,后置表达式,求后置表达式的值,（中置表达式）,一.中置表达式转换为后置表达式,设置一个专门保存运算符的栈，保存暂时不能处理的运算符，我们称它为运算符栈。 规定运算符的优先级别。,运算符的优先级别,我们假定表达式中只有+ - * /四个运行符和括号，而且括号也是运算符。 为了处理方便，人为规定一个特殊的字符$，在处理表达式之前，先把它压入栈里它在栈内的优先级是最低。因此它们的优先级别如下表,转换过程,1.从左到右逐个扫描整个表达式，若当前的运算符比栈顶的运算符优级高，进栈，否则出栈。 2.如果当前字符是左括号，进栈（请大家讨论，为什么）。 3.如果当前字符是右括号，则出栈，直到遇到左括号为止。 4.如果当前字符是操作数，直接输出。,转换过程举例,得到后置表达为 abc*+d/e-,有表达 (a+b*c)/d-e,算法描述,详细描述算法ExpressTrans.txt,思考题,在这个算法里，我们假定表达式是正确的，如果不正确，如括号不匹配，运算符不正确或缺少操作数，怎么办？ 实际中，表达式远比这个复杂，但是处理方法还是一样的。,说明,把中缀表达式转换为后置表达式实质就是去括号，同时重新排列表达。把运算符放在运算数后面。 那么如何求后置表达式的值呢？,二.对后置表达式求值,设置一个操作数栈，对后置表达式进行扫描，遇到操作数进栈，遇到操作符退栈(退2次，以除为例，第一次退出是除数，第二次被除数），进行运算，并把运算结果再进栈。当表达式处理完毕时，得到的结果就是表达式的值值。,举例说明,后置表达为abc*+d/e- 变量的值为a=6,b=4,c=3 d=2,e=5,算法,后置表达式求值算法算法后置表达式求值.txt,思考题,当运算中存在错误，如除数为零，怎么办？,迷宫问题,有一个迷宫，一个老鼠从入口进来，在迷宫里找出一个出口。,迷宫,出口,入口,白色表示通路，蓝色的表示墙,解题的思路,当老鼠走到某个位置，前面没有路可走时，怎么办？要沿着老路回去。退回到哪里呢？退回到刚走的位置。这正好符合栈的特征，最近的最先出来。,需要解决的几个问题,迷宫如何表示？ 位置如何保存在栈里？ 如何确定当前位置是否有出路？ 如何表示已经走过的位置？,迷宫的表示,用一个比较大的二维数组表示迷宫，每一格子相当于一个元素，除了入口和出口外，最外层的元素置1，随机地给其他元素置1或置0。 1表示障碍，0表示通路。,栈里的元素,栈里的元素表示某个位置，某个位置用行和列表示，因此要定义 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的下一个格位置 如果找到的话，把该格置1，同时入栈 如果找不到，如果栈是空，根本不存在通路 如果栈不空，退栈 ,栈与函数,栈与函数调用 系统栈，专门用来保存与函数调用有关的信息，保证函数调用的正确性。,main() f1(); addr1: . f2(); addr2: ,void f1(.) int a=23; f2(); addr3: f3(); addr4 ,f3() f2(); addr5: ,f2() ,栈与函数,在调用函数之前，把相应的数据入栈，同时把下一语句的地址入栈。 在函数结束时，把栈里的地址出栈，同时把相应的数据也出栈。,3.2 队列,队列的定义 队列的表示与实现 队列的应用,1.队列的定义,队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。,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的队尾。此操作简称入队。,（5）出队,DeleteQueue（&Q,&x） 若队列Q非空，则删去Q的队头元素，并返回该元素。此操作简称出队。,（6）取队首元素,GetHead（Q,&x） 若队列Q非空，则返回队头元素，但不改变队列Q的状态。,（7）队列清空,ClearQueue（&Q） 队列置空操作，把队列Q置为空队列。,（8）销毁队列,DestroyQueue（&Q） 队列销毁操作，释放队列空间。,队列的存储表示,顺序队列 链队列,3.2.2顺序队列,顺序队列的定义 顺序队列的实现,（1）顺序队列的定义,队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表,（2） 顺序队列的表示,和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。 由于队列的队头和队尾的位置是变化的，设置两个“指针”front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。,假溢出,front,rear,顺序队列的基本操作,入队时：将新元素插入rear所指的位置，然后将rear加1。 出队时：删去front所指的元素，然后将front加1并返回被删元素。 注意： 当头尾指针相等时，队列为空。 在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。 顺序队列基本操作,2、循环队列,为充分利用向量空间，克服“假上溢“现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。,循环队列示意图,循环队列举例,G,F,D,E,H,I,J,% rear=(rear+1)%8 rear= =front? (rear+1)%8=front count=0,（2） 循环队列边界条件处理,如何判断是“空”还是“满”。 解决这个问题的方法至少有三种： 另设一布尔变量以区别队列的空和满； 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）； 使用一个计数器记录队列中元素的总数（即队列长度）。,循环队列的类型定义,#define MAXSIZE 100 /应根据具体情况定义该值 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 x) if(IsFull(Q) return false Q-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 +MAXSIZE)%MAXSIZE; /某一年的考试题目,3.2.3链队列,删除（出队）,插入（入队）,1、 链队列的定义,队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。,2、 链队列的结构类型说明,注意,增加指向链表上的最后一个结点的尾指针，便于在表尾做插入操作,注意： 和链栈类似，无须考虑判队满的运算及上溢。 在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。 以上讨论的是无头结点链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增加头结点的链队列的基本运算,定义链队列的存储结构,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 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) 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; ,（1） 置空队,void InitQueue(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 /实际上只须判断队头指针是否为空即可 ,（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 *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; ,