数据结构(CC++语言版)第三章-队列、栈和串.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 特殊线性表,栈,队列,1,1,、编号为,1,，,2,，,3,，,4,的四辆列车，顺序开进一个栈式结构的站点，问开出车站的顺序有多少种可能？请具体写出所有可能的出栈序列。,2,、设有数组,A1.m,分配给两个栈,S1,和,S2,使用，如何分配数组空间，使得对任何一个栈，当且仅当数组空间全满时才不能插入。试说明你的分配方法。,3,、现有中缀表达式,E=(A-B)/C+D*(E-F)*G,（,1,）写出与,E,等价的后缀表达式。（,2,）用一个运算符栈来模拟表达式的转换过程，画出在将,E,转换成后缀表达式的过程中，栈内容的变化图。（,3,）用一个操作数栈来模拟后缀表达式的求值过程，画出对（,2,）中所得到的后缀表达式求值时，栈中内容的变化图。,2,4,、设计一个算法，它使用两个栈，一个栈存放操作数，另一个栈存放运算符。把已知算术表达式（中缀表示）的字符串作为输入，计算算术表达式的值。,5,、假设以一维数组,Q0.m-1,存储循环队列的元素。若要使这,m,个分量都得到利用，则需另设一个标志,tag,，以,tag,为,0,或,1,来区分尾指针和头指针值相同时队列的状态是“空”还是“满”。试编写与此结构相应的插入和删除算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当,m,较小而队列中每个元素占的空间较多时，哪一种方法较好）。,3,6,、假设以数组,Q0.m-1,存放循环队列的元素，同时设变量,rear,和,quelen,分别指示循环队列中队尾元素的位置和当前队列中元素的个数。试给出此循环队列满的条件，并写出插入和删除算法。,7,、如何用两个栈来实现队列？并写出队列基本操作的算法。,4,栈,和,队列,是计算机科学和程序设计中应用非常广范的两种数据结构，主要用于,临时性,地,缓存数据,元素（把一些数据保存起来供后面的计算中使用）。栈也常称为,堆栈,。,栈和队列可以方便地用线性表的基本结构实现，因此不少教科书把栈和队列看作是特殊的,操作受限,的线性表。,从,抽象数据类型,的角度看，栈和队列是与线性表完全不同的数据结构，因为它们具有不同的操作集合。,栈和队列都提供了元素,存入,、,访问,和,删除,操作，以及几个辅助操作，如创建、判断空等。,这两种结构的特点在于访问和删除操作：任何时刻能访问、删除的元素是,默认的,且,唯一确定,的。当时保存的其他元素都不能访问、删除。存入和删除操作将改变能访问的元素。,栈和队列给元素使用规定了,顺序,，两者的不同也就在这里。,6,栈及其基本运算,栈（,Stack,）是一种容器，可存入数据元素、访问元素、删除元素。在这里没有,位置,的概念。,栈保证任何时刻可访问、删除的元素都是前面最后存入栈里的那个元素。因此确定了一种,访问顺序,。,基本操作是封闭集合（与表不同），通常包括：,创建空栈,判断栈是否为空,向栈中插入（或称,推入,/,压入,，,push,）一个元素,从栈中删除（或称,弹出,，,pop,）一个元素,取当前（最新）元素的值（并不删除）,3.1 特殊线性表栈,7,3.1 特殊线性表栈,栈的逻辑结构,空栈：,不含任何数据元素的栈。,（,a,1,a,2,a,n,）,栈：,限定仅在,表尾,进行插入和删除操作的,线性表,。,栈顶,栈底,允许插入和删除的一端称为栈顶，另一端称为栈底。,8,栈的操作特性：,后进先出,a,1,a,2,a,3,入栈,出栈,栈底,栈顶,3.1 特殊线性表栈,插入：入栈、进栈、压栈,删除：出栈、弹栈,栈顶,栈的示意图,10,例：有三个元素按,a,、,b,、,c,的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,3.1特殊线性表栈,栈底,栈顶,a,b,栈顶,c,栈顶,情况,1,：,栈的逻辑结构,11,3.1 特殊线性表栈,栈底,栈顶,a,b,栈顶,出栈序列：,b,情况,2,：,例：有三个元素按,a,、,b,、,c,的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,栈的逻辑结构,13,例：,对于一个栈，给出输入项,A,、,B,、,C,，如果输入项序列由,ABC,组成，试给出所有可能的输出序列。,A,进,A,出,B,进,B,出,C,进,C,出,ABC,A,进,A,出,B,进,C,进,C,出,B,出,ACB,A,进,B,进,B,出,A,出,C,进,C,出,BAC,A,进,B,进,B,出,C,进,C,出,A,出,BCA,A,进,B,进,C,进,C,出,B,出,A,出,CBA,不可能产生输出序列,CAB,思考,:,假如,输入项为,A,、,B,、,C,、,D,，,则输出序列是哪些？,3.1 特殊线性表栈,栈的逻辑结构,15,16,DestroyStack,前置条件：栈已存在,输入：无,功能：销毁栈,输出：无,后置条件：释放栈所占用的存储空间,Push,前置条件：栈已存在,输入：元素值,x,功能：在栈顶插入一个元素,x,输出：如果插入不成功，抛出异常,后置条件：如果插入成功，栈顶增加了一个元素,栈的抽象数据类型定义,3.1 特殊线性表栈,18,Pop,前置条件：栈已存在,输入：无,功能：删除栈顶元素,输出：如果删除成功，返回被删元素值，否则，抛出异常,后置条件：如果删除成功，栈减少了一个元素,GetTop,前置条件：栈已存在,输入：无,功能：读取当前的栈顶元素,输出：若栈不空，返回当前的栈顶元素值,后置条件：栈不变,栈的抽象数据类型定义,3.1 特殊线性表栈,19,Empty,前置条件：栈已存在,输入：无,功能：判断栈是否为空,输出：如果栈为空，返回,1,，否则，返回,0,后置条件：栈不变,endADT,栈的抽象数据类型定义,3.1 特殊线性表栈,20,栈的顺序存储结构及实现,顺序栈,栈的顺序存储结构,如何改造数组实现栈的顺序存储？,0 1 2 3 4 5 6 7 8,a,1,确定用数组的哪一端表示栈底。,3.1 特殊线性表栈,附设指针,top,指示栈顶元素在数组中的位置。,top,21,出栈：,top,减1,进栈：,top,加1,栈空：,top=,-,1,0 1 2 3 4 5 6 7 8,3.1 特殊线性表栈,a,1,top,a,2,top,a,3,top,栈满：,top=,MAX_SIZE,栈的顺序存储结构及实现,22,顺序栈的实现,入栈,template,void seqStack:Push(T x),if(top=MAX_SIZE,-,1)throw “,溢出”;,top+;,datatop=x;,3.1 特殊线性表栈,操作接口：,void Push(T x);,时间复杂度？,24,顺序栈的实现,出栈,template ,T seqStack:Pop(),if(top=,-,1)throw “,溢出”;,x=datatop,-,;,return x;,3.1 特殊线性表栈,操作接口：,T Pop();,时间复杂度？,25,两栈共享空间,解决方案,1,：,直接解决：为每个栈开辟一个数组空间。,解决方案,2,：,顺序栈单向延伸,使用一个数组来存储两个栈,3.1 特殊线性表栈,在一个程序中需要,同时,使用具有,相同,数据类型的,两个栈,，,如何顺序存储这两个栈？,会出现什么问题？如何解决？,26,栈1的底固定在下标为0的一端；,栈2的底固定在下标为,StackSize-1,的一端。,top1,和,top2,分别为栈1和栈2的栈顶指针；,Stack_Size,为整个数组空间的大小（图中用,S,表示）；,a,1,a,2,a,i,top1,0 1 2,S,-1,两栈共享空间,两栈共享空间,top2,b,j,b,2,b,1,栈,1,底,栈,2,底,28,两栈共享空间,top1=-1,什么时候栈,1,为空？,a,1,a,2,a,i,top1,0 1 2,S,-1,两栈共享空间,top2,b,j,b,2,b,1,top1,29,两栈共享空间,top1=-1,什么时候栈,1,为空？,a,1,a,2,a,i,top1,0 1 2,S,-1,两栈共享空间,top2,b,j,b,2,b,1,什么时候栈,2,为空？,top2=Stack_Size,什么时候栈满？,top2=top1+1,31,1.如果栈满，则抛出上溢异常；,2.判断是插在栈1还是栈2；,2.1 若在栈1插入，则,2.1.1 top1,加1,;,2.1.2,在,top1,处填入,x；,2.2,若在栈2插入，则,2.2.1 top2,减1,;,2.2.2,在,top2,处填入,x；,两栈共享空间,两栈共享空间的实现,插入,操作接口：,void Push(int i,T x),;,32,1.,若是在栈1删除，则,1.1,若栈1为空栈，抛出下溢异常；,1.2,删除并返回栈1的栈顶元素；,2.,若是在栈2删除，则,2.1,若栈2为空栈，抛出下溢异常；,2.2,删除并返回栈2的栈顶元素；,两栈共享空间,两栈共享空间的实现,删除,操作接口：,T Pop(int i),;,33,栈的链接存储结构及实现,链栈：,栈的链接存储结构,特殊线性表栈,first,a,1,a,2,a,n,a,i,链栈需要加头结点吗？,如何改造链表实现栈的链接存储？,将哪一端作为栈顶？,将链头作为栈顶，方便操作。,链栈不需要附设头结点。,34,栈的链接存储结构及实现,栈顶,栈底,链栈：,栈的链接存储结构,特殊线性表栈,top,a,n,a,n,-1,a,1,first,a,1,a,2,a,n,a,i,两种示意图在内存中对应同一种状态,top,a,1,a,n,-1,a,n,栈顶,栈底,35,算法描述：,template,void LinkStack:Push,(,T x,),s=new Node;,s,-,data=x;,s,-,next=top;,top=s;,特殊线性表栈,top,a,n,a,n,-1,a,1,链栈的实现,插入,x,s,top,操作接口：,void Push(T x);,为,什,么,没,有,判,断,栈,满？,36,算法描述：,template,T LinkStack:,Pop,(),if,(,top=NULL,),throw,下溢;,x=top,-,data;,p=top;,top=top,-,next;,delete p;,return x;,特殊线性表栈,链栈的实现,插入,操作接口：,T Pop();,top,a,n,a,n,-1,a,1,top,p,top+,可以吗？,37,顺序栈和链栈的比较,时间性能：,相同，都是常数时间,O,(1),。,空间性能：,顺序栈：有元素个数的限制和空间浪费的问题。,链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。,特殊线性表栈,总之，当栈的使用过程中元素,个数变化,较大时，用链栈是适宜的，反之，应该采用顺序栈。,38,栈与递归,递归,递归函数到非递归函数的转换*,简化的背包问题*,迷宫问题,表达式计算,后缀表达式的求值,中缀表达式到后缀表达式的转换,栈的应用举例递归,39,栈的应用举例递归,1 递归的定义,子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种,描述问题,和,解决问题,的基本方法。,2,递归的基本思想,问题分解：,把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。,3,递归的要素,递归边界条件：,确定递归到何时终止,；,递归模式：大问题是如何分解为小问题的。,40,例,1,：括号匹配问题,：,假设一个算术表达式中允许包含两种括号：圆括号与方括号，其嵌套的次序随意。请设计一个算法判断一个算术表达式中的括号是否匹配。,栈的应用举例递归,41,void check(),SqStack s;,SElemType ch80,*p,e;,if(InitStack(s)/,初始化栈成功,printf(,请输入表达式,n);,gets(ch);,p=ch;,while(*p)/,没到串尾,switch(*p),case(:,case:,Push(s,*p+);,break;/,左括号入栈，且,p+,case):,case:if(!StackEmpty(s),Pop(s,e);/,弹出栈顶元素,if(*p=)&e!=(,|,*p=&e!=),printf(,左右括号不配对,n);,exit(ERROR);,else,p-;,break;/,跳出,switch,语句,else /,栈空,printf(,缺乏左括号,n);,exit(ERROR);,default:p+;/,其它字符不处理，指针向后移,if(StackEmpty(s)/,字符串结束时栈空,printf(,括号匹配,n);,else,printf(,缺乏右括号,n);,42,(a),迷宫的图形表示,(b),迷宫的二维数组表示,栈的应用举例,迷宫问题,43,44,45,46,47,48,49,50,51,52,例,3,：表达式求值问题：,53,54,55,56,57,问题的提出：,解决主机与外部设备之间速度不匹配的问题。主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。,（如何解决？）,解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入到这个缓冲区中；打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据。,“打印数据缓冲区”“队列”,58,3.2 队列,队列的定义,队列：,只允许在,一端,进行插入操作，而,另一端,进行删除操作的线性表。,队尾,队头,a,1,a,2,a,3,入队,出队,队列的操作特性：,先进先出,59,3.2 队列,60,队列的抽象数据类型定义,ADT Queue,Data,队列中元素具有相同类型及先进先出特性，,相邻元素具有前驱和后继关系,Operation,InitQueue,DestroyQueue,EnQueue,DeQueue,GetQueue,Empty,endADT,3.2 队列,61,0 1 2 3 4,入队,出队,队列的顺序存储结构及实现（,顺序队列）,如何改造数组实现队列的顺序存储？,例：,a,1,a,2,a,3,a,4,依次入队，仿照顺序表,n,个元素存放在前,n,个单元中。,a,1,a,2,a,3,a,4,入队操作时间性能为,O,(1),3.2 队列,62,队列的顺序存储结构及实现（,顺序队列）,如何改造数组实现队列的顺序存储？,3.2 队列,例：,a,1,a,2,依次出队,0 1 2 3 4,入队,出队,a,1,a,2,a,3,a,4,63,例：,a,1,a,2,依次出队,0 1 2 3 4,入队,出队,a,2,a,3,a,4,3.2 队列,如何改造数组实现队列的顺序存储？,队列的顺序存储结构及实现（,顺序队列）,64,例：,a,1,a,2,依次出队,0 1 2 3 4,入队,出队,a,3,a,4,出队操作时间性能为,O(,n,),3.2 队列,如何改造数组实现队列的顺序存储？,队列的顺序存储结构及实现（,顺序队列）,65,如何改进出队的时间性能？,放宽队列的所有元素必须存储在数组的前,n,个单元这一条件，只要求队列的元素存储在数组中连续的位置。,设置队头、队尾两个指示,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,66,0 1 2 3 4,入队,出队,例：,a,1,a,2,a,3,a,4,依次入队,a,1,rear,入队操作时间性能仍为,O,(1),front rear,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,67,0 1 2 3 4,入队,出队,例：,a,1,a,2,a,3,a,4,依次入队,a,1,a,2,rear,入队操作时间性能仍为,O,(1),front,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,68,0 1 2 3 4,入队,出队,例：,a,1,a,2,a,3,a,4,依次入队,a,1,a,2,a,3,rear,入队操作时间性能仍为,O,(1),front,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,69,0 1 2 3 4,入队,出队,例：,a,1,a,2,a,3,a,4,依次入队,a,1,a,2,a,3,a,4,rear,入队操作时间性能仍为,O,(1),front,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,70,例：,a,1,a,2,依次出队,0 1 2 3 4,入队,出队,a,1,a,2,a,3,a,4,rear,front,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,71,例：,a,1,a,2,依次出队,0 1 2 3 4,入队,出队,a,1,a,2,a,3,a,4,rear,front,出队操作时间性能提高为,O,(1),3.2 队列,队列的顺序存储结构及实现（,顺序队列）,72,例：,a,1,a,2,依次出队,0 1 2 3 4,入队,出队,a,1,a,2,a,3,a,4,rear,front,出队操作时间性能提高为,O,(1),3.2 队列,队列的顺序存储结构及实现（,顺序队列）,73,例：,a,1,a,2,依次出队,0 1 2 3 4,入队,出队,a,3,a,4,rear,front,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,74,rear,假溢出：,当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。,继续入队会出现什么情况？,0 1 2 3 4,入队,出队,a,3,a,4,front,a,5,rear,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,75,循环队列：,将存储队列的数组头尾相接。,如何解决假溢出？,0 1 2 3 4,入队,出队,a,3,a,4,front,a,5,rear,rear,a,6,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,76,不存在物理的循环结构，但可用软件方法实现。,求模,：（,4,1,）,mod 5,0,如何实现循环队列？,0 1 2 3 4,入队,出队,a,3,a,4,front,rear,a,6,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,77,如何判断循环队列队空？,队空的临界状态,0 1 2 3 4,入队,出队,a,3,rear,front,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,78,如何判断循环队列队空？,执行出队操作,0 1 2 3 4,入队,出队,a,3,rear,front,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,79,如何判断循环队列队空？,执行出队操作,队空：,front=rear,0 1 2 3 4,入队,出队,a,3,front,rear,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,80,如何判断循环队列队满？,队满的临界状态,0 1 2 3 4,入队,出队,a,3,a,4,front,a,5,rear,a,6,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,81,如何判断循环队列队满？,执行入队操作,0 1 2 3 4,入队,出队,a,3,a,4,front,a,5,rear,a,6,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,82,如何判断循环队列队满？,执行入队操作,队满：,front=rear,0 1 2 3 4,入队,出队,a,3,a,4,front,a,5,a,6,rear,a,7,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,83,队空、队满的判定条件出现二义性。,如何将队空和队满的判定条件分开？,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,方法一：,修改队满条件，浪费一个元素空间，队满时数组中还有一个空闲单元,；,0 1 2 3 4,入队,出队,a,3,a,4,front,a,5,rear,a,6,84,方法二：,附设一个存储队列中元素个数的变量,num，,当,num=0,时队空，当,num=QueueSize,时为队满；,队空、队满的判定条件出现二义性。,如何将队空和队满的判定条件分开？,3.2 队列,队列的顺序存储结构及实现（,顺序队列）,方法一：,修改队满条件，浪费一个元素空间，队满时数组中还有一个空闲单元,；,方法三：,设置标志,flag，,当,front=rear,且,flag=0,时为队空，当,front=rear,且,flag=1,时为队满。,85,队列的链接存储结构及实现,链队列：,队列的链接存储结构,队头指针即为链表的头指针,first,a,1,a,2,a,n,如何改造单链表实现队列的链接存储？,rear,front,3.2 队列,86,队列的链接存储结构及实现,非空链队列,front,a,1,a,2,a,n,rear,空链队列,front,rear,3.2 队列,87,操作接口：,LinkQueue();,算法描述：,template,LinkQueue:LinkQueue,(),front=new Node;,front-next=NULL;,rear=front;,链队列的实现,构造函数,front,rear,3.2 队列,88,x,s,链队列的实现,入队,操作接口：,void EnQueue(T x);,front,a,1,a,n,rear,rear,front,x,s,rear,rear,算法描述：,s-next=NULL;,rear-next=s;,rear=s;,有了头结点两种情况下的处理是一致的。,3.2 队列,89,链队列的实现,入队,template,void LinkQueue:EnQueue,(,T x,),s=new Node;,s-data=x;,s-next=NULL;,rear-next=s;,rear=s;,3.2 队列,90,链队列的实现,出队,front,a,1,a,2,a,n,rear,p,算法描述：,p=front-next;,front-next=p-next;,3.2 队列,91,链队列的实现,出队,front,a,1,a,2,a,n,rear,p,考虑边界情况：队列中只有一个元素？,front,a,1,p,rear,rear,仅1个元素的队列判断：,if(p-next=NULL),rear=front;,如何判断边界情况？,3.2 队列,92,template,T,LinkQueue:,DeQueue(),if(rear=front)throw,下溢;,p=front-next;,x=p-data;,front-next=p-next;,if(p-next=NULL),rear=front,;,/,修改队尾指针,delete p;,return x;,链队列的实现,出队,3.2 队列,93,时间性能:,循环队列和链队列的基本操作都需要常数时间,O(1)。,空间性能:,循环队列：必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。,链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个指针域，从而产生了结构性开销。,3.2 队列,循环队列和链队列的比较,94,例,1,:,农夫过河问题,3.4,队 列 应 用,95,96,97,98,99,100,101,例,2,:,求迷宫的最短路径,.,0,1,1,0,0,1,1,0,0,0,0,1,0,0,0,1,1,0,0,0,1,0,1,0,1,1,1,1,0,0,0,0,0,1,0,1,0,1,0,1,1,1,1,0,1,0,0,0,1 2 3 4 5 6 7 8,1,2,3,4,5,6,3.4,队 列 应 用,102,需要解决的问题,1,：如何从某一坐标点出发搜索其四周的邻点,?,(,x,y,),(x-1,y),(x-1,y+1),(x,y+1),(x+1,y+1),(x+1,y),(x+1,y-1),(x,y-1),(x-1,y-1),x,y,+1,-1,7,0,-1,6,-1,-1,5,-1,0,4,-1,+1,3,0,+1,2,+1,+1,1,+1,0,0,y,x,坐标增量数组,move,103,需要解决的问题,2,：如何存储搜索路径,?,需要解决的问题,3,：如何防止重复到达某坐标点,?,3,2,1,3,4,2,3,3,3,1,2,2,2,0,1,1,1,pre,y,x,步,3,1,3,5,6,front,rear,104,需要解决的问题,4,：如何输出搜索路径,?,1,12,13,14,15,16,17,18,19,20,x,1,5,2,5,6,5,6,6,5,6,y,1,6,6,3,1,7,5,4,8,8,pre,0,8,9,10,10,11,12,14,16,16,105,#define SIZE 64,#define M 10,#define N 10,int m=M-2,n=N-2;,typedef struct,int x,y;,int pre;,SqType;,SqType sqSIZE;,struct moved,int x,y;,move8;,int mazeMN;,106,int ShortPath(int maze2),int i,j,v,front,rear,x,y;,sq1.x=1;sq1.y=1;sq1.pre=0;,front=1;rear=1;,maze11=-1;,while(front=rear),x=sqfront.x;y=sqfront.y;,for(v=0;v8;v+),i=x+movev.x;,j=y+movev.y;,if(mazei,j=0),rear+;,sqrear.x=i;sqrear.y=j;,sqrear.pre=front;,mazeij=-1;,107,if(i=m)&(j=n),PrintPath(sq,rear);,Restore(maze);,return 1;,front+;,return 0;,108,void PrintPath(,SqType,sq,int rear),int i;,i=rear;,do,printf(“n(%d,%d)”,sqi.x,sqi.y);,i=sqi.pre;,while(i!=0);,109,110,特殊线性表,栈,队 列,栈的定义,操作特性,ADT,定义,队列定义,操作特性,ADT,定义,顺序栈,链,栈,循环队列,链队列,逻辑结构,存储结构,逻辑结构,存储结构,比 较,比较,比较,基本操作的实现,时间性能,基本操作的实现,时间性能,111,