队列和栈相互转换及简单思考
在数据结构中常见的两个问题就是怎么用队列实现栈,怎么用栈实现队列,这两个数据结构的特性是相反的。昨天突然回忆到这个问题,就闪过了了一遍,用栈实现队列这个比较顺利没啥问题,但是用栈实现队列这个想了许久也没有想通。最后还是翻起了攻略,这两个其实我老早就看过当时也解决了,但是过了一段时间后就忘了 其实还是没有理解透彻呗!
用两个栈转换队列
这个其实没什么说的,因为栈是逆的 两个逆的就是顺的。 有点负负得正的感觉。或者是位操作中取反的操作。
insert->stackA->stackB->pop
就是所有的入队列 都吧数据存到栈A
所有的读数据都从栈B读取,当栈B数据没有的时候从A去转换
栈自带反转属性所以这个比较好理解
用两个队列实现栈
这个稍微就比较绕了,因为队列本身没有反转的属性,这里的核心点就是要自己实现反转的操作,
如何实现反转呢 我觉得这个瓶颈点就是 不能一次性反转,当时一直没想通,事每次insert操作都要反转
举个例子吧,看我灵魂画手
每次两个队列 必定有一个是空队列,插入的时候在空队列里面插入,然后取出另外一个队列里面的元素追加到这个队列里面,每次都这么操作 这样就是每次都取反当前元素 ,或者你这么理解
每次都往队列头部插入元素 ,每次插入都是开辟一个临时空间用来做头部然后把其他的元素接上就可以了,是不是就很通顺了
另外一个理解
每次都是取反 取反操作 就是
逻辑呢 :
方向是-> 就是右边的是队列头部的 ,左边的是队列尾部的
xy ->yx
插入a :a + 空 取反 空+ a = 空a
x=a,y=空 (空)(a)
插入b :b+空a 取反 空a + b = 空ab
x=b,y=空a (空a)(b)
插入c :c+空ab 取反 空ab +c= 空abc
x=c,y=空ab (空ab)(c)
其实这个就是 取反的操作,因为栈自带取反操作,所以 负负得正 直接用就可以了
但是队列是不带取反操作的,所以要自己实现,自己感觉好像抓到一点数学证明的影子,但是怎奈数学基础不咋的,不强行解释了 。