指针top[1]=m+1，当top[0]=0为左栈空，top[1]=m+1为右栈空；当top[0]=0并且top[1]=m+1时为全栈空。当top[1]-top[0]=1时为栈满。 27、（1）每个栈仅用一个顺序存储空间时，操作简便，但分配存储空间小了，容易产生溢出，分配空间大了，容易造成浪费，各栈不能共享空间。
（2）多个栈共享一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才能产生溢出，其缺点是当一个栈满时要向左、右栈查询有无空闲单元。如果有，则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时，查询空闲单元、移动元素和修改栈底栈顶指针的操作频繁，计算复杂并且耗费时间。
（3）多个链栈一般不考虑栈的溢出（仅受用户内存空间限制），缺点是栈中元素要以指针相链接，比顺序存储多占用了存储空间。
28、设top1和top2分别为栈1和2的栈顶指针 （1）入栈主要语句
if(top2-top1==1) {printf(“栈满\\n”); exit(0);} case1:top1++；SPACE[top1]=x; //设x为入栈元素。 case2:top2--；SPACE[top2]=x; 出栈主要语句
case1：if（top1==-1） {printf（“栈空\\n”）；exit（0）；} top1--；return（SPACE[top1+1]）； //返回出栈元素。 case2：if（top2==N）{printf（“栈空\\n”）；exit（0）；} top2++；return（SPACE[top2-1]）； //返回出栈元素。 （2）栈满条件：top2-top1=1
栈空条件：top1=-1并且top2=N //top1=-1为左栈空，top2=N为右栈空 29、设顺序存储队列用一维数组q[m]表示，其中m为
队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。 30、见上题29的解答。 31、参见上面29题。 32、typedef struct node
{elemtype elemcq[m]; //m为队列最大可能的容量。
int front ,rear; //front和rear分别为队头和队尾指针。 }cqnode; cqnode cq;
初始状态
cq.front=cq.rear=0;
队列空
cq.front==cq.rear;
队列满
(cq.rear+1)%m==cq.front;
33、栈的特点是后进先出，队列的特点是先进先出。初始时设栈s1和栈s2均为空。 （1）用栈s1和s2模拟一个队列的输入：设s1和s2容量相等。分以下三种情况讨论：若s1未满，则元素入s1栈；若s1满，s2空，则将s1全部元素退栈，再压栈入s2，之后元素入s1栈；若s1满，s2不空（已有出队列元素），则不能入队。 （2）用栈s1和s2模拟队列出队（删除）：若栈s2不空，退栈，即是队列的出队；若s2为空且s1不空，则将s1栈中全部元素退栈，并依次压入s2中，s2栈顶元素退栈，这就是相当于队列的出队。若栈s1为空并且s2也为空，队列空，不能出队。 （3）判队空 若栈s1为空并且s2也为空，才是队列空。 讨论：s1和s2容量之和是队列的最大容量。其操作是，s1栈满后，全部退栈并压栈入s2（设s1和s2容量相等）。再入栈s1直至s1满。这相当队列元素“入队”完毕。出队时，s2退栈完毕后，s1栈中元素依次退栈到s2，s2退栈完毕，相当于队列中全部元素出队。
在栈s2不空情况下，若要求入队操作，只要s1不满，就可压入s1中。若s1满和s2不空状态下要求队列的入队时，按出错处理。 34、（1）队空s.front=s.rear； //设s是sequeuetp类型变量 （2）队满：（s.rear+1）MOD MAXSIZE=s.front //数组下标为0.. MAXSIZE-1 具体参见本章应用题第29题 35、typedef struct {elemtp q[m];
int front,count; //front是队首指针，count是队列中元素个数。 }cqnode;
//定义类型标识符。
(1)判空：int Empty(cqnode cq) //cq是cqnode类型的变量 {if(cq.count==0) return(1)；else return(0); //空队列} 入队: int EnQueue(cqnode cq，elemtp x)
{if(count==m){printf(“队满\\n”)；exit(0); } cq.q[(cq.front+count)%m]=x; //x入队
count++; return(1); //队列中元素个数增加1,入队成功。 }
出队: int DelQueue(cqnode cq)
{if (count==0){printf(“队空\\n”)；return(0);} printf(“出队元素”，cq.q[cq.front]); x=cq.q[cq.front];
cq.front=(cq.front+1)%m; //计算新的队头指针。 return(x)
}
(2) 队列中能容纳的元素的个数为m。队头指针front指向队头元素。
36、循环队列中元素个数为（REAR-FRONT+N）%N。其中FRONT是队首指针，指向队首元素的前一位置；REAR是队尾指针，指向队尾元素；N是队列最大长度。
37、循环队列解决了用向量表示队列所出现的“假溢出”问题，但同时又出现了如何判断队列的满与空问题。例如：在队列长10的循环队列中，若假定队头指针front指向队头元素的前一位置，而队尾指针指向队尾元素，则front=3，rear=7的情况下，连续出队4个元素，则front==rear为队空；如果连续入队6个元素，则front==rear为队满。如何判断这种情况下的队满与队空，一般采取牺牲一个单元的做法或设标记法。即假设front==rear为队空，而（rear+1）%表长==front为队满，或通过设标记tag。若tag=0，front==rear则为队空；若tag=1，因入队而使得front==rear，则为队满。 本题中队列尾指针rear，指向队尾元素的下一位置,listarray[rear]表示下一个入队的元素。在这种情况下，我们可规定，队头指针front指向队首元素。当front==rear时为队空，当（rear+1）%n=front时为队满。出队操作（在队列不空情况下）队头指针是front=（front+1）%n， 38、既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是dbca。 39、（1）4132 （2）4213 （3）4231 40、（1）队空的初始条件：f=r=0；
（2）执行操作A3后，r=3；// A3表示三次入队操作 执行操作D1后，f=1；//D1表示一次出队操作 执行操作A5后，r=0； 执行操作D2后，f=3； 执行操作A1后，r=1； 执行操作D2后，f=5；
执行操作A4后，按溢出处理。因为执行A3后，r=4，这时队满，若再执行A操作，则出错。 41．一般说，高级语言的变量名是以字母开头的字母数字序列。故本题答案是: AP321,PA321,P3A21,P32A1,P321A。
五、算法设计题
1、[题目分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1栈顶指针为-1，s2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。
#define maxsize 两栈共享顺序存储空间所能达到的最多元素数 #define elemtp i
nt //假设元素类型为整型 typedef struct
{elemtp stack[maxsize]; //栈空间 int top[2]; //top为两个栈顶指针 }stk;
stk s; //s是如上定义的结构类型变量，为全局变量。 (1)入栈操作：
int push(int i,int x)
//入栈操作。i为栈号，i=0表示左边的栈s1，i=1表示右边的栈s2，x是入栈元素。入栈成功返回1，否则返回0。
{if(i<0||i>1){printf(“栈号输入不对”);exit(0);} if(s.top[1]-s.top[0]==1) {printf(“栈已满\\n”);return(0);} switch(i)
{case 0: s.stack[++s.top[0]]=x; return(1); break; case 1: s.stack[--s.top[1]]=x; return(1); }
}//push
（2） 退栈操作 elemtp pop(int i)
//退栈算法。i代表栈号，i=0时为s1栈，i=1时为s2栈。退栈成功返回退栈元素，否则返回-1。
{if(i<0 || i>1){printf(“栈号输入错误\\n”)；exit(0);} switch(i)
{case 0: if(s.top[0]==-1) {printf(“栈空\\n”)；return（-1）；} else return(s.stack[s.top[0]--]);
case 1: if(s.top[1]==maxsize {printf(“栈空\\n”); return(-1);} else return(s.stack[s.top[1]++]); }
}//算法结束
[算法讨论] 请注意算法中两栈入栈和退栈时的栈顶指针的计算。两栈共享空间示意图略，s1栈是通常意义下的栈，而s2栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。
2、#define maxsize 栈空间容量 void InOutS(int s[maxsize])
//s是元素为整数的栈，本算法进行入栈和退栈操作。 {int top=0; //top为栈顶指针，定义top=0时为栈空。 for(i=1; i<=n; i++) //n个整数序列作处理。 {scanf(“%d”,&x); //从键盘读入整数序列。 if(x!=-1) // 读入的整数不等于-1时入栈。
if(top==maxsize-1){printf(“栈满\\n”);exit(0);}else s[++top]=x; //x入栈。 else //读入的整数等于-1时退栈。 {if(top==0){printf(“栈空\\n”);exit(0);} else printf(“出栈元素是%d\\n”,s[top--])；}} }//算法结束。
3、[题目分析]判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。 int EXYX(char E[],int n)
//E[]是有n字符的字符数组，存放字符串表达式，以‘#’结束。本算法判断表达式中圆括号是否匹配。
{char s[30]; //s是一维数组，容量足够大，用作存放括号的栈。 int top=0; //top用作栈顶指针。
s[top]= ‘#’; //‘#’先入栈，用于和表达式结束符号‘#’匹配。 int i=0; //字符数组E的工作指针。
while(E[i]!= ‘#’) //逐字符处理字符表达式的数组。 switch(E[i])
{case‘(’: s[++top]=‘(’; i++ ; break ;
case‘)’: if(s[top]==‘(’{top--; i++; break;} else{printf(“括号不配对”);exit(0);}
case‘#’: if(s[top]==‘#’){printf(“括号配对\\n”);return
(1);}
else {printf(“ 括号不配对\\n”);return (0);} //括号不配对 default : i++; //读入其它字符，不作处理。 }
}//算法结束。
[算法讨论]本题是用栈判断括号匹配的特例：只检查圆括号的配对。一般情况是检查花括号（‘{’，‘}’）、方括号（‘[’，‘]’）和圆括号（‘（’，‘）’）的配对问题。编写算法中如遇左括号（‘{’，‘[’，或‘（’）就压入栈中，如遇右括号（‘}’，‘]’，或‘）’），则与栈顶元素比较，如是与其配对的括号（左花括号，左方括号或左圆括号），则弹出栈顶元素；否则，就结论括号不配对。在读入表达式结束符‘#’时，栈中若应只剩‘#’，表示括号全部配对成功；否则表示括号不匹配。
另外，由于本题只是检查括号是否匹配，故对从表达式中读入的不是括号的那些字符，一律未作处理。再有，假设栈容量足够大，因此入栈时未判断溢出。
4、[题目分析]逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND,对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。 float expr( )
//从键盘输入逆波兰表达式，以‘$’表示输入结束，本算法求逆波兰式表达式的值。 ｛float OPND[30]; // OPND是操作数栈。 init(OPND); //两栈初始化。 float num=0.0; //数字初始化。
scanf (“%c”,&x);//x是字符型变量。 while(x!=’$’) {switch
{case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’) //拼数
if(x!=’.’) //处理整数
{num=num*10+（ord(x)-ord(‘0’)）; scanf(“%c”,&x);} else //处理小数部分。
{scale=10.0; scanf(“%c”,&x); while(x>=’0’&&x<=’9’) {num=num+(ord(x)-ord(‘0’)/scale;
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库栈与队列习题与答案(6)在线全文阅读。
相关推荐：