1、棧的定義

• 棧(stack)是限定僅在表尾進(jìn)行插入或刪除操作的線性表。
  • 棧頂(top)，指表尾端。
  • 棧底(bottom)，指表頭端。
  • 空棧，即不含元素的空表。
  • LIFO(Last In First Out)，即棧的修改是按后進(jìn)先出的原則進(jìn)行的。
  • 順序棧， 指利用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧，即利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置。

棧中元素和指針之間的關(guān)系圖

• 由于順序棧的插入和刪除只在棧頂進(jìn)行，其他操作和順序表類似，本文只給出了以下基本操作。
  • 初始化
  • 入棧
  • 出棧
  • 取棧頂元素

2、順序棧的初始化

type Stack struct {
    top int
    base int
    stackSize int
    stackList []interface{}
}

//棧的初始化
func initStack(size int, arr []interface{}) *Stack{
    if size <= 0 {return new(Stack)}
    list := &Stack{
        top:       0,
        base:      0,
        stackSize: size,
        stackList: make([]interface{}, 0, size),
    }

    for i := range arr {
        list.stackList = append(list.stackList, arr[i])
        list.top ++
    }
    return list
}

3、入棧

//入棧
func (stack *Stack) push(val interface{}) {
    if stack.top - stack.base == stack.stackSize{
        fmt.Println("棧滿")
        return
    }
    stack.stackList = append(stack.stackList, val)
    stack.top ++
}

4、出棧

//出棧
func (stack *Stack) pop() interface{}{
    if stack.top == stack.base {
        fmt.Println("棧空")
        return nil
    }
    val := stack.stackList[stack.top - 1]
    stack.top --
    stack.stackList = append(stack.stackList[:stack.top])
    return val
}

5、取棧頂元素

//取棧頂元素
func (stack *Stack) getTop() interface{} {
    if stack.top == stack.base {
        fmt.Println("棧空")
        return nil
    }
    val := stack.stackList[stack.top - 1]
    return val
}

6、完整代碼即結(jié)果展示

package main

import "fmt"

type Stack struct {
    top int
    base int
    stackSize int
    stackList []interface{}
}


//棧的初始化
func initStack(size int, arr []interface{}) *Stack{
    if size <= 0 {return new(Stack)}
    list := &Stack{
        top:       0,
        base:      0,
        stackSize: size,
        stackList: make([]interface{}, 0, size),
    }

    for i := range arr {
        list.stackList = append(list.stackList, arr[i])
        list.top ++
    }
    return list
}

//入棧
func (stack *Stack) push(val interface{}) {
    if stack.top - stack.base == stack.stackSize{
        fmt.Println("棧滿")
        return
    }
    stack.stackList = append(stack.stackList, val)
    stack.top ++
}

//出棧
func (stack *Stack) pop() interface{}{
    if stack.top == stack.base {
        fmt.Println("?？?)
        return nil
    }
    val := stack.stackList[stack.top - 1]
    stack.top --
    stack.stackList = append(stack.stackList[:stack.top])
    return val
}

//取棧頂元素
func (stack *Stack) getTop() interface{} {
    if stack.top == stack.base {
        fmt.Println("?？?)
        return nil
    }
    val := stack.stackList[stack.top - 1]
    return val
}

func main()  {
    data := []interface{}{
        "bala",
        "aa",
        12,
        45,
    }
    //var data2 []interface{}
    L := initStack(6, data)
    fmt.Println(L)

    L.push("99")
    fmt.Println(L)

    fmt.Printf("棧頂元素為:%s\n", L.getTop())
    fmt.Println(L.pop())
    fmt.Println(L)
}

&{4 0 6 [bala aa 12 45]}
&{5 0 6 [bala aa 12 45 99]}
棧頂元素為:99
99
&{4 0 6 [bala aa 12 45]}

7、總結(jié)

• 和鏈棧一起總結(jié)了