Go 語(yǔ)言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)：棧和隊(duì)列

線性表中，棧和隊(duì)列是非常重要的兩種數(shù)據(jù)結(jié)構(gòu)，本文將就這兩種數(shù)據(jù)結(jié)構(gòu)進(jìn)行 golang語(yǔ)言實(shí)現(xiàn)

一.棧的實(shí)現(xiàn)

我們需要實(shí)現(xiàn)如下幾個(gè)方法

1. push() ? ?向棧中壓入一個(gè)元素
2. pop() ? ? 從棧頂取出一個(gè)元素
3. isEmpty() ?判斷棧是否為空
4. length() ? 獲取棧中元素的數(shù)目
5. peer() ? ? 查詢(xún)棧頂元素

我們需要注意 peer() 方法并不會(huì)將棧頂元素刪除

數(shù)組實(shí)現(xiàn)如下：

type?stack?struct?{
????cache?[]int
}

func?(sk?*stack)?push(n?int)?{
????sk.cache?=?append(sk.cache,?n)
}

func?(sk?stack)?length()?int?{
????return?len(sk.cache)
}
func?(sk?*stack)?pop()?int?{
????if?sk.length()?==?0?{
????????return?0
????}
????item?:=?sk.cache[sk.length()-1]
????sk.cache?=?sk.cache[:len(sk.cache)-1]
????return?item
}
func?(sk?stack)?isEmpty()?bool?{
????return?len(sk.cache)?==?0
}
func?(sk?stack)?peer()?int?{
????return?sk.cache[sk.length()-1]
}

接下來(lái)，我們將用鏈表實(shí)現(xiàn)以下項(xiàng)目，并使用 interface{} 來(lái)代替 int實(shí)現(xiàn)多種類(lèi)型的兼容

type?stackLink?struct?{
????Top????*node
????Length?int
}

type?node?struct?{
????Val??interface{}
????Prev?*node
}

func?(sl?*stackLink)?push(value?interface{})?{
????newNode?:=?&node{
????????Val:??value,
????????Prev:?sl.Top}
????sl.Top?=?newNode
????sl.Length++
}

func?(sl?*stackLink)?pop()?interface{}?{
????topNodeVal?:=?sl.Top.Val
????sl.Top?=?sl.Top.Prev
????sl.Length--
????return?topNodeVal
}

func?(sl?stackLink)?length()?int?{
????return?sl.Length
}

func?(sl?stackLink)?isEmpty()?bool?{
????return?sl.Length?==?0
}

func?(sl?stackLink)?peer()?interface{}?{
????return?sl.Top.Val
}

由于任何的變量都實(shí)現(xiàn)了空接口，所以我們可以通過(guò)傳遞空接口來(lái)實(shí)現(xiàn)在棧中壓入不同元素的目的

二.隊(duì)列實(shí)現(xiàn)

同樣，我們對(duì)于隊(duì)列，實(shí)現(xiàn)了如下方法：

1. enqueue() ? ? 入隊(duì)列
2. dequeue() ? ? 出隊(duì)列
3. isEmpty() ? ? ?判斷隊(duì)列是否為空
4. getLength() ? ?獲隊(duì)列的長(zhǎng)度

鏈表實(shí)現(xiàn)方式如下：

type?queue?struct?{
????First?*node
????Last??*node
????Len???int
}

type?node?struct?{
????Val??interface{}
????Next?*node
????Pre??*node
}
func?(qu?*queue)?enqueue(data?interface{})?{
????nNode?:=?&node{
????????Val:??data,
????????Pre:??qu.First,
????????Next:?nil}
????if?qu.First?==?nil?{
????????qu.First?=?nNode
????}?else?{
????????qu.First.Next?=?nNode
????????qu.First?=?nNode
????}
????if?qu.Last?==?nil?{
????????qu.Last?=?nNode
????}
????qu.Len++
}

func?(qu?*queue)?dequeue()?interface{}?{
????if?qu.Len?>?0?{
????????nNode?:=?qu.Last.Val
????????if?qu.Last.Next?!=?nil?{
????????????qu.Last.Next.Pre?=?nil
????????}
????????qu.Last?=?qu.Last.Next
????????qu.Len--
????????return?nNode
????}
????return?errors.New("error")
}

func?(qu?queue)?isEmpty()?bool?{
????return?qu.Len?<=?0
}

func?(qu?queue)?getLength()?int?{
????return?qu.Len
}

三.棧和隊(duì)列的應(yīng)用

在這一部分，我們通過(guò)棧來(lái)實(shí)現(xiàn)表達(dá)式的計(jì)算 例如：我們需要計(jì)算 (1+((2+3)(45)))

我們維護(hù)兩個(gè)棧，一個(gè)是值棧，一個(gè)是操作棧，我們?cè)谧x取表達(dá)式的時(shí)候采取如下的策略：

1. 如果遇到 '('，我們將忽略它
2. 如果遇到數(shù)字，將其壓入值棧
3. 如果遇到操作符，將其壓入操作棧
4. 如果遇到 ')'，我們從值棧中取出兩個(gè)值 n1和 n2，在操作棧中，我們?nèi)〕鲆粋€(gè)操作符 op
5. 我們進(jìn)行 n2 op n1的操作（例如 n1 = 3，n2 = 9，op = '/'，我們將執(zhí)行 9/3 ）
6. 將所得的結(jié)果壓入值棧

func?stackCompute(str?string)?int?{
????var?(
????????vsk??stackLink
????????opsk?stackLink
????)
????for?_,?v?:=?range?str?{
????????if?v?<=?'9'?&&?v?>=?'0'?{
????????????vsk.push(int(v)?-?'0')
????????}?else?if?v?==?'+'?||?v?==?'-'?||?v?==?'*'?||?v?==?'/'?{
????????????opsk.push(int(v))
????????}?else?if?v?==?')'?{
????????????n1?:=?vsk.pop().(int)
????????????n2?:=?vsk.pop().(int)
????????????op?:=?opsk.pop().(int)
????????????var?ans?int
????????????switch?op?{
????????????case?'+':
????????????????ans?=?n2?+?n1
????????????case?'-':
????????????????ans?=?n2?-?n1
????????????case?'*':
????????????????ans?=?n2?*?n1
????????????case?'/':
????????????????ans?=?n2?/?n1
????????????}
????????????vsk.push(int(ans))
????????}
????}
????for?!opsk.isEmpty()?{
????????n1?:=?vsk.pop().(int)
????????n2?:=?vsk.pop().(int)
????????op?:=?opsk.pop().(int)
????????var?ans?int
????????switch?op?{
????????case?'+':
????????????ans?=?n2?+?n1
????????case?'-':
????????????ans?=?n2?-?n1
????????case?'*':
????????????ans?=?n2?*?n1
????????case?'/':
????????????ans?=?n2?/?n1
????????}
????????vsk.push(int(ans))
????}
????char?:=?vsk.pop().(int)
????return?int(char)
}

我們?nèi)缦抡{(diào)用

stackCompute("(1+((2+3)\*(4\*5)))")
將會(huì)得到結(jié)果?101

參考文獻(xiàn)：Dynamic Connectivity - 普林斯頓大學(xué) | Coursera

作者：YXCoder

鏈接：https://www.jianshu.com/p/e8de9ac93cbc

來(lái)源：簡(jiǎn)書(shū)

著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。