線性表中，棧和隊列是非常重要的兩種數(shù)據(jù)結構，本文將就這兩種數(shù)據(jù)結構進行 golang語言實現(xiàn)
一.棧的實現(xiàn)
我們需要實現(xiàn)如下幾個方法
- push()????????向棧中壓入一個元素
- pop()??????????從棧頂取出一個元素
- isEmpty()????判斷棧是否為空
- length()??????獲取棧中元素的數(shù)目
- peer()?????????查詢棧頂元素
我們需要注意 peer() 方法并不會將棧頂元素刪除
數(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]
}
接下來，我們將用鏈表實現(xiàn)以下項目，并使用 interface{} 來代替 int實現(xiàn)多種類型的兼容
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
}
由于任何的變量都實現(xiàn)了空接口，所以我們可以通過傳遞空接口來實現(xiàn)在棧中壓入不同元素的目的
二.隊列實現(xiàn)
同樣，我們對于隊列，實現(xiàn)了如下方法：
- enqueue()??????????入隊列
- dequeue()??????????出隊列
- isEmpty()????????????判斷隊列是否為空
- getLength()????????獲隊列的長度
鏈表實現(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
}
三.棧和隊列的應用
在這一部分，我們通過棧來實現(xiàn)表達式的計算
例如：我們需要計算 (1+((2+3)*(4*5)))
我們維護兩個棧，一個是值棧，一個是操作棧，我們在讀取表達式的時候采取如下的策略：
- 如果遇到 '('，我們將忽略它
- 如果遇到數(shù)字，將其壓入值棧
- 如果遇到操作符，將其壓入操作棧
- 如果遇到 ')'，我們從值棧中取出兩個值 n1和 n2，在操作棧中，我們?nèi)〕鲆粋€操作符 op
- 我們進行 n2 op n1的操作（例如 n1 = 3，n2 = 9，op = '/'，我們將執(zhí)行 9/3 ）
- 將所得的結果壓入值棧
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)))")
將會得到結果 101
