计算机专业基础综合数据结构栈和队列历年真题试卷汇编5

计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编5(总分：80.00，做题时间：90分钟)一、单项选择题(总题数：28,分数：56.00)1.对于栈操作数据的原则是―。【青岛大学2001年】A.先进先出B.后进先出VC.后进后出D.不分顺序考查栈的概念。栈是一种后进先出的数据结构。.在初始为空的堆栈中依次插入元素f,e,d,c,b,a以后，连续进行了三次删除操作，此时栈项元素是―。【北京航空航天大学2002年】A.cB.dVC.bD.e考查栈的基本性质。数据入栈时，先入栈的元素后出栈，只需简单地画图即可看出栈顶元素应是d。.六个不同元素依次进栈，能得到一种不同的出栈序列。【北京邮电大学2007年】A.42B.82C.132VD.192考查栈的基本性质。设有n个不同元素时，有f(n)种出栈序列。若第一个元素是第i个出栈的，则在这个元素之前是编号为2〜i的元素出栈，之后是编号为i+1〜n的元素出栈。所以第一个元素是第i个出栈对应f(i-1)*f(n—i)种出栈顺序。f(1)=1f(2)=2f(3)=f(2)+f(1)*f(1)+f(2)=5f(4)=f(3)+f(1)+f⑵十f(2)+f(1)+f(3)=14f(5)=f(4)+(1)+f(3)+“2)+f(2)+f(3)*(1)+f(4)=42f(6)=f(5)+(1)+f(4)+f(2)+f(3)+f(3),f(2)+f(4)+f(1)+f(5)=42+14+10+10+14+42=132.入栈序列为1,2,3,4,5,则可能得到的出栈序列是―。【上海交通大学2005】A.12534B.31254C.32541VD.14235考查栈的性质。C的情况是由以下操作得到：1、2、3先入栈，接着3弹栈，2弹栈，然后4、5入栈，5弹栈，4弹栈，最后1弹栈。其他各种情况，都不可能由栈的操作得到。.一个栈的输入序列为1,2,3,4,5,则下列序列中不可能是栈的输出序列的是。【北京理工大学2000年】【北京交通大学2006年】【中南大学2003年】A.23415B.54132VC.23145D.15432考查栈的性质。考生可通过画图得出正确答案。A是可能的：先是1、2入栈，然后2弹栈，3入栈，3弹栈，4入栈，4弹栈，1弹栈，5入栈，5弹栈。C是可能的：1和2入栈，2弹栈，3入栈，3弹栈，1弹栈，4入栈，4弹栈，5入栈，5弹栈。D是可能的：1入栈，l弹栈，2345入栈，5432弹栈。.若已知一个栈的入栈序列为1,2,3,4,其出栈序列为pl,p2,p3,p4,则p2,p4不可能是—。【华中科技大学2007年】A.2、4B.2、1C.4、3VD.3、4考查栈的性质。对于A,可能的顺序：1入栈，1弹栈，2入栈，2弹栈，3入栈，3弹栈，4入栈，4弹栈。对于B,可能的顺序：1入栈，2入栈，3入栈，3弹栈，2弹栈，4入栈，4弹栈，1弹栈。对于D,可能的顺序：1入栈，1弹栈，2入栈，3入栈，3弹栈，2弹栈，4入栈，4弹栈。C则没有对应的序列。.某堆栈的输入序列为a,b,c,d,下面的四个序列中，不可能是它的输出序列的是―。【北京航空航天大学2005年】【北京邮电大学2005年】A.a，c，b，dB.b，c，d，aC.c,d,b,aD.d，c，a，bV考查栈的性质。A可能的序列：a入栈，a出栈，b入栈，c入栈，c出栈，b出栈，d入栈，d出栈。B可能的序列：a、b入栈，b出栈，c入栈，c出栈，d入栈，d出栈，a出栈。C可能的序列：a、b、c入栈，c出栈，d入栈，d出栈，b出栈，a出栈。.输入序列为ABC，可以变为CBA时，经过的栈操作为——。【中山大学1999年】A.push，pop，push，pOp，push，popB.push，push，push，pOp，pOp，popVC.push，push，pop，pOp，push，popD.push，pOp，push，push，pOp，pop考查栈的性质。本题属于比较简单的类型。正确的顺序：A入栈，B入栈，c入栈，c弹栈，B弹栈，A弹栈。.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(j=1，2)栈顶，栈1的底在V【1]，栈2的底在V[m]，则栈满的条件是―。【南京理工大学1999年】A.1top[2]top[1]1=0B.top[1]+1=top[2]VC.top[1]+top[2]=mD.top[1]=top[2]考查栈共享空间的问题。可以通过画图来寻找问题的解，当空间V装满后，必有栈1的栈项+1=栈2的栈顶，即top[1]+1=top[2]。.向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应该执行。【北京理工大学2005年】A.h.>next=s：B.s->next=h；C.s.>next=h：h->next=s；D.s->next=h一〉next.h->next=S；V考查链栈的插入操作。实际上考查的是在一个链表的头结点后插入一个新结点的操作，因此如果熟练掌握了链表的插入操作，本题是比较容易的。由于该链表是带头结点的，因此h指向的是头结点，所以插入新结点的操作是：s一>lqext=h—〉Fiext；h一〉rtext=s；11.执行完下列语句段后，i值为。【浙江大学2000年】intf(intx){return((x>0)?x*f(x—1)：2)；)inti；i=f(f(1));A.2B.4VC.8D.无限递归考查对递归的理解和应用。由题得f(0)=2；f(1)=1*f(0)=2；f(1))=f(2)=2*f(1)=4,即f(1))=4。.一个递归算法必须包括—。【武汉大学2000年】A.递归部分B.终止条件和递归部分VC.迭代部分D.终止条件和迭代部分

