?

前言

棧和隊(duì)列是比較基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。無(wú)論在工作中，還是在面試中，棧和隊(duì)列都用的比較多。在計(jì)算機(jī)的世界，你會(huì)看到隊(duì)列和棧，無(wú)處不在。
?

棧：一個(gè)先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)

隊(duì)列：一個(gè)先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)
?

棧和隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)，同時(shí)也存在某種聯(lián)系。用棧可以實(shí)現(xiàn)隊(duì)列，用隊(duì)列也可以實(shí)現(xiàn)棧。

?

海邊風(fēng)景不錯(cuò)，欣賞一下風(fēng)景，下面開(kāi)始步入正題。學(xué)完這篇，咱們?cè)俳又达L(fēng)景。

?

兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列

思路：讓數(shù)據(jù)入stack1，然后棧stack1中的數(shù)據(jù)出棧并入到棧stack2，然后出stack2。

代碼如下：

type?CQueue?struct?{stack1,?stack2?*list.List }//構(gòu)造函數(shù)???? func?Constructor()?CQueue?{return?CQueue{stack1:?list.New(),stack2:?list.New(),} }//尾部插入 func?(this?*CQueue)?AppendTail(value?int)??{this.stack1.PushBack(value) }//頭部刪除,back函數(shù)返回其list最尾部的值 func?(this?*CQueue)?DeleteHead()?int?{//如果第二個(gè)棧為空if?this.stack2.Len()?==?0?{for?this.stack1.Len()?>?0?{this.stack2.PushBack(this.stack1.Remove(this.stack1.Back()))}}if?this.stack2.Len()?!=?0?{e?:=?this.stack2.Back()this.stack2.Remove(e)return?e.Value.(int)}return?-1 }

先調(diào)用 AppendTail 函數(shù)將所有元素插入 stack1，在調(diào)用 DeleteHead 函數(shù)將 stack1 中的元素轉(zhuǎn)移到 stack2 中，再將元素再出棧。

再調(diào)用 DeleteHead 時(shí)，先判斷 statck2 是否為空，為空則將 stack1 元素移動(dòng)到 stack2 中，然后將 stack2 中的棧頂元素保存，并彈棧。

?

兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧

思路：兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧，使用了隊(duì)列交換的思想。
?

代碼如下：

type?MyStack?struct?{queue1,?queue2?[]int }//構(gòu)造函數(shù) func?Constructor()?(s?MyStack)?{return }func?(s?*MyStack)?Push(x?int)?{s.queue2?=?append(s.queue2,?x)for?len(s.queue1)?>?0?{s.queue2?=?append(s.queue2,?s.queue1[0])s.queue1?=?s.queue1[1:]}s.queue1,?s.queue2?=?s.queue2,?s.queue1 }func?(s?*MyStack)?Pop()?int?{v?:=?s.queue1[0]s.queue1?=?s.queue1[1:]return?v }func?(s?*MyStack)?Top()?int?{return?s.queue1[0] }func?(s?*MyStack)?Empty()?bool?{return?len(s.queue1)?==?0 }

?

先將元素入對(duì)到 queue2，此時(shí) queue1 為0，交換 queue2 和 queue1。此時(shí) queue2 為0，queue1 中有1個(gè)元素。

再執(zhí)行push操作時(shí)，len(queue1)?> 0，此時(shí)再把 queue1 中的元素插入queue2 的尾部，然后將 queue2 和 queue1 進(jìn)行交換。
此時(shí)相當(dāng)于，插入 queue2 的兩個(gè)元素的位置發(fā)生了交換并保存在 queue1中。最后將 queue1 中的元素出隊(duì)，這樣就可以保證后插入的元素先出。

不斷執(zhí)行 push 操作就行。

??

一個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧

思路：使用一個(gè)隊(duì)列時(shí)，將當(dāng)前插入元素前面的所有元素,先出隊(duì)再入隊(duì)即可。

代碼如下：

type?MyStack?struct?{queue?[]int }func?Constructor()?(s?MyStack)?{return }func?(s?*MyStack)?Push(x?int)?{n?:=?len(s.queue)s.queue?=?append(s.queue,?x)for?;?n?>?0;?n--?{s.queue?=?append(s.queue,?s.queue[0])s.queue?=?s.queue[1:]} }func?(s?*MyStack)?Pop()?int?{v?:=?s.queue[0]s.queue?=?s.queue[1:]return?v }func?(s?*MyStack)?Top()?int?{return?s.queue[0] }func?(s?*MyStack)?Empty()?bool?{return?len(s.queue)?==?0 }

每次執(zhí)行 push 操作，如果queue存在元素，則將新插入元素前的所有元素出隊(duì)，然后依次進(jìn)隊(duì)。這樣新插入的元素就在隊(duì)首了。

?

絮叨

棧和隊(duì)列作為基礎(chǔ)的數(shù)據(jù)，大家務(wù)必掌握其性質(zhì)和功能，知道它們之間的某種依存關(guān)系，才能靈活運(yùn)用。

上面的算法雖然很簡(jiǎn)單，但是思路很巧妙，還有其他解法，大家也可仔細(xì)研究，必有收獲。有本數(shù)據(jù)結(jié)構(gòu)的書(shū)<<大話(huà)數(shù)據(jù)結(jié)構(gòu)>>推薦給大家。

?

---

專(zhuān)注后臺(tái)開(kāi)發(fā)相關(guān)技術(shù)，廣度深度并存，干貨情懷同在。
微信搜索【盼盼編程】關(guān)注這個(gè)不一樣的程序員。

總結(jié)

以上是生活随笔為你收集整理的栈和队列互相实现，一文弄懂它们的关系的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。