栈

定义

// 线性表的一种，构造上一端凋谢、一端关闭
// 凋谢的一端，容许进行插入和删除操作，称为栈顶
// 关闭的一端，成为栈底

// 依据定义写出栈的结构构造体(假设栈中都是整型元素)
type Stack struct {
    // 一个寄存栈元素的容器
    container []int
    // 栈顶标记
    top int
    // 容量限度
    size int
}

// 依据构造体写出栈的构造方法
func NewStack(size int) *Stack {
    // 返回的是Stack构造体指针
    return &Stack{
        // 用切片来示意栈容器
        container: make([]int, size),
        // 初始栈顶元素为0
        top: 0,
        // 容量限度同入参size
        size: size,
    }
}

基本操作

栈判空：栈顶标记为零
栈判满：栈顶标记等于容量限度
入栈：把某一元素放入栈顶
出栈：把栈顶元素取出

// 栈判空
func (s *Stack) IsEmpty() bool {
    if s.top == 0 {
        return true
    }
    return false
}

// 栈判满
func (s *Stack) IsFull bool {
    if s.top == s.size {
        return true
    }
    return false
}

// 入栈
func (s *Stack) Push(e int) bool {
    if s.IsFull() {
        fmt.Println(false, e)
        return false
    }
    s.container[s.top] = e
    s.top++
    fmt.Println(true, e)
    return true
}

// 出栈
func (s *Stack) Pop() (flag bool, ret int) {
    if s.IsEmpty() {
        return false, ret
    }
    ret = s.container[s.top]
    s.top--
    return true, ret
}

测试

func main() {
    s := NewStack(5)
    s.Push(1)
    s.Push(2)
    s.Push(3)
    s.Push(4)
    s.Push(5)
    s.Push(6)
    fmt.Println(s.Pop())
    fmt.Println(s.Pop())
    fmt.Println(s.Pop())
    fmt.Println(s.Pop())
    fmt.Println(s.Pop())
    fmt.Println(s.Pop())
}

// 运行后果
true 1
true 2
true 3
true 4
true 5
false 6
true 5
true 4
true 3
true 2
true 1
false 0