Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,,‹#›,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,1,数据结构课程的内容,,,,,,,2,3.1,栈（,Stack,）,,第三章 栈和队列,3.2,队列,（,Queue,）,1.,定义,2.,逻辑结构,3.,存储结构,4.,运算规则,5.,实现方式,1.,定义,2.,逻辑结构,3.,存储结构,4.,运算规则,5.,实现方式,,3,1.,定义,3.1,栈,与同线性表相同，仍为一对一关系用顺序栈或链栈存储均可，但以顺序栈更常见,只能在栈顶运算，且访问结点时依照后进先出（,LIFO,）或先进后出（,FILO,）的原则关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同基本操作有入栈、出栈、读栈顶元素值、建栈、或判断栈满、栈空等3.,存储结构,4.,运算规则,5.,实现方式,,2.,逻辑结构,限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）,,4,问：堆栈是什么？它与一般线性表有什么不同？,3.1,栈,答：,堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。
与一般线性表的区别：仅在于运算规则不同一般线性表 堆栈,逻辑结构：一对一 逻辑结构：一对一,存储结构：顺序表、链表 存储结构：顺序栈、链栈,运算规则：随机存取 运算规则：后进先出,(LIFO),,“,进” ＝压入,=PUSH,（,x),“,出” ＝弹出,=POP ( y ),5,栈 是仅在,表尾,进行插入、删除操作的线性表表尾,(,即,a,n,端,),称为,栈顶,,top ;,表头,(,即,a,1,端,),称为,栈底,base,例如： 栈,s= (a,1,, a,2 ,,a,3 , ……….,,a,n-1 ,,a,n,),,a,1,称为 栈底元素,,a,n,,称为 栈顶元素,插入元素到,栈顶,（即表尾）的操作，称为,入栈,从,栈顶,（即表尾）删除最后一个元素的操作，称为,出栈教材,P44,对,栈,有更详细定义：,强调：,插入和删除都只能在表的一端（栈顶）进行！,,6,栈的表示和实现,顺序栈：栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针,top,指向栈顶元素在顺序栈中的下一个位置，,,base,为栈底指针，指向栈底的位置。
base,空栈,a,进栈,b,进栈,,,,a,a,b,top,base,top,base,top,顺序栈示意图,s,,,a,1,a,2,a,3,data,,,(,栈底,),(,栈顶,),99,.,.,.,3,2,1,0,top,,,,,8,顺序栈的类型表示,:,#define STACK_INIT_SIZE 100,；,#define STACKINCREMENT 10,；,,typedef char StackData;,,typedef struct {,//,顺序栈定义,,StackData *base;,//,栈底指针,,,StackData *top;,//,栈顶指针,,,int stacksize,；,//,当前已分配的存储空间,} SeqStack,；,9,判栈空,int StackEmpty (SeqStack *S) {,if( S->top == S->base ) return 1 //,空则返回,1,else return 0; //,否则返回,0,},判栈满,int StackFull (SeqStack *S) {,if( S->top- S->base >= S-> StackSize ) return 1,//,判栈满,,,满则返回,1,else return 0;,//,否则返回,0,},顺序栈的基本运算,:,,10,初始化,void InitStack ( SeqStack *S) {,//,置空栈,S,->base,=( StackData *)malloc(STACK_INIT_SIZE * sizeof(StackData)); if (!S->base) exit(OVERFLOW);,S,->,top = S,->base,;,S,->stacksize= S,TACK_INIT_SIZE ;,Return ok;,},11,a,1,a,2,……,a,n,顺序栈,S,a,i,……,,表和栈的操作区别,——,对线性表,,s= (a,1,, a,2 , …. ,,a,n-1 ,,a,n,),表头,表尾,栈底,base,栈顶,top,低地址,高地址,写入：,v[i]=,a,i,读出：,x= v[i],压入：,PUSH (an+1),弹出：,POP (x),前提：一定要预设栈顶指针,top,！,低地址,高地址,v[i],a,1,a,2,a,i,a,n,……,顺序表,V[n],……,,a,n+1,12,入栈操作,——,例如用堆栈存放（,A,，,B,，,C,，,D,）,,（注意要遵循,“,后进先出,”,原则）,A,,,,,,A,,,C,B,A,,,,B,A,top,核心语句：,top,=L;,,顺序栈中的,PUSH,函数,status Push(ElemType x),{ if(top>M){,上溢,},else v[,top++,]=x;,},Push (B);,Push (C);,Push (D);,,,top,top,top,top,低地址,L,Push (A);,高地址,M,B,C,D,13,入栈,int Push (SeqStack *S, StackData x) {,//,插入元素,x,为新的栈顶元素,,,if ( StackFull (S) ){,S->base =( StackData *)malloc(S->base ,,(S->stacksize+ STACKINCREMENT) * sizeof(StackData));,if(! S->base)exit(overflow);,S->top= S->base + S->stacksize;,S->stacksize+= STACKINCREMENT;,//,追加存储空间,},*(S->top)=x;,,（,S->top,）,++;,Return ok,},14,,出栈操作,——,例如从栈中取出,‘,B,’,,,（注意要遵循,“,后进先出,”,原则）,D,C,B,A,,top,top,,D,C,,A,B,,D,C,B,A,top,,,D,C,B,A,top,低地址,L,高地址,M,D,核心语句：,Pop ( );,Pop ( );,Printf(,Pop (),);,,顺序栈中的,POP,函数,status Pop( ),{ if(top=L) {,下溢,},else { y=v[,--top,]; return(y);},},,15,出栈,,int pop (SeqStack *S, StackData &x) {,//,若栈空返回0,,,否则栈顶元素退出到,x,并返回,1,,if ( StackEmpty(S) ) return 0;,--(S->top);,x = *(S->top);,return 1;,},16,例,1,：,一个栈的输入序列是,12345,，若在入栈的过程中允许出栈,，,则栈的输出序列,43512,可能实现吗？,12345,的输出呢？,43512,不可能实现，主要是其中的,12,顺序不能实现；,,12345,的输出可以实现，只需压入一个立即弹出一个即可。
435612,中到了,12,顺序不能实现；,,135426,可以实现例,2,：,如果一个栈的输入序列为,123456,，能否得到,435612,和,135426,的出栈序列？,,答：,答：,17,例,3,（严题集,3.1,）,一个栈的输入序列为,123,，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？,答：,可以通过穷举所有可能性来求解：,①,1,入,1,出，,2,入,2,出，,3,入,3,出， 即,123,；,②,1,入,1,出，,2,、,3,入,3,、,2,出， 即,132,；,③,1,、,2,入，,2,出，,3,入,3,出， 即,231,；,④,1,、,2,入，,2,、,1,出，,3,入,3,出， 即,213,；,⑤,1,、,2,、,3,入，,3,、,2,、,1,出， 即,321,；,合计有,5,种可能性18,例,4,：,计算机系,2001,年考研题（程序设计基础）,设依次进入一个栈的元素序列为,c,，,a,，,b,，,d,，,则可得到出栈的元素序列是：,,Ａ）,a,，,b,，,c,，,d,Ｂ）,c,，,d,，,a,，,b,Ｃ）,b,，,c,，,d,，,a,Ｄ）,a,，,c,，,d,，,b,A,、,D,可以,（,B,、,C,不行）。
讨论：有无通用的判别原则？,有在可能的输出序列中，不存在这样的输入序列,i,，,j,，,k,，能同时满足,idata=x; p->link=st; st=p;},},,S,tatus,pop( ),,{ if(st==NULL){,下溢,},else{y=st->data;p=st;st=st->link;,free(p); return(y);},},,链栈,入栈函数,链栈,出栈函数,插入表头,从表头删除,23,说 明,,链式栈无栈满问题，空间可扩充,插入与删除仅在栈顶处执行,链式栈的栈顶在链头,适合于多栈操作,24,,数制转换（十转,N,）,——P48,,设计思路：用栈暂存低位值,,例,2,：括号匹配的检验,————P49,,设计思路：用栈暂存左括号,,例,3,,：,表达式求值,—-————P52,,设计思路：用栈暂存运算符,,,例,1,：,栈的应用举例,25,1.,数制转换,,N = (N div d)×d + N mod d,,例如：（,1348),10,= (2504),8,,，其运算过程如下：,,,N N div 8 N mod 8,,1348 168 4 168 21 0 21 2 5 2 0 2,输出顺序,计算顺序,26,void conversion () {,InitStack(S);,scanf ("%d",N);,while (N) {,Push(S, N % 8);,N = N/8;,},while (!StackEmpty(S)) {,Pop(S,e);,printf ( "%d", e );,},} // conversion,27,2.,行编辑程序,在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。
设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区,;,并假设“,#”,为退格符，“,@”,为退行符假设从终端接受两行字符：,,whli##ilr#e,（,s#*s),outcha@putchar(*s=#++);,实际有效行为：,,while (*s),putchar(*s++);,28,Void LineEdit(){,InitStack(s);,ch=getchar();,while (ch != EOF) {,//EOF,为全文结束符,,while (ch != EOF && ch != '\n'),,{,switch (ch),{,case '#' : Pop(S, c); break;,case '@': ClearStack(S); break;,,//,重置,S,为空栈,,default : Push(S, ch); break;,},ch = getchar();,//,从终端接收下一个字符,,},29,将从栈底到栈顶的字符传送至调用过程的数据区,；,ClearStack(S);,//,重置,S,为空栈,if (ch != EOF) ch = getchar();,},DestroyStack(s);,},30,例,3,,表达式求值,(,这是栈应用的典型例子,),,这里，,表达式求值的算法是,“,算符优先法,”,。
例如：,3*,（,7 – 2,）,（,1,）要正确求值，首先了解算术四则运算的规则：,,a.,,从左算到右,,b.,,先乘除，后加减,,c.,,先括号内，后括号外,例：,4+2*3-10/5=4+6-10/5=10-10/5=10-2=8,,由此，此表达式的计算顺序为：,,3*,（,7 – 2,）,= 3 * 5 = 15,,31,（,2,）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符,,1,和,,2,,，都要比较优先权关系算符优先法所依据的算符间的优先关系,见教材,P53,表,3.1,,（是提供给计算机用的表！）,由表可看出，右括号,),,和井号,,#,,作为,,2,时,级别最低；,,由,c,规则,得出： * ，,/,，,+,，,-,为,,1,时的优先权低于‘（’，高于‘）’,由,a,规则,得出：‘,（,’,=‘,）,’ 表明括号内运算，已算完‘,#,’=‘,#,’,表明表达式求值完毕栈的应用（表达式求值）,,32,（,3,）算法思想：,设定两栈：,操作符栈,OPTR,，操作数栈,OPND,栈初始化,：设操作数栈,OPND,为空；操作符栈,OPTR,的栈底元素为表达式起始符 ‘,#’,；,依次读入字符,：是操作数则入,OPND,栈，是操作符则要判断：,,if,,操作符,<,栈顶元素,，则退栈、计算，结果压入,OPND,栈；,,操作符,=,栈顶元素且不为‘,#’,，脱括号（弹出左括号）；,,操作符,>,栈顶元素,，压入,OPTR,栈。
栈的应用（表达式求值）,,33,栈的应用（表达式求值）,OPTR,OPND,INPUT,OPERATE,3*(7-2)#,Push(opnd,’3’),,#,*(7-2)#,3,#,Push(optr,’*’),#,*,3,(7-2)#,Push(optr,’(’),#,*,(,3,7-2)#,Push(opnd,’7’),#,*,(,3,7,-2)#,Push(optr,’-’),#,*,(,,－,3,7,2)#,Push(opnd,’2’),#,*,(,,－,3,7,2,),#,Operate(7-2),#,*,(,3,5,)#,Pop(optr),#,*,3,5,#,Operate(3*5),#,15,#,GetTop(opnd),,34,Status EvaluateExpression( OperandType &result) {,InitStack(OPND); InitStack(OPTR);Push(OPTR ,’#’);c=getchar();,while((c!=‘#’)//(GetTop(OPTR)!=‘#’)),{ if (!In(c,OP) { Push(OPND,c); c=getchar();},else switch(,compare(c,GetTop(OPTR),)),{case ‘>’ : Push(OPTR , c); c=getchar();break;,case ‘=’: Pop(OPTR);c=getchar();break;,,case ‘<’ : temat=Pop(OPTR); b=Pop();a=Pop();,,result= Operate(a,temat,b);Push(OPND,result);,c=getchar();break;,} //switch }//while,result=GetTop(OPND);}//EvaluateExpression,,此函数在哪里？,35,,定 义,3.2,队列,与线性表相同，仍为一对一关系。
顺序队,或,链队,，以循环顺序队更常见只能在队首和队尾运算，且访问结点时依照,先进先出,（,FIFO,）,的原则关键是掌握,入队,和,出队,操作，具体实现依顺序队或链队的不同而不同基本操作有入队或出队，建空队列，判队空或队满等操作3.,存储结构,4.,运算规则,5.,实现方式,,2.,逻辑结构,只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表 （,头删尾插,）,,36,队列 （,Queue,）,是仅在,表尾,进行插入操作，在,表头,进行删除操作的线性表表尾即,a,n,端，称为,队尾,,； 表头即,a,1,端，称为,队头,它是一种先进先出（,ＦＩＦＯ,）的线性表例如：队列,Q= (a,1,, a,2 ,,a,3 , ……….,,a,n-1 ,,a,n,),插入元素称为,入队,；删除元素称为,出队,队头,队尾,教材,P59,对队列有更详细定义：,,队列的抽象数据类型定义见教材Ｐ,59,－,60,队列的存储结构为,链队,或,顺序队,,（常用循环顺序队）,37,链队列示意图,,讨论：,空队列的特征？,Q,,(,队尾,),(,队首,),front,,,,,a1,a2,,a3,^,rear,,,p,front,,,,^,rear,,,③,怎样实现入队和出队操作？,入队（尾部插入）：,rear->next=S; rear=S;,出队（头部删除）：,front->next=p->next;,,②,队列会满吗？,front=rear,一般不会，因为删除时有,free,动作。
除非内存不足！,38,,,front,rear,x,^,元素,x,入队,,front,,,rear,x,,y,^,元素,y,入队,,front,,,rear,x,^,^,y,元素,x,出队,,front,rear,^,空队列,^,39,链式队列的定义,,typedef int QueueData;,,typedef struct node {,QueueData data; //,队列结点数据,,struct node *link; //,结点链指针,} QueueNode;,,typedef struct {,QueueNode *rear, *front;,} LinkQueue;,40,基本操作,Status InitQueue(LinkQueue &Q),{,//,构造一个空队列,Q,if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)))),exit(OVERFLOW);,Q.front->next=NULL;,return OK;,},41,Status QueueEmpty(LinkQueue Q),{ //,若,Q,为空队列,,,则返回,TRUE,,否则返回,FALSE,if(Q.front==Q.rear),return TRUE;,else,return FALSE;,},42,int QueueLength(LinkQueue Q),{,//,求队列的长度,,int i=0;,QueuePtr p;,p=Q.front;,while(Q.rear!=p),{,i++;,p=p->next;,},return i;,},43,Status EnQueue(LinkQueue &Q,QElemType e),{,//,插入元素,e,为,Q,的新的队尾元素,,QueuePtr p;,if(!(p=(QueuePtr)malloc(sizeof(QNode)))),//,存储分配失败,,exit(OVERFLOW);,p->data=e;,p->next=NULL;,Q.rear->next=p;,Q.rear=p;,return OK;,},44,Status DeQueue(LinkQueue &Q,QElemType &e),{,//,若队列不空,,,删除,Q,的队头元素,,,用,e,返回其值,,,并返回,OK,,否则返回,ERROR,QueuePtr p;,if(Q.front==Q.rear),return ERROR;,p=Q.front->next;,e=p->data;,Q.front->next=p->next;,if(Q.rear==p),Q.rear=Q.front;,free(p);,return OK;,},45,顺序队示意图,Q,,,(,队尾,),(,队首,),,front,,,,a,1,a,2,a,3,data,a,4,,0,.,.,.,.,.,.,.,99,rear,,,②,队列会满吗？,很可能会，因为数组前端空间无法释放。
因此数组应当有长度限制①,空队列的特征？,约定：,front=rear,队尾后地址,入队,(,尾部插入,),：,v[rear]=e; rear++;,出队,(,头部删除,),：,x=v[front]; front++;,讨论：,假溢出,,有缺陷,③,怎样实现入队和出队操作？,3.2,队列,46,问：什么叫“假溢出” ？如何解决？,答：,在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫,“,假溢出,”,3.2,队列,,解决假溢出的途径,———,采用循环队列,47,,a3,a2,a1,,,0,1,2,3,N-1,rear,front,循环队列（臆造）,顺序队列,,,a3,a2,a1,,,front,rear,0,1,2,3,.,.,N-1,新问题：,在循环队列中，空队特征是,front=rear,；,队满时也会有,front=rear,；,判决条件将出现二义性！,解决方案有三：,① 加设标志位，让删除动作使其为,1,,插入动作使其为,0,,则可识别当前,front=rear,②,使用一个计数器记录队列中元素个数（即队列长度）；,③ 人为浪费一个单元，令,队满特征为,front=(rear+1)%N,；,,48,队空条件,:,front = rear,(,初始化时：,front = rear ),队满条件,：,front = (rear+1) % N,(N=maxsize),队列长度：,L=,（,N,＋,rear,－,front,）,% N,,J2 J3,J1 J4,,J5,front,rear,,选用,空闲单元法：,即,front,和,rear,之一指向实元素，另一指向空闲元素。
问,2,：,在具有,n,个单元的循环队列中，队满时共有多少个元素？,n-1,个,5,,,问,1,：左图中队列长度,L=,？,,49,J6 J5,J7,J8 J9,例,1,：,一循环队列如下图所示，若先删除,4,个元素，接着再插入,4,个元素，请问队头和队尾指针分别指向哪个位置,?,J2 J3,J1 J4,,J5,front,rear,解：,由图可知，队头和队尾指针的初态分别为,front=1,和,rear=6,front,rear,,删除,4,个元素后,front=5,；再插入,4,个元素后，,r=(6+4),%,6=4,front,front,front,front,front,50,例,2,：,数组Ｑ,[n],用来表示一个循环队列，,f,为当前队列头元素的,前一,位置，,r,为队尾元素的位置假定队列中元素的个数小于,n,，计算队列中元素的公式为,:,（Ａ）,r,－,f,（Ｂ）（,n,＋,f,－,r,）,% n,（Ｃ）,n,＋,r,－,f,（Ｄ） （,n,＋,r,－,f,）,% n,4,种公式哪种合理？,当,r ≥f,时（,A,）合理；,当,r < f,时（,C,）合理；,分析 ：,,,综合,2,种情况，以（,D,）的表达最为合理,例,3,：,在一个循环队列中，若约定队首指针指向队首元素的,前一个,位置。
那么，从循环队列中删除一个元素时，其操作是 先,,，后,,移动队首指针,取出元素,√,51,问：为什么要设计队列？它有什么独特用途？,离散事件的模拟（模拟事件发生的先后顺序）；,操作系统中多道作业的处理（一个,CPU,执行多个作业）；,3.,简化程序设计答：,循环队列的操作实现,见教材,P64,,52,循环队列的操作实现,1,）,初始化一空队列,算法要求：生成一空队列,算法操作：为队列分配基本容量空间,设置队列为,空队列,，,即,front=rear=0,（也可为任意单元，如,2,，或,4,）,;,,53,算法：,Status InitQueue ( SqQueue &q ),{//,初始化空循环队列,q,q . base=(QElemType *)malloc,(,sizeof(QElemType,）,* QUEUE_MAXSIZE,);,//,分配空间,if (,!q.base,) exit(OVERFLOW);//,失败，退出程序,q.front =q.rear=0;//,置空队列,return OK;,}//InitQueue;,,新开单元的地址为,0,则表示内存不足,54,算法说明：向循环队列的队尾插入一个元素,分 析,：,(1),插入前应当先判断队列是否满,,if (( q . rear + 1 ) %,,QUEUE_MAXSIZE,)==q.front),return ERROR;,(2,）插入动作,,q.base [q.rear] = e;,q.rear = ( q . rear + 1 ) %,QUEUE_MAXSIZE,;,,2,） 入队操作,,55,Status,EnQueue,(SqQueue &q, QElemType e),{,//,向循环队列,q,的队尾加入一个元素,e,if ( (q.rear+1) %,QUEUE_MAXSIZE,= = q.front ),return ERROR ;,q.base [ q.rear ] = e;,//,存储,,q.rear = ( q . rear + 1 ) %,QUEUE_MAXSIZE,;,//,指针后移,return OK;,},//,EnQueue,;,,2,） 入队操作（完整函数）,56,3,）出队操作,算法说明：删除队头元素，返回其值,e,分 析：,（,1,）,在删除前应当判断队列是否空；,,if (q.front = q.rear ) return ERROR;,,（,2,）,插入动作分析；,因为队头指针,front,指向队头元素的位置，所以：,,e = q.base [ q.front ] ;,q.front = ( q . front + 1 ) %,QUEUE_MAXSIZE,;,,,57,Status,DeQueue,,( SqQueue &q, QElemType &e),{,//,若队列不空，删除循环队列,q,的队头元素，,,//,由,e,返回其值，并返回,OK,if ( q.front = = q.rear ) return ERROR;,//,队列空,e = q.base [ q.front ] ;,q.front=(q.front+1) %,QUEUE_MAXSIZE,;,return OK;,},// DeQueue,算法：,,58,讨论（代本章小结）,线性表、栈与队的异同点,相同点：,逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即,受限的线性表,（只是对插入、删除运算加以限制）。
不同点：,① 运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表,LIFO,；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表,FIFO,② 用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等59,一 选择题,1.,对于栈操作数据的原则是（ ）先进先出,B.,后进先出,C.,后进后出,D.,不分顺序,2.,一个栈的输入序列为,123…n,，若输出序列的第一个元 素是,n,，输出第,i,（,1<=i<=n,）个元素是（ ）A.,不确定,B. n-i+1 C. i D. n-i,3.,若一个栈的输入序列为,1,2,3,…,n,，输出序列的第一个 元素是,i,，则第,j,个输出元素是（ ）A. i-j-1 B. i-j C. j-i+1 D.,不确定的,4.,栈在（ ）中应用中山大学,1998,二、,3,（,2,分）,】,递归调用,B.,子程序调用,C.,表达式求值,D. A,，Ｂ，Ｃ,5.,有六个元素,6,，,5,，,4,，,3,，,2,，,1,的顺序进栈，问下列哪,一个不是合法的出栈序列？（ ）,5 4 3 6 1 2 B. 4 5 3 1 2 6,C. 3 4 6 5 2 1 D. 2 3 4 1 5 6,60,6.,在作进栈运算时,,,应先判别栈是否,( ① ),,在作退栈运算时应先判别栈是否,( ② ),。
当栈中元素为,n,个,,,作进栈运算时发生上溢,,,则说明该栈的最大容量为,( ③ ),为了增加内存空间的利用率和减少溢出的可能性,,,由两个栈共享一片连续的内存空间时,,,应将两栈的,( ④ ),分别设在这片内存空间的两端,,,这样,,,当,( ⑤ ),时，才产生上溢①,, ②: A.,空,B.,满,C.,上溢,D.,下溢,③,: A. n-1 B. n C. n+1 D. n/2,④: A.,长度,B.,深度,C.,栈顶,D.,栈底,⑤,: A.,两个栈的栈顶同时到达栈空间的中心点,.,B.,其中一个栈的栈顶到达栈空间的中心点,.,C.,两个栈的栈顶在栈空间的某一位置相遇,.,D.,两个栈均不空,,,且一个栈的栈顶到达另一个栈的栈底,.,61,7.,输入序列为,ABC,，可以变为,CBA,时，经过的栈操作为（ ）,【,中山大学,1999,一、,8(1,分,)】,A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop,C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop,8.,若一个栈以向量,V[1..n],存储，初始栈顶指针,top,为,n+1,，则下面,x,进栈的正确操作是,( ),。
A,．,top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1,C. top:=top-1; V [top]:=x D. V [top]:=x; top:=top-1,9.,设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳A,．线性表的顺序存储结构,B.,队列,C.,线性表的链式存储结构,D.,栈,62,10.,用不带头结点的单链表存储队列时,,,其队头指针指向队头结点,,,其队尾指针指向队尾结点，则在进行删除操作时,( ),北京理工大学,2001,六、,3,（,2,分）,】,A,．仅修改队头指针,B.,仅修改队尾指针,C.,队头、队尾指针都要修改,D.,队头,,,队尾指针都可能要修改,11.,假设以数组,A[m],存放循环队列的元素,,,其头尾指针分别为,front,和,rear,，则当前队列中的元素个数为（ ）A,．,(rear-front+m)%m B,．,rear-front+1,C,．,(front-rear+m)%m D,．,(rear-front)%m,12,栈和队都是（ ）,A,．顺序存储的线性结构,B.,链式存储的非线性结构,C.,限制存取点的线性结构,D.,限制存取点的非线性结构,。