考查对于递归的理解。一个递归算法分为终止条件和递归部分两个部分。终止条件是递归算法的出口，也就是终止递归的条件。递归部分是一个递推的关系式。.将递归算法转变成对应非递归算法时，需要使用―保存中间结果。【华中科技大学2007年】A.栈VB.队列C.二叉树D.单链表考查递归算法转化为非递归算法的方法。栈的一个重要应用就是实现程序中的递归。.表达式a*(b+c)—d的后缀表达式是。【南京理工大学2001年】A.abed*+—B.abc+*d——VC.abe*+d——D.-+*abcd将此树按照后序遍历，即可考查后缀表达式的计算方法。后缀表达式中，每一个计算符号均位于它的两个操作数的直接后面，按这样的方式逐步根据计算的优先级将每个计算式进行变换即可得到后缀表达式。或者还可以采用下面的方法：将表达式构造为一棵树，然后以后序遍历法遍历这棵树即可得到后缀表达式。同理可得前缀表达式、中缀表达式。比如在此题中，表达式a*(b+c)—d构造的树如图2.1所示。得到abc+*d一。将此树按照后序遍历，即可15.中缀表达式(A+B)*(C——D)/(E——F*G)的后缀表达式是―。【北京邮电大学2005年】A.A+B*C——D/E〜F*GB.AB十CD一*EFG*—/ VC.AB+C*D——E/F——G+D.ABCDEFG+*一/一*考查由中缀表达式计算后缀表达式的方法。本题给出了中缀表达式，可以通过中缀表达式构建表达式的树结构，然后以后序遍历这棵树，即可得到后缀表达式。16.中缀表达式A一(B+C/D)}E的后缀形式是。【北京航空航天大学2007年】A.ABCD/+E*—VB.ABC+D/*E——C.AB——C+D/E*D.ABC-+D/E*考查由中缀表达式计算后缀表达式的方法。按照上题的方法，可以很快得出答案。17.设计一个判别表达式中左、右括号是否配对出现的算法，采用—数据结构最佳。【西安电子科技大学1996年】A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈V考查栈和队列的应用领域。栈通常在数制转换、括号匹配检验、表达式求值、行编辑程序设计以及迷宫求解等方面有应用。18.在链队列的出队操作中，修改尾指针的情况发生在―。【广东工业大学2002年】A.变成空队列的时候B.变成满队列的时候C.队列只剩一个元素的时候VD.任何时候考查链队列的出队操作。链队列是一种特殊的链表。链队列的入队操作是在链表尾部插入一个新的结点，出队操作是在队头删除一个结点。所以只有等到只剩一个元素时，出队操作才会修改尾指针。19.对于循环队列，正确的是——。【哈尔滨工业大学2007年】A.无法判断队列是否为空B.无法判断队列是否为满C.队列不可能满D.以上说法都不对V考查循环队列的基本概念。考生可以很容易判断A、B和C三项均不正确。.循环队列A[0—m—1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是―。【南京理工大学2001年】【华中科技大学2007年】A.(rear一front+m)%mVB.rear一front+lC.rear一front一1D.rear一front考查循环队列元素数的计算方法。对于循环队列，计算元素数目的公式就是(rear-front+m)%m。.循环队列存储在数组A[0—m]中，则入队时的操作为―。【中山大学1999年】A.rear=rear+1B.rear=(rear+1)mod(m一1)C.rear=(rear+1)modmD.rear=(rear+1)mod(re+1)V考查循环队列入队操作。循环队列新元素入队时操作算法为rear=(rear+1)modmaxsize,本题中maxsize=m+1。因此入队操作为rear=(rear+1)mod(m+1)。.最大容量为n的循环队列，队尾指针是rear,队头是front,则队空的条件是―。【南京理工大学1999年】A.(rear+1)MODn=frontB.rear=frontVC.rear+1=frontD.(rear-11MODn=front考查循环队列队空的条件。循环队列当队空的时候，rear=front。.判定一个长度为M的循环队列Q队满的条件是一一。【北京交通大学2007年】A.Q.front+1==Q.rearB.Q.front==Q.rear+1C.Q.front=Q.rearD.Q.front=(Q.rear+1)%MV考查循环队列队满的条件。原本队列满和空的时候都是Q.front=Q.rear,但是为了区分两种情况，通常牺牲一个存储空间，即每次入队前先判断(Q.rear+1)%M是否等于Q.front,是的话就认为队列已满。所以，Q.front=(Q.rear+1)%M便是队满的条件。24.栈和队列的共同点是一一。【燕山大学2001年】A.都是先进先出B.部是先进后出C.只允许在端点处插入和删除元素VD.没有共同点考查栈和队列的特性。.栈s和队列Q的初始状态皆为空，元素a1,a2,a3,a4,a5和a6依次通过s栈，一个元素出栈后即进入队列Q,若6个元素出队列的顺序是a3,a4,a2,a1,a5,a6,则栈s至少应该容纳个元素。【哈尔滨工业大学2004年】A.6B.4C.3VD.2考查队列和栈的性质。由于队列“先进先出”，所以出队列的序列与进队列的序列是相同的，从而可以得到出栈的次序为a3,a4,a2,a1,a5,a6：再由栈“先进后出”的特性，进栈的次序为al,a2,a3,a4,a5和a6,可见，排在某个元素之后出栈却排在它之前进栈的元素个数，表示之前栈内的元素个数，因此a3进栈后，al和a2在栈中，因此栈的最小容量为3。.和顺序栈相比，链栈有一个比较明显的优势是―。【北京理工大学2006年】A.通常不会出现栈满的情况VB.通常不会出现栈空的情况C.插入操作更容易实现D.删除操作更容易实现考查链栈的特点。顺序栈是用一维数组实现的，链栈是用单链表实现的。当需要存储在顺序栈中的元素超过一维数组所能容纳的大小时，顺序栈是没有办法进行动态分配的。但是链栈就不存在这个问题。另外，当使用顺序栈时，由于栈的插入和删除结点都在栈顶，因此插入和删除只需要改变数组下标即可实现栈顶指针的修改。因此，和顺序栈相比，链栈的最大优势在于它可以动态的分配存储空间。27.执行―操作时，需要使用队列作辅助存储空间。【华中科技大学2006年】A.查找散列表B.广度优先搜索网VC.前序（根）遍历二叉树D.深度优先搜索网考查队列的应用领域。由于队列具有先进先出的特点，使得队列在树的层次遍历、图的广度优先遍历、离散时间模拟等方面均有应用。28.对n阶对称矩阵作压缩存储时，需要表长为的顺序表【华中科技大学2006年】A.n/2B.n,n/2C.n（n+1）/2VD.n（n一1）/2考查矩阵的压缩存储。对称矩阵只需要存储上（下）三角形（含对角线）元素，由题易得答案为n（n+1）/2。二、综合题（总题数：12,分数：24.00）.设从键盘输入一整数的序列：al,a2,a3,…，an,试编写算法实现：用栈结构存储输入的整数，当aiW—1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。【南京航空航天大学1998年】正确答案：（正确答案：算法的基本设计思想：依次输入每个整数，然后判断是否是一1,如果是，则弹栈；不是，则入栈。算法的代码：voidInOutS（ints[maxsize]）{//s是元素为整数的栈，本算法进行入栈和退栈操作inttop=0;//top为栈顶指针，定义top=0时为栈空for（inti=l；i<=n；i++）//n个整数序列作处理{scanf（"％d"，&x）； //从键盘读入整数序列if（xf=-1）//读入的整数不等于一l时入栈{if（top==maxsize-1）{printf（"栈满\n"）；exit（1）；}elses[++top]=x； //x入栈}else//读入的整数等于一1时退栈{if（top==0）{printf（"栈空\n"）；exit（1）,}elseprintf（“出栈元素是％d\n”,s[top一一]）；}}}//InOutS）.设有两个栈s1、s2都采用顺序栈方式，并且共享一个存储区[0.maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计s1、s2有关入栈和出栈的操作算法。【哈尔滨工业大学2001年】正确答案：（正确答案：两栈共享向量空间，将两栈栈底设在向量两端，初始时，sl栈项指针为一1,s2栈顶指针为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。数据结构的设计：typedefstruct{elemtpstack[maxsize]； //栈空间inttop[2]； //top为两个栈顶指针}stk；stks； //s是如上定义的结构类型变量，为全局变量1）入栈操作。算法的基本设计思想：设置一个变量来标识入哪个栈，若要将元素加入到s1栈中，s1栈顶指针加1；若要将元素加入到s2栈中，s2栈顶指针减1即可。算法的代码：intpush（inti,intX）{//入栈操作。i为栈号，i=0表示栈S1,i=1表示栈s2,x是入栈元素//入栈成功返回1,否则返回0if（i1）{printf（"栈号输入不对\n"）；return0；}if（S.top[1]—S.top[0]==1）{printf（"栈已满\n'）；return0；}SWitch（i）{case0：s.stack[++s.top[0\]\]=x；return1；case1：s.stack—s.top[1\]\]=x；return1；}}//push2)出栈操作。算法的基本设计思想：同理设置一个变量来标识入哪个栈，若是sl栈出栈，si栈顶指针减_1.若是s2栈出栈，s2栈顶指针加1即可。算法的代码：elemtppop(inti){//出栈算法。i代表栈号，i=0时为si栈，i=l时为s2栈//出栈成功返回出栈元素，否则返回一1if(ii){printf("栈号输入错误\n")；return0；}switch(i){case0：if(S.top[0]=1){printf(”栈空\n")；return-1；}elsereturn(s.stack[s.top[0]—―]),case1：if(S.top[1]==maxsize{printf(、、栈空\n")；return―1；}e1Sereturns.stack[s.top[1]++]；}}//pop请注意算法中两栈入栈和出栈时的栈顶指针的计算。sl栈是通常意义下的栈，而s2栈入栈操作时，其栈顶指针减1,出栈时，栈顶指针加1。).从键盘上输入一个逆波兰表达式，写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、一、*、/四种运算。例如：23434+2*$。【山东师范大学1999年】正确答案：(正确答案：算法的基本设计思想：逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND,对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈；当扫描到运算符时，从OPND栈退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。算法的代码：floatexprO{//从键盘输入逆波兰表达式，以'$'表示输入结束，本算法求逆波兰式表达式的值floatOPND[30]； //OPND是操作数栈init(OPND);//N栈初始化floatnum=0.0;//数字初始化scanf("%c”,&x),//x是字符型变量while(x!="$"){Switch(X);case0：case1：case2：case3：case4：case5：caseb：case?：case8：case9：case"."：while((x>="0"&&x<="9")||x="."){if(x!=".")//处理整数{//拼数，ord()是取ASCII码值的函数num=num*10+(Ord(X)—Ord("0"))；Scanf("%C",&X);}else//处理小数部分{f10atscale=10.0；Scanf("%c”,&x)；while(x>="0"&&x<="9"){rlLlm=FtLtm+(0rd(x)一0rd("0")/scale;Scale=scale±10；scanf(、、%c,,,&x)；}}//if一else}//whilepush(OPND,hum)；//数压入栈，并将用于拼数的临时变量初始化num=0.0;//注意此处没有breakCaSe""：break；//遇空格，继续读下一个字符CaSe"+"：push(OPND,pop(OPND)+pop(OPND))；break;CaSe"一"：floatx1=pop(OPND)；floatx2=pop(OPND);push(0PND,x2一x1);break；CaSe"*"：push(OPND,pop(OPND)*pop《OPND))；break;case"/"：floatx1=pop(OPND);float；x2=pop(OPND)；push(OPND,x2/x1),bEeak；}//结束switchscanf("%c",&x)； //读入表达式中下一个字符}//结束while(x!"$")printf("后缀表达式的值为％f”,pop(OPND))；}//expr算法中拼数部分是核心。若遇到大于等于’0’且小于等于‘9’的字符，认为是数。这种字符的序号减去字符‘0’的序号得出数。对于整数，每读入一个数字字符，前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点时，认为数的整数部分已完，要接着处理小数部分。小数部分的数要除以10(或10的幕数)变成十分位、百分位、千分位数等，与前面部分数相加。在拼数过程中，若遇到非数字字符，表示数已拼完，将数压入栈中，并且将变量llum恢复为0,准备下一个数。这时对新读入的字符进行'+‘、'一、'+'、'/'及空格的判断，因此在结束处理数字字符的case后，不能加入break语句。).设整数序列a1,a2,…，an,给出求解最大值的递归程序。【南京航空航天大学2000年】正确答案：(正确答案：算法的基本设计思想：比较an与an之前的n—1个元素的最大值，如果an大，则最大值为an；否则，继续递归求解之前n一1个元素的最大值。当比较到第一个元素的时候，最大值为第一个元素，递归终止。算法的代码：intMaxValue(inta[],intn)f//设整数序列存于数组a中，共有n个元素，本算法求解其最大值intmax；if(n==1)//只剩下一个元素时max=a[1]；e1Seif(a[n]>MaxValue(a,n-1))max=a[n]；e1Semax=MaxValue(a,n-1)；retUrnmaX；}//MaxValue)33.给定一个由英文字母组成的字符串s(假设S用数组实现)，编制一个递归函数，测试s是否为回文串，“回文串”是指从左向右读该字符串和从右向左读该字符串完全相同，例如：“noon”、“radar”等。【南京大学2005年】正确答案：(正确答案：算法的基本设计思想：利用递归算法，依次比较字符串中前后位置相对的元素是否相等。当字符串只剩一个元素或者两个元素(判断是否相等)时，递归过程终止。算法的代码：int

teSt(char*S,intf,inte){//f是字符数组S的首元素下标，e是末元素下标if((e—1==f&&S[f]==S[e])||f==e)return1;if(S[f]!=S[e])return0,returnteSt(S,f+1,e-1);}//teSt)34.设一个由字母组成的字符串，编写算法对它们的字母顺序进行调整，使输出时所有大写字母都在小写字母之前，并且同类字母之间的相对位置颠倒。华南理工大学2005年】例如:原有字符串为AbcDEfiglfiJKlmn,输出序列为KJEDAnmlihgfcbo正确答案：(正确答案：算法的基本设计思想：利用栈的先进后出的性质，依次读入字符串中的字母，判断是大写还是小写，大写则压入栈1中，小写则压入栈2中，字符串读完之后分别输出栈1和栈2内的字母。算法的代码：VOidchange(char*s){StackS1,S2；//假设栈是顺序栈，topl是s1的栈顶指针，top2是s2的栈顶指针inti=0;while(("a”<S[i]<"z")||"A"<s[i]<"Z"){if("A”<s[i]<"Z")PUSH(S1,S[i])；e1SePUSH(s2,s[i])；i++；1while(topl!=-1)printf("%c”,pop(S1)),while(top21=—1)printf("%c”,pop(s2));}//change).已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n等于零，则返回m。第二步：若m小于n,则m与n相互交换：否则，保存m,然后将n送m,将保存的m除以n的余数送no1)将上述过程用递归函数表达出来(设求x除以y的余数可以用xMODy形式表示)。2)写出求解该递归函数的非递归算法。【北京航空航天大学2001年】为欧几里德定理。正确答案：(正确答案：1)求两个正整数m和n的最大公因子，本题叙述的运算方法称为辗转相除法，也称)算法的基本设计思想题目已经讲得很清楚。算法的代码：递归方式的代码如下:intgcd(intm,intn){//求正整数m和n的最大公因子的递归算法if(m)为欧几里德定理。.试将下列递归过程改写为非递归过程。【北京轻工业学院2000年】voidtest(int&sum){intx；scanf(”%d,x)；1t(x=0)sum=0；else{test(sum)；Sum+=X；}printf("%d”,sum)；}正确答案：(正确答案：算法的基本设计思想：读入X值，判断是否为0,不为0则压入栈中并继续读入X值，为0则停止读入x值并打印输出sum。然后将栈中的元素依次累加，每累加一个元素，输出一个sum值。算法的代码：VOidteSt(){intX,sum=0,top=0,S[];SCanf(”%d”,&X);while(X!=0){S[++top]=x;scanf("%d”,&x)；}printf(”%d”,sum);while(top){sum+=S[top一一];printf(”%d”,sum)；}}//teSt).假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。【华东师范大学2000年】【苏州大学2002年】正确答案：(正确答案：算法的基本设计思想：入队操作即在循环链表的尾部插入一个结点，出队操作即在循环链表的头结点后删除一个结点。算法的代码：1)voidEnQueue(LinkedLiSt&rear,ElemTypeX){//rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾S=(LinkedLiSt)malloc(Sizeof(LNode))；//申请结点空间S一>data=x;s一>next=rear—〉next；//将S结点链入队尾rear一〉next=S：rear=s； //rear指向新队尾}2)VOidDeQueue(LinkedLiSt&rear){//rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则//给出出错信息if(rear一〉neXt=：rear){printf(“队空\/，)；exit(1),}s=rear一〉next—〉next； //S指向队头元素rear一〉next—>next=S—>next； //队头元素出队printf(“出队元素是%d”,S->data)；if(S==rear)rear=rear->nextj//空队列free(s)；}).一个双端队列deque是限定在两端endl、end2都可进行插入和删除的线性表，队空条件是endl+l=end2。若用顺序方式来组织双端队列，试根据下列要求，定义双端队列的结构，并给出在指定端i(i=1,2)的插入enq和删除deq操作的实现。1)当队满时，最多只能有一个元素空间可以是空的。2)在做两端的插入和删除时，队列中其他元素一律不动。【中南大学2003年】正确答案：(正确答案：双端队列示意图如下(设maxsize=12)：法的基本设计思想：用一维数组作正确答案：(正确答案：双端队列示意图如下(设maxsize=12)：法的基本设计思想：用一维数组作存储结构，把它看作首尾相接的循环队列，可以在任一端(end1或end2)进行插入或删除操作。初始状态end1+1=end2被认为是队空状态，endl=end2被认为是队满状态。endl指向(左端队列)队尾元素的前一位置，end2指向(右端队列)队尾元素的后一位置。入队时判队满，出队(删除)时判队空。删除一个元素时需要返回所删除元素的值。算法的代码：typedefStruct{datatypeelem[maxsize]intendl，end2;//endl和end2取值范围是[0..maxsize一1]}deque;intadd(dequeQudatatypeX,inttag){//在双端队列Qu中插入元素X,若插入成功，返回1：若插入失败，返回一1//tag=0表示在end1端插入，tag=1表示在end2端插入if(Qu.endl==Qu.end2){printf("队满")；retL1rn—1；}switch(tag){Case0：Qu.end1=x；//插入xQu.encll=《Qu.endl-1+maxsize)〜maxsize;//修改endlreturn1：case1：Qu.end2=x：Qu.end2=(Qu.end2+1)%maxsize；retuEn1；}}//adddatatypedelete(dequeQu,datatypex,inttag){//在双端队列Qu中删除元素x,tag=0时从endl端删除，tag=1时从encl2端删除//删除成功返回被删元素的值，否则返回NULLif((Qu.endl+1)%maxsize=Qu.end2){printf("队空“)；returnNULL：}switch(tag){case0：Qu.endl=(Qu.end1+1)%maxsiZe；returnQu.elem[Qu.end1];caSe1：Qu.end2=(Qu.end2-1+maxsize)%maxsize;returnQu.elem[Qu.enct2]；}}//delete请注意下标运算。(i十1)modmaxsize容易理解。考虑到i-1可能为负的情况，所以求下个i时用T(i-1+maxsize)modmaxsizeo).已知Q是一个非空队列，s是一个空栈。仅用队列和栈的ADT函数和少量工作变量，使用C语言编写一个算法，将队列Q中的所有元素逆置。栈的ADT函数有：【清华大学2000年】makeEmpty(s：stack)；//置空栈push(s：stack；value：datatype)； //新元素value进栈pop(