go 实现栈

约定不等于承诺〃 2021-07-24 11:42 308阅读 0赞

# 一 点睛 #

有些程序员也把栈称为堆栈，其实栈和堆栈是同一个概念。

1 栈的英文为(stack)。

2 栈是一个 先入后出(FILO-First In Last Out)的有序列表。

3 栈(stack)限制线性表中元素的插入和删除。只能在线性表的同一端进行操作。允许插入和删除的一端，为变化的一端，称为 栈顶(Top)， 另一端为固定的一端，称为栈底(Bottom)。

4 根据堆栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。

# 二 图解入栈和出栈 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

# 三 栈的应用 #

1 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。

2 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。

3 表达式的转换与求值。

4 二叉树的遍历。

5 图形的深度优先(depth 一 first)搜索法。

# 四 代码 #

package main
    
    import (
       "errors"
       "fmt"
    )
    
    // 使用数组来模拟一个栈
    type Stack struct {
       MaxTop int    // 栈最大可以存放数个数
       Top    int    // 栈顶, 因为栈顶固定，因此我们直接使用 Top
       arr    [5]int // 数组模拟栈
    }
    
    // 入栈
    func (this *Stack) Push(val int) (err error) {
       // 判断栈是否满
       if this.Top == this.MaxTop-1 {
          fmt.Println("stack full")
          return errors.New("stack full")
       }
       this.Top++
       // 放入数据
       this.arr[this.Top] = val
       return
    }
    
    // 出栈
    func (this *Stack) Pop() (val int, err error) {
       // 判断栈是否空
       if this.Top == -1 {
          fmt.Println("stack empty!")
          return 0, errors.New("stack empty")
       }
       // 先取值，再 this.Top--
       val = this.arr[this.Top]
       this.Top--
       return val, nil
    }
    
    // 遍历栈，注意需要从栈顶开始遍历
    func (this *Stack) List() {
       // 先判断栈是否为空
       if this.Top == -1 {
          fmt.Println("stack empty")
          return
       }
       fmt.Println("栈的情况如下：")
       for i := this.Top; i >= 0; i-- {
          fmt.Printf("arr[%d]=%d\n", i, this.arr[i])
       }
    }
    
    func main() {
       stack := &Stack{
          MaxTop: 5,  // 最多存放5个数到栈中
          Top:    -1, // 当栈顶为-1，表示栈为空
       }
       // 入栈
       stack.Push(1)
       stack.Push(2)
       stack.Push(3)
       stack.Push(4)
       stack.Push(5)
       // 显示
       stack.List()
       val, _ := stack.Pop()
       fmt.Println("出栈val=", val) // 5
       // 显示
       stack.List() //
       fmt.Println()
       val, _ = stack.Pop()
       val, _ = stack.Pop()
       val, _ = stack.Pop()
       val, _ = stack.Pop()
       val, _ = stack.Pop()       // 出错
       fmt.Println("出栈val=", val) // 5
       // 显示
       stack.List()
    }

# 五 测试 #

> 栈的情况如下：
> 
> arr\[4\]=5
> 
> arr\[3\]=4
> 
> arr\[2\]=3
> 
> arr\[1\]=2
> 
> arr\[0\]=1
> 
> 出栈val= 5
> 
> 栈的情况如下：
> 
> arr\[3\]=4
> 
> arr\[2\]=3
> 
> arr\[1\]=2
> 
> arr\[0\]=1
> 
>  
> 
> stack empty!
> 
> 出栈val= 0
> 
> stack empty

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/443b3581e64e42f489ac7fc325b0c582.png