第3章-栈和队列数据结构.pptx

3.1,线性表的基本概念,第,3,章,栈和队列,3.1.1,栈的基本概念,1,栈的定义,栈,(Stack),是限制在表的一端进行插入和删除运算的线性表。通常称插入、删除的这一端（表尾端）为栈顶,(Top),，另一端（表头端）为栈底,(Bottom),。当表中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。,3.1,线性表的基本概念,第,3,章,栈和队列,2,栈,的基本操作,栈,作为运算受限的线性表，其基本操作除了入栈、出栈外，还有建立堆栈（栈的初始化）、判断栈是否为空、判断栈是否满及获取栈顶元素等操作。,（,1,）,InitStack(S),初始化操作，其作用是将栈,S,置为空栈。,（,2,）,ClearStack(S),清栈操作，其作用是将已经存在的栈,S,置成空栈。,（,3,）,IsEmpty(S),判栈空操作，其作用是判断已存在的栈,S,，若,S,为空栈，则返回,TRUE,，否则返回,FALSE,。,3.1,线性表的基本概念,第,3,章,栈和队列,（,4,）,IsFull(S),判栈满操作，其作用是判断已存在的栈,S,是否已满，若,S,为满栈，则返回,TRUE,，否则返回,FALSE,。,（,5,）,Push(S,x),入栈操作，其作用是将元素,x,插入栈,S,中，使,x,成为栈,S,新的栈顶元素。,（,6,）,Pop(S,&x),出栈操作，其作用是当栈非空时，删除,(,亦称弹出,)S,的栈顶元素，并用,x,带回该值。,（,7,）,GetTop(S,&x),取栈顶元素操作，当栈非空时，取出,S,的栈顶元素，与,Pop(S,&x),的不同之处在于,GetTop(S,&x),不改变栈顶的位置。,3.1,线性表的基本概念,第,3,章,栈和队列,3.1.2,栈,的存储结构和操作实现,1,顺序栈,栈,的顺序存储结构简称为顺序栈，它是运算受限的顺序表。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组两端的任何一个端点；栈顶位置是随着入栈和出栈操作而变化的，故需用一个变量,top,来指示当前栈顶的位置，通常称,top,为栈顶指针。,3.1线性表的基本概念,第,3,章,栈和队列,顺序栈可以用,C,语言描述如下：,#define TRUE 1,#define FALSE 0,#define Stack_Size 50,/*Stack_Size,为栈的最大容量*,/,typedef struct,StackDataType,dataStack_Size;/*,用来存放栈中数据元素的一维数组,，,StackDataType,为栈中元素的类型*,/,int,top;,/*,栈顶指针，用来存放栈顶元素的下标*,/,SeqStack;,SeqStack,*S;,/*,定义一个指向顺序栈的指针变量*,/,3.1,线性表的基本概念,第,3,章栈和队列,图,3-2,顺序栈的操作示意图,3.1,线性表的基本概念,第,3,章,栈和队列,2,顺序栈的实现,（,1,）初始化,void InitStack(SeqStack*S),/*,构造一个空栈,S*/,S-,top=-1;,（,2,）判别栈是否为空,int,IsEmpty(SeqStack*S)/*,判栈,S,为空栈时返回值为真，反之为假*,/,if(S-,top=-1),return,TRUE;,else,return FALSE;,3.1,线性表的基本概念,第,3,章,栈和队列,（,3,）判别栈是否满,int,IsFull(SeqStack*S),if(S-,top=Stack_Size-1),return,TRUE;,else,return FALSE;,（,4,）入栈,int Push(SeqStack*S,StackDataType x),if(S-,top=Stack_Size-1),return(FALSE,);,/*,栈已满*,/,S-,top+;,S-,dataS-top=x;,return(TRUE,);,3.1,线性表的基本概念,第,3,章,栈和队列,（,5,）出栈,int Pop(SeqStack*S,StackDataType*x),/*,将栈,S,的栈顶元素弹出，放到,x,所指的存储空间中*,/,if(S-,top=-1)/*,栈为空*,/,return(FALSE,);,else,*,x=S-dataS-top;,S-,top-;,/*,修改栈顶指针*,/,return(TRUE,);,3.1,线性表的基本概念,第,3,章,栈和队列,（,6,）取栈顶元素,int GetTop,（,SeqStack*S,StackDataType*x,）,/*,将栈,S,的栈顶元素弹出，放到,x,所指的存储空间中，但栈顶位置保持不变*,/,if(S-,top=-1)/*,栈为空*,/,return(FALSE,);,else,*x=S-dataS-top;,return(TRUE);,3.1,线性表的基本概念,第,3,章,栈和队列,3,两栈共享空间,栈的应用非常广泛，经常会出现在一个程序中需要同时使用多个栈的情况。若使用顺序栈，会因为对栈空间大小难以准确估计，从而产生有的栈溢出、有的栈空间还很空闲的情况。为了解决这个问题，可以让多个栈共享一个足够大的数组空间，通过利用栈的动态特性来使其存储空间互相补充，这就是多栈的共享技术。,在栈的共享技术中最常用的是两个栈的共享技术：它主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间,SM,，将两个栈的栈底分别放在一维数组的两端，分别是,0,，,M-1,。由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。,3.1,线性表的基本概念,第,3,章,栈和队列,两栈共享的数据结构定义如下：,#define M 100,typedef struct,StackDataType,StackM;,int,top2;,/*,top0,和,top1,分别为两个栈顶指示器*,/,DqStack;,3.1,线性表的基本概念,第,3,章,栈和队列,4.,链栈,栈的链式存储结构简称为链栈，它是运算受限的单链表。由于只能在链表头部进行操作，故链栈没有必要像单链表那样附加头结点。链表的表头指针就作为栈顶指针，如,图所,示。,链,栈的示意图,3.1,线性表的基本概念,第,3,章,栈和队列,链栈可用,C,语言描述如下：,typedef struct node,StackDataType,data;,/*,数据域*,/,struct,node *link;,/*,指针域，用于存放下一结点的地址*,/,LinkStackNode,，*,LinkStack;,LinkStack,top,；,/*,栈顶指针*,/,3.1,线性表的基本概念,第,3,章,栈和队列,入栈操作,int Push(LinkStack top,StackDataType x),/*,将数据元素,x,压入栈,top,中*,/,LinkStackNode,*s;,s,=(LinkStackNode*)malloc(sizeof(LinkStackNode);,if(s=NULL)return(FALSE);/*,申请空间失败*,/,s-,data=x;,s-,link=top;,top=s,;/*,修改当前栈顶指针*,/,return(TRUE,);,3.1,线性表的基本概念,第,3,章,栈和队列,出栈操作,int Pop(LinkStack top,StackDataType*x),/*,将栈,top,的栈顶元素弹出，放到,x,所指的存储空间中*,/,LinkStackNode,*s;,s=top,;,if(s,=NULL),/*,栈为空*,/,return(FALSE,);,top=s-,link;,*,x=s-data;,free(s,);,/*,释放存储空间*,/,return(TRUE,);,3.1,线性表的基本概念,第,3,章,栈和队列,3.1.3,栈的应用实例,表达式求值,表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。在本节中，首先讨论算术表达式的两种表示方法，即中缀表示法和后缀表示法，接着讨论后缀表达式求值的算法，最后讨论中缀表达式求值的算法,。,1.,算术表达式的两种表示,通常书写的算术表达式是由操作数和运算符以及改变运算次序的圆括号连接而成的式子。操作数可以是常量、变量和函数，同时还可以是表达式。运算符包括单目运算符和双目运算符两类，单目运算符只要求一个操作数，并被放在该操作数的前面，双目运算符要求有两个操作数，并被放在这两个操作数的中间。单目运算符为取正“,+”,和取负“,-”,，双目运算符有加“,+”,减“,-”,乘“*”和除“,/”,等。为了简便起见，在我们的讨论中只考虑双目运算符,。,3.1,线性表的基本概念,第,3,章,栈和队列,2.,后缀表达式的求值算法,后缀表达式的求值比较简单，扫描一遍即可完成。它需要使用一个栈，假定用,st,表示，其元素类型应为操作数的类型，假定为浮点型,float,，用此栈存储后缀表达式中的操作数、计算过程中的中间结果以及最后结果，同时假定后缀算术表达式以一个字符串的方式提供。,后缀表达式求值算法的基本思路是：把包含后缀算术表达式的字符串定义为一个输入字符串流对象，每次从中读入一个字符（每个运算对象,数据输入结束后输入空格作为分隔符）时，若它是运算符，则表明它的两个操作数已经在栈,st,中，其中栈顶元素为运算符的后一个操作数，栈顶元素的下一个元素为运算符的前一个操作数，把它们弹出后进行相应运算即可，然后把运算结果再压入栈,st,中；否则，读入的字符必为操作数的最高位数字，应把它重新送回输入流中，然后把下一个数据作为浮点数输入，并把它压入到栈,st,中。依次扫描每一个字符（对于浮点数只需扫描它的最高位并一次输入整个浮点数）并进行上述处理，直到整个输入字符串流结束为止，表明后缀表达式计算完毕，最终结果保存在栈中，并且栈中仅存在这一个值把它弹出返回即可。,3.1,线性表的基本概念,第,3,章,栈和队列,3.,中缀表达式的求值算法,如前所述，中缀表达式的求值比较复杂，为了实现中缀表达式的求值，需要使用两个工作栈。一个称做运算符栈,ct,，用以寄存运算符；另一个称做操作数栈,st,，用以寄存操作数和计算过程中的中间结果以及最后结果，和后缀表达式相同，假定中缀算术表达式也以一个字符串的方式提供，同时，为了简化求值过程，假设表达式开始和结束运算符为,#,，且,#,的运算优先级最低。,3.1,线性表的基本概念,第,3,章,栈和队列,中缀,表达式求值算法的基本思路是：,（,1,）置操作数栈为空栈，表达式起始符“,#”,为运算符栈的栈底元素；,（,2,）依次读入中缀表达式字符串流，每次从中读入一个字符时，若它是运算符，则和,ct,栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即,ct,栈顶元素和当前读入的字符均为“,#”,）；否则，读入的字符必为操作数的最高位数字，应把它重新送回输入流中，然后把下一个数据作为浮点数输入，并把它压入到栈,OPND,中。依次扫描每一个字符并进行上述处理，直到整个输入字符串流结束为止，表明中缀表达式计算完毕，最终结果保存在,st,栈中，并且,st,栈中仅存在这一个值，把它弹出返回即可。,3.2,队列,第,3,章,栈和队列,日常生活中，经常遇到排队办事的问题，如：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊，先到的人排在前面，后来的人则排在队尾等候；又如：乘坐公共汽车，应该在车站排队，先到的人排在前面，后来的人则排在后面，然后按顺序上车；此外，队列在程序设计中也经常出现，一个最典型的例子就是操作系统中的作业排队，在允许多道程序运行的计算机系统中，同时有几个作业运行，如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队等等。,3.2,队列,第,3,章,栈和队列,3.2.1,队列的基本概念,1.,队列的定义,队列,(Queue),是另一种运算受限的线性表，它只允许在表的一端插入元素，而在另一端删除元素。通常称插入的一端为队尾,(rear),，删除的一端为队头,(front),。若队列中没有元素，则称为空队列。队列的插入操作被形象地称为入队，删除操作称为出队。,假设队列为,Q=(a1,，,a2,，,，,an),，如图,3-5,所示，,a1,就是队头元素，,an,则是队尾元素。队列中的元素是按照,a1,，,a2,，,，,an,的顺序进入的，退出队列也必须按照同样的次序依次出队，也就是说，只有在,a1,，,a2,，,，,an-1,都离开队列之后，,an,才能退出队列，即先进入队列的成员总是先离开队列。因此队列亦称作先进先出的线性表，简称,FIFO(First In First Out),表。,队列示意图,3.2,队列,第,3,章,栈和队列,2.,队列的,基本操作,队列作为运算受限的线性表，其基本操作除了入队列、出队列外，还有建立队列（队列的初始化）、判断队列是否为空、及获取队头元素等操作。,（,1,）,InitQueue(Q),初始化操作，其作用是将队列,Q,置为空队列。,（,2,）,IsEmpty(Q),判队列是否为空操作，其作用是判断已存在的队列,Q,，若,Q,为空队列，则返回,TRUE,，否则返回,FALSE,。,（,3,）,EnterQueue(Q,，,x),入队操作，其作用是将元素,x,插入,Q,的队尾，使,x,成为,Q,新的队尾元素。,（,4,）,DeleteQueue(Q,&x),出队操作,其作用是当,Q,非空时，删除,Q的队头元素，并用,x,带回该值。,（,5,）,GetHead,（,Q,&x,）取队头元素操作，当队列非空时，取出,Q,的队头元素，与,DeleteQueue(Q,&x),不同之处在于,GetHead,（,Q,&x,）不改变队头位置。,（,6,）,ClearQueue(Q),队列置空操作，将队列,Q,置为空队列。,（,7,）,DestroyQueue(&Q),销毁队列操作，释放队列的空间。,3.2,队列,第,3,章,栈和队列,3.2.2,队列的存储结构和操作,实现,1,队列,的顺序存储,结构,队列的顺序存储结构简称为顺序队列，它也是运算受限的顺序表，即顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针,front,和,rear,，分别指示队头元素和队尾元素在数组中的位置。,3.2,队列,第,3,章,栈和队列,顺序,队列可以用,C,语言描述如下：,#define MaxSize 100,/*,队列的最大容量*,/,typedef struct,QueueDataType,dataMaxSize;/*,用来存放队列中数据元素的一维数组,，,QueueDataType,为队列中元素的类型*,/,int,front;/*,队头指示器*,/,int,rear;/*,队尾指示器*,/,SeqQueue;,SeqQueue,*Q,/*,定义一个指向顺序队列的指针变量*,3.2,队列,第,3,章,栈和队列,顺序队列示意图,空队列示意图,3.2,队列,第,3,章,栈和队列,3.2,队列,第,3,章,栈和队列,2,循环队列的实现,（,1,）初始化操作,void,InitQueue,（,SeqQueue*Q,）,/*,将*,Q,初始化为一个空的循环队列*,/,Q-,front=Q-rear=0;,3.2,队列,第,3,章,栈和队列,（,2,）入队操作,int EnterQueue(SeqQueue*Q,QueueDataType x),/*,将元素,x,入队*,/,if,(Q-rear+1)%MaxSize=Q-front)/*,队列已满*,/,return(FALSE);,Q-,dataQ-rear=x;,Q-,rear=(Q-rear+1)%MaxSize;/*,重新设置队尾指针*,/,return(TRUE,);/*,操作成功*,/,3.2,队列,第,3,章,栈和队列,（,3,）出队操作,int DeleteQueue(SeqQueue*Q,QueueDataType*x),/*,删除队列的队头元素，用,x,返回其值*,/,if,（,Q-front=Q-rear,）,/*,队列为空*,/,return(FALSE,);,*,x=Q-dataQ-front;,Q-,front=(Q-front+1)%MaxSize;/*,重新设置队头指针*,/,return(TRUE,);,/*,操作成功*,/,3.2,队列,第,3,章,栈和队列,3.,链,队列,队列的链式存储结构简称为链队列，它是运算受限的单链表。为了操作方便，我们采用带头结点的链表结构，并设置一个队头指针和一个队尾指针，如图,3-10,所示。队头指针始终指向头结点，队尾指针指向当前最后一个元素。空的链队列的队头指针和队尾指针均指向头结点。,带头结点的链队列,3.2,队列,第,3,章,栈和队列,4.,链队列的基本,操作,（,1,）初始化操作,int InitQueue(LinkQueue*Q),/*,将,Q,初始化为一个空的链队列*,/,Q-front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode);/*,申请头结点*,/,if(Q-,front!=NULL),Q-,rear=Q-front;,Q-,front-link=NULL;,return(TRUE,);,/*,将,Q,初始化为带头结点的链队列*,/,else,return(FALSE);,3.2,队列,第,3,章,栈和队列,（,2,）入队,操作,3.2,队列,第,3,章,栈和队列,int EnterQueue(LinkQueue*Q,QueueDataType x),/*,将数据元素,x,插入到队列,Q,中*,/,LinkQueueNode *New;,New=(LinkQueueNode*)malloc(sizeof(LinkQueueNode);,if(New,!=NULL),New-,data=x;,New-,link=NULL;,Q-,rear-link=New;,Q-,rear=New;,return(TRUE,);,else,return(FALSE);,3.2,队列,第,3,章,栈和队列,（,3,）出队,操作,3.2,队列,第,3,章,栈和队列,int DeleteQueue(LinkQueue*Q,QueueDataType*x),/*,将队列,Q,的队头元素出队，并存放到,x,所指的存储空间中*,/LinkQueueNode,*p;,if(Q-,front=Q-rear),return(FALSE,);,p=Q-,front-link;,Q-,front-link=p-link;/*,队头元素,p,出队*,/,if(Q-,rear=p)/*,如果队列中只有一个元素,p,，则,p,出队后成为空队*,/,Q-,rear=Q-front;,*,x=p-data;,free(p,);/*,释放存储空间*,/,return(TRUE,);,3.2,队列,第,3,章,栈和队列,5,双端队列,还有一种限定性数据结构是双端队列,(Deque),。双端队列是限定插入和删除操作都可以在表的两端进行的线性表这两端分别称作端点,1,和端点,2,。在实际使用中，还可以有输出受限的双端队列，即一个端点允许插入和删除，另一个端点只允许插入的双端队列，以及输入受限的双端队列，即一个端点允许插入和删除，另一个端点只允许删除的双端队列。如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变成为两个栈底相邻接的栈了。尽管双端队列看起来似乎比栈和队列更灵活，但实际上在实际应用中远不及栈和队列常用。,3.2,队列,第,3,章,栈和队列,3.2.3,队列的应用实例,舞伴问题,队列也可以应用于很多场合，舞伴问题的实现是队列的一个典型应用实例。在本节中，讨论舞伴问题如何用队列来实现的算法。,假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头各出队一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题,。,问题分析：先入队的男士或女士亦先出队配成舞伴。因此该问题具有典型的先进先出特性，可用队列作为算法的数据结构。,小结,第,3,章,栈和队列,本章介绍了栈和队列这两种运算受限线性表。栈是一种限定其入栈、出栈操作只能在栈顶进行，所以栈中数据元素具有后进先出的特点，故又将它称为,LIFO,线性表，栈可以用顺序存储结构和链式存储结构表示；队列限定其入队在队尾进行，出队在队头进行，所以队列中的数据元素具有先进先出的特点，故又将它称为,FIFO,线性表，同栈一样，队列也可以利用顺序存储结构和链式存储结构表示。在顺序存储结构表示队列时，为了避免“假溢出”现象的发生，需要将队列构成循环状，这就形成了循环队列。,