crazylinux 发表于 2011-10-6 10:10:38

用两个堆栈实现一个队列

栈
的特点是后进先出，队列的特点是先进先出。所以，用两个栈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中。

下面两个方法的思路是一致的，只是一个是基于进栈与队列相同一个基于出栈与队列相同。
**** Hidden Message *****

haogl 发表于 2011-10-6 10:18:00

回复来看看，先谢过楼主！

吥咔咔 发表于 2011-10-6 13:31:37

这都要回复。。。。。{:5_90:}

crazylinux 发表于 2011-10-6 13:34:32

吥咔咔 发表于 2011-10-6 13:31 static/image/common/back.gif
这都要回复。。。。。

代码单独要回复是想让大家有个思考的时间，看完题目就看答案，那样永远学不会，只有思考了不懂的地方看看代码那样学到的才是自己的

zengsnail 发表于 2011-10-7 00:09:47

很不错~~~~~~~~~~

囧浻烱埛 发表于 2012-10-23 20:54:14

有意思。。。

麻神_181 发表于 2012-10-24 09:37:08

只要是设计到算法 我看都不敢看

晓北 发表于 2012-10-24 09:54:42

楼主，我觉得这个模拟队列的容量最多只能是一个栈的容量加一，当元素个数大于栈的容量加一的时候，入队的时候，可以先压入一个栈，再压入另一个栈，可出队的时候，便不能实现先进先出了，初学，不知道想的对不对，你的代码我还没看~~~~多指教~~

金色暢想犬舍 发表于 2012-10-24 10:01:32

我顶定定定定定定啊啊啊啊啊

麻神_181 发表于 2012-10-24 11:34:00

看不懂啊

gk-jsj 发表于 2016-4-24 20:56:33

{:5_90:}
页: [1]
查看完整版本: 用两个堆栈实现一个队列