用两个堆栈实现一个队列

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

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

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

游客，如果您要查看本帖隐藏内容请回复

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

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

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

这都要回复。。。。。

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

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

登录/注册后可看大图

这都要回复。。。。。

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

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

账号		自动登录	找回密码
密码			立即注册