{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. 设从键盘输入一整数的序列：a1, a2, a3，?，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。
【南京航空航天大学 1998 六 （10分）】 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. 设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。)
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++; //读入其它字符，不作处理。 }
}//算法结束。
[算法讨论]本题是用栈判断括号匹配的特例：只检查圆括号的配对。一般情况是检查花括号（‘{’，‘}’）、方括号（‘[’，‘]’）和圆括号（‘（’，‘）’）的配对问题。编写算法中如遇左括号（‘{’，‘[’，或‘（’）就压入栈中，如遇右括号（‘}’，‘]’，或‘）’），则与栈顶元素比较，如是与其配对的括号（左花括号，左方括号或左圆括号），则弹出栈顶元素；否则，就结论括号不配对。在读入表达式结束符‘#’时，栈中若应只剩‘#’，表示括号全部配对成功；否则表示括号不匹配。
另外，由于本题只是检查括号是否匹配，故对从表达式中读入的不是括号的那些字符，一律未作处理。再有，假设栈容量足够大，因此入栈时未判断溢出。
【北京科技大学 2001 九、1 （10分）】
4. 从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$
【山东师范大学 1999 七 （10分）】
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; scale=scale*10; scanf(“%c”,&x); } }//else
push(OPND,num); num=0.0;//数压入栈，下个数初始
化
case x=‘ ’:break; //遇空格，继续读下一个字符。 case x=‘+’:push(OPND,pop(OPND)+pop(OPND));break;
case x=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; case x=‘*’:push(OPND,pop(OPND)*pop(OPND));break;
case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; default: //其它符号不作处理。 }//结束switch
scanf(“%c”,&x);//读入表达式中下一个字符。 }//结束while（x！=‘$’）
printf(“后缀表达式的值为%f”,pop(OPND)); }//算法结束。
[算法讨论]假设输入的后缀表达式是正确的，未作错误检查。算法中拼数部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符，认为是数。这种字符的序号减去字符‘0’的序号得出数。对于整数，每读入一个数字字符，前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点，认为数的整数部分已完，要接着处理小数部分。小数部分的数要除以10（或10的幂数）变成十分位，百分位，千分位数等等，与前面部分数相加。在拼数过程中，若遇非数字字符，表示数已拼完，将数压入栈中，并且将变量num恢复为0，准备下一个数。这时对新读入的字符进入‘+’、‘-’、‘*’、‘/’及空格的判断，因此在结束处理数字字符的case后，不能加入break语句。
5. 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 （1）下面所示的序列中哪些是合法的？
A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO
（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。【武汉大学 2000 五、2】 5、（1）A和D是合法序列，B和C 是非法序列。 （2）设被判定的操作序列已存入一维数组A中。 int Judge(char A[])
//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返
回false。
{i=0; //i为下标。
j=k=0; //j和k分别为I和字母O的的个数。 while(A[i]!=‘\\0’) //当未到字符数组尾就作。 {switch(A[i])
{case‘I’: j++; break; //入栈次数增1。
case‘O’: k++; if(k>j){printf(“序列非法\\n”)；exit(0);} }
i++; //不论A[i]是‘I’或‘O’，指针i均后移。}
if(j!=k) {printf(“序列非法\\n”)；return(false);} else {printf(“序列合法\\n”)；return(true);}
}//算法结束。
[算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记‘\\0’），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。 6.设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。【南京邮电大学 2000五】
6、[题目分析]表达式中的括号有以下三对：‘（’、‘）’、‘[’、‘]’、‘{’、‘}’，使用栈，当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对，否则，结论表达式括号不配对。
int Match(LinkedList la)
//算术表达式存储在以la为头结点的单循环链表中，本算法判断括号是否正确配对 {char s[]; //s为字符栈，容量足够大
p=la->link; //p为工作指针，指向待处理结点 StackInit(s); //初始化栈s
while (p!=la) //循环到头结点为止
{switch (p->ch)
{case ‘(’:push(s,p->ch); break;
case ‘)’:if(StackEmpty(s)||StackGetTop(s)!=‘(’)
{printf(“括号不配对\\n”); return(0);} else pop(s);break;
case ‘[’:push(s,p->ch); break;
case ‘]’: if(StackEmpty(s)||StackGetTop(s)!=‘[’)
{printf(“括号不配对\\n”); return(0);} else pop(s);break;
case ‘{’:push(s,p->ch); break;
case ‘}’: if(StackEmpty(s)||StackGetTop(s)!=‘{’)
{printf(“括号不配对\\n”); return(0);} else pop(s);break;
} p=p->link; 后移指针 }//while
if (StackEmpty(s)) {printf(“括号配对\\n”); return(1);} else{printf(“括号不配对\\n”); return(0);}
}//算法match结束
[算法讨论]算法中对非括号的字符未加讨论。遇到右括号时，若栈空或栈顶元素不是其对应的左圆（方、花）括号，则结论括号不配对，退出运行。最后，若栈不空，仍结论括号不配对。
7. 请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释） 【西安电子科技大学2001软件五(10分)】【上海交通大学1999 二(12分)】【河海大学1998
三(12分)】
类似本题的另外叙述有：
（1）有两个长度相同的栈S1,S2，已知以下入栈、出栈、判栈满和判栈空操作： PROCEDURE push(Stack:Stacktype;x:Datatype); FUNCTION Pop(Stack:Stacktype ):Datatype; FUNCTION Full (Stack:Stacktype):Boolean; FUNCTION Empty(Stack:Stacktype)Boolean;
现用此二栈构成一个队列，试写出下面入队列、出队列操作算法： PROCEDURE EnQueue(x:Datatype);
FUNCTION DeQueue: Datatype;【北京邮电大学 2000 六（10分）】
7、[题目分析]栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且s1也为空，才算是队列空。 (1) int enqueue(stack s1,elemtp x)
//s1是容量为n的栈，栈中元素类型是elemtp。本算法将x入栈，若入栈成功返回1，否则返回0。
{if(top1==n && !Sempty(s2)) //top1是栈s1的栈顶指针，是全局变量。 {printf(“栈满”);return(0);} //s1满s2非空,这时s1不能再入栈。 if(top1==n && Sempty(s2)) //若s2为空，先将s1退栈,元素再压栈到s2。 {while(!Sempty(s1)) {POP(s1,x);PUSH(s2,x);}
PUSH(s1,x); return(1); //x入栈，实现了队列元素的入队。 }
(2) void dequeue(stack s2,s1)
//s2是输出栈，本算法将s2栈顶元素退栈，实现队列元素的出队。 {if(!Sempty(s2)) //栈s2不空，则直接出队。 {POP(s2,x); printf(“出队元素为”,x); } else //处理s2空栈。
if(Sempty(s1)) {printf(“队列空”);exit(0);}//若输入栈也为空，则判定队空。
else //先将栈s1倒入s2中，再作出队操作。 {while(!Sempty(s1)) {POP(s1,x);PUSH(s2,x);} POP(s2,x); //s2退栈相当队列出队。 printf(“出队元素”，x); }
}//结束算法dequue。 (3) int queue_empty()
//本算法判用栈s1和s2模拟的队列是否为空。
{if(Sempty(s1)&&Sempty(s2)) return(1);//队列空。 else return(0); //队列不空。 }
[算法讨论]算法中假定栈s1和栈s2容量相同。出队从栈s2出，当s2为空时，若s1不空，则将s1倒入s2再出栈。入队在s1，当s1满后，若s2空，则将s1倒入s2，之后再入队。因此队列的容量为两栈容量之和。元素从栈s1倒入s2，必须在s2空的情况下才能进行，即在要求出队操作时，若s2空，则不论s1元素多少（只要不空），就要全部倒入s2