上海交通大学1999年试题的两种解法 (转载)

请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释）【上海交通大学1999 二(12分)】
[题目分析]栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且s1也为空，才算是队列空。
[算法讨论]算法中假定栈s1和栈s2容量相同。出队从栈s2出，当s2为空时，若s1不空，则将s1倒入s2再出栈。入队在s1，当s1满后，若s2空，则将s1倒入s2，之后再入队。因此队列的容量为两栈容量之和。元素从栈s1倒入s2，必须在s2空的情况下才能进行，即在要求出队操作时，若s2空，则不论s1元素多少（只要不空），就要全部倒入s2中。
下面两个方法的思路是一致的，只是一个是基于进栈与队列相同一个基于出栈与队列相同。
法（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入栈，实现了队列元素的入队。
}
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。
int queue_empty()
//本算法判用栈s1和s2模拟的队列是否为空。
{if(Sempty(s1)&&Sempty(s2)) return(1);//队列空。
else return(0);                       //队列不空。
}
法（2）
ElementType DeQueue(S1)
{
if(Empty(S1)
{
printf("Error!");
exit(0);
}
else
return Pop(S1);
}
void EnQueue(S1,ElementType x)
{
ElementType t;
while(!Empty(S1))
{
t=Pop(S1);
Push(S2,t;
}
Push(S1,x);
while(!Empty(S2))
{
t=Pop(S2);
Push(S1,t);
}
]