栈的特点是后进先出,队列的特点是先进先出。所以,用两个栈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);
}
阅读(3268) | 评论(0) | 转发(0) |