棧和隊列互相實(shí)現(xiàn)，一文弄懂它們的關(guān)系

前言

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

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

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

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

海邊風(fēng)景不錯，欣賞一下風(fēng)景，下面開始步入正題。學(xué)完這篇，咱們再接著看風(fēng)景。

兩個棧實(shí)現(xiàn)一個隊列

思路：讓數(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 {
    //如果第二個棧為空
    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 時，先判斷 statck2 是否為空，為空則將 stack1 元素移動到 stack2 中，然后將 stack2 中的棧頂元素保存，并彈棧。

兩個隊列實(shí)現(xiàn)一個棧

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

代碼如下：

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
}

先將元素入對到 queue2，此時 queue1 為0，交換 queue2 和 queue1。此時 queue2 為0，queue1 中有1個元素。

再執(zhí)行push操作時，len(queue1) > 0，此時再把 queue1 中的元素插入queue2 的尾部，然后將 queue2 和 queue1 進(jìn)行交換。

此時相當(dāng)于，插入 queue2 的兩個元素的位置發(fā)生了交換并保存在 queue1中。最后將 queue1 中的元素出隊，這樣就可以保證后插入的元素先出。

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

  

一個隊列實(shí)現(xiàn)一個棧

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

代碼如下：

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存在元素，則將新插入元素前的所有元素出隊，然后依次進(jìn)隊。這樣新插入的元素就在隊首了。

絮叨

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

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

點(diǎn)擊關(guān)注公眾號，領(lǐng)取學(xué)習(xí)資料