数据结构考研分类复习真题 第三章 答案[21]

[题目分析]栈的特点是后进先出队列的特点是先进先出所以用两个栈s和s模拟一个队列时s作输入栈逐个元素压栈以此模拟队列元素的入队当需要出队时将栈s退栈并逐个压入栈s中s中最先入栈的元素在s中处于栈顶s退栈相当于队列的出队实现了先进先出显然只有栈s为空且s也为空才算是队列空

() int enqueue(stack selemtp x)

//s是容量为n的栈栈中元素类型是elemtp本算法将x入栈若入栈成功返回否则返回

{if(top==n && !Sempty(s)) //top是栈s的栈顶指针是全局变量

{printf(栈满);return();} //s满s非空这时s不能再入栈

if(top==n && Sempty(s)) //若s为空先将s退栈元素再压栈到s

{while(!Sempty(s)) {POP(sx);PUSH(sx);}

PUSH(sx); return(); //x入栈实现了队列元素的入队

}

() void dequeue(stack ss)

//s是输出栈本算法将s栈顶元素退栈实现队列元素的出队

{if(!Sempty(s)) //栈s不空则直接出队

{POP(sx); printf(出队元素为x); }

else //处理s空栈

if(Sempty(s)) {printf(队列空);exit();}//若输入栈也为空则判定队空

else //先将栈s倒入s中再作出队操作

{while(!Sempty(s)) {POP(sx);PUSH(sx);}

POP(sx); //s退栈相当队列出队

printf(出队元素x);

}

}//结束算法dequue

() int queue_empty()

//本算法判用栈s和s模拟的队列是否为空

{if(Sempty(s)&&Sempty(s)) return();//队列空

else return(); //队列不空

}

[算法讨论]算法中假定栈s和栈s容量相同出队从栈s出当s为空时若s不空则将s倒入s再出栈入队在s当s满后若s空则将s倒入s之后再入队因此队列的容量为两栈容量之和元素从栈s倒入s必须在s空的情况下才能进行即在要求出队操作时若s空则不论s元素多少（只要不空）就要全部倒入s中

类似本题叙述的其它题的解答

该题同上面题本质相同只有叙述不同请参考上题答案

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []