基本介绍

  1. 有些程序员也把栈称为堆栈,即栈和堆栈是同一个概念
  2. 栈的英文为(stack)
  3. 栈是一个先入后出(FILO-First In Last Out)的有序列表。
  4. 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
  5. 根据堆栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

应用场景

  1. 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
  2. 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
  3. 表达式的转换与求值。
  4. 二叉树的遍历。
  5. 图形的深度优先(depth一first)搜索法。

数组模拟栈

  1. // 栈
  3. package main
  5. import (
  6.     "errors"
  7.     "fmt"
  8. )
  10. type Stack struct {
  11.     MaxTop int    // 栈的容量
  12.     Top    int    // 栈顶下标 默认 -1
  13.     arr    [5]int // 数组模拟栈
  14. }
  16. // 入栈
  17. func (stack *Stack) Push(val int) (err error) {
  18.     // 栈满
  19.     if stack.Top == stack.MaxTop-1 {
  20.         fmt.Println("stack full")
  21.         return errors.New("stack full")
  22.     }
  23.     stack.Top++
  24.     // 放入数据
  25.     stack.arr[stack.Top] = val
  26.     return
  27. }
  29. // 出栈
  30. func (stack *Stack) Pop() (val int, err error) {
  31.     if stack.Top == -1 {
  32.         fmt.Println("空栈")
  33.         return 0, errors.New("空栈")
  34.     }
  35.     // 取出数据
  36.     val = stack.arr[stack.Top]
  37.     stack.Top--
  38.     return val, nil
  39. }
  41. // 遍历栈
  42. func (stack *Stack) List() {
  43.     if stack.Top == -1 {
  44.         fmt.Println("空栈")
  45.         return
  46.     }
  48.     for i := stack.Top; i >= 0; i-- {
  49.         fmt.Printf("arr[%d] = %v \n", i, stack.arr[i])
  50.     }
  52. }
  54. func main() {
  55.     stack := &Stack{
  56.         MaxTop: 5,
  57.         Top:    -1,
  58.     }
  59.     stack.List()
  60.     fmt.Println("入栈")
  61.     stack.Push(1)
  62.     stack.Push(2)
  63.     stack.Push(3)
  64.     stack.Push(4)
  65.     stack.Push(5)
  66.     stack.Push(6)
  67.     // if err != nil {
  68.     //     fmt.Println("push 出错了", err)
  69.     // }
  71.     fmt.Println("显示栈1")
  72.     stack.List()
  73.     fmt.Println("出栈")
  74.     val, err := stack.Pop()
  75.     if err == nil {
  76.         fmt.Printf("出栈数据： %v \n", val)
  77.     }
  78.     val, err = stack.Pop()
  79.     if err == nil {
  80.         fmt.Printf("出栈数据： %v \n", val)
  81.     }
  82.     val, err = stack.Pop()
  83.     if err == nil {
  84.         fmt.Printf("出栈数据： %v \n", val)
  85.     }
  86.     val, err = stack.Pop()
  87.     if err == nil {
  88.         fmt.Printf("出栈数据： %v \n", val)
  89.     }
  90.     val, err = stack.Pop()
  91.     if err == nil {
  92.         fmt.Printf("出栈数据： %v \n", val)
  93.     }
  94.     fmt.Println("显示栈2")
  95.     stack.List()
  96. }
  98. /*
  99. 空栈
  100. 入栈
  101. stack full
  102. 显示栈1
  103. arr[4] = 5
  104. arr[3] = 4
  105. arr[2] = 3
  106. arr[1] = 2
  107. arr[0] = 1
  108. 出栈
  109. 出栈数据： 5
  110. 出栈数据： 4
  111. 出栈数据： 3
  112. 出栈数据： 2
  113. 出栈数据： 1
  114. 显示栈2
  115. 空栈
  116. */