注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

天地不仁,以万物为Googol!

天行有常,不以物喜,不以己悲……

 
 
 

日志

 
 

栈和队的统一  

2009-05-28 10:48:00|  分类: 积累 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这是上周软设考试时遇到的一道题,判断对错:可以用两个栈模拟一个队列,也可以用一个队列模拟两个栈。

这个题以前从来没有想过,一直当栈和队都是基本的数据结构,都是从线性表直接衍生出来的,从来没想过相互间的转化。当时蒙了一下。不过既然连需要的数量都给出来了,那说明至少某个单方向是可行的(不然这数还真是有零有整的……)。

很快,两个栈模拟一个队列的情况就想出来了。这里用到一个栈的特性:出栈的顺序与入栈的顺序正好相反。假设有栈A和栈B,其中A负责入队操作,B负责出队操作。首先两个栈都空,入队直接入到A中。可以把A的顶看成被模拟的队的队尾,栈底是队首。如果需要出队,就把A里的所有元素按顺序出栈,并入栈到B里。由于刚才说过出栈入栈顺序正好相反,这时在B里的栈顶就是队首,栈底就是队尾。从B里出栈就相当于从被模拟的队列里面出队。如果需要继续入队,就再把B里的元素按顺序出栈加入A,队尾就又变成了A的栈顶。

这种模拟的一个好处是可以用连续空间方便的操作队列,不用考虑队列顶部向前蠕动带来的内存分配问题,缺点是本来是O(1)的操作可能会变成O(n),不适用需要频繁交替出队入队的场合。

反向模拟想的时间稍微长了一些,最开始只能用队列模拟一个栈,过程是这样:入队相当于入栈,出栈时先把队里的(n-1)个元素出队再入队,这样本来在队尾的元素就变成了队首,而且没有改变其余元素的顺序。这时直接出队,就相当于出栈操作。这个利用了队列入队出队顺序不变的特性,相当于循环移位,把队尾的元素移动到队首。

后来很长一段时间没有想法怎么模拟两个栈,直到突然想到既然这个栈是在出队时增加了一个循环移位整个队列的操作,如果把这个操作换到入队时呢?于是想了一下,果然可以再模拟一个栈。(具体过程就不写了)这时相当于两个栈的栈底是连在一起,两个栈分别向两端增长。

这种模拟使一个栈的出栈的操作是O(m+n),另一个的入栈操作是O(m+n),都增大了不少。而且考虑到队列的内存分配问题,似乎没有什么优点。如果是同时使用两个栈,似乎还是栈底分离,相向增长的方式比较好。
  评论这张
 
阅读(702)| 评论(5)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017