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

棧和隊(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)棧。

兩個(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 中的棧頂元素保存，并彈棧。