面试题 : 两个栈如何实现一个队列 ??

OscerSong 发布于 2013/04/18 16:43
阅读 648
收藏 0
面试题 :  两个栈如何实现一个队列  ??
加载中
0
lwdxinghuo
lwdxinghuo
假设分别为栈A、B,对于队列操作 入队 将数据假如栈A, 出队列,首先查询A是否为空,不为空将所有数据入栈到B,从B出栈一个数据为出队列, 如果A、B都为空,则队列空   大概就是这个意思吧
0
立志尚早
立志尚早

假设有数据  4、1、3、A  要实现队列,队列原则是先进先出。再假设有 甲、乙两栈,现将所有数据入甲栈,步骤如下:

                甲栈                  乙栈                        数据    

  1.       4-1-3-A                    
  2.         4                            A-3-1                                
  3.                                       A-3-1                                 4    
  4.         1-3-A                                                               4
  5.         1                              A-3                                  4
  6.                                         A-3                                 4-1
  7.         3-A                                                                 4-1
  8.         3                                A                                  4-1
  9.                                           A                                 4-1-3
  10.                                                                             4-1-3-A

规律是显而易见,取甲栈除开栈底元素 入 乙栈  取出甲栈栈底元素输出

取乙栈所有元素入甲栈 ,重复以上步骤,既实现队列功能。

最后加个判断 乙栈 只剩一个元素,就直接输出。

0
looyer
looyer
将队列头看做是B栈顶,将队尾看做是A栈顶即可。
0
Xsank
Xsank
看来是常见面试题 
0
变成马甲了哈哈
变成马甲了哈哈
不就是俩柱儿的汉诺塔吗
0
中山野鬼
中山野鬼
不过这种也是挺无聊的面试。哈哈。
OscerSong
OscerSong
说的是啊
0
hylent
hylent

先入a栈 然后出栈 入b栈 使用的时候用b栈 这样次序就对了么 栈间移动元素这个过程是在b栈为空的情况下进行

0
viwii
viwii
数据在两个栈里面倒腾来倒腾去,保证FIFO就行了
0
Cloud_Lee
Cloud_Lee

不就是大学 数据结构中的问题吗

把栈底拼一起就搞定了

返回顶部
顶部