1 堆栈功能

堆栈是线性的，它是相同类型项目的集合，如果看过之前文章的朋友应该记得我们有使用过，这里继续记录。

在堆栈中，元素的放入和弹出只发生在一侧，这可以被称之为 LIFO，先进后出。

  该策略表示最后放入的元素将最先出来。
  你可以拿一口井 作为现实生活中的例子。 然后向里面放入石板。
  我们最后放进井中的石板在最上面，因为我们移除了最上面的石板，
  所以我们可以说最后放的石板最先出来。

当一个元素被push 放入到堆时，它就成为第一个被弹出的元素。如果要获得最早放入的项目，则必须全部取出堆的内容。

• 它被以下基本操作所支持，因此称之为堆。

  push 添加元素到堆顶
  
  pop 从堆中删除最顶层远程
  
  isEmpty 检测是否为空
  
  isFull 是否已满
  
  peek 查看顶层元素
  

  我们的结构体内部使用 切片保存全部元素，将所有数据都以interface的方式存入堆，

    type Stack struct {
       items []interface{}
   }
  

  我们并以string的方式返回。

  // 转换为 字符串
   func ToString(inter interface{}) string {
       ...
    }
  

指针peek 被设置为堆最顶层元素，初始化为 -1，通过比较执行检查堆是否为空。
如创建一个新堆

   ns := NewStack()

该程序ns允许用户 放入，弹出，显示，判断状态几个操作。

• 判空

  func (sk *Stack) IsEmpty() bool {
      return len(sk.items) == 0
  }
  

• 压入数据

  func (sk *Stack) Push(value interface{}) {
      sk.items = append(sk.items, value)
  }
  

• 弹出最近的数据

  func (sk *Stack) Pop() string {
      if sk.IsEmpty() {
          panic("under stack flow.")
      }
      lastOne := sk.items[len(sk.items)-1]
      sk.items = sk.items[:len(sk.items)-1]
      return ToString(lastOne)
  }
  

• 查看最近的数据

   func (sk *Stack) Peek() string {
       if sk.IsEmpty() {
           panic("under stack flow.")
       }
       ps := sk.items[len(sk.items)-1]
       return ToString(ps)
   }
  

• 执行 push(1) 将数字 1 放入堆

  ns.Push(1)
  

• 执行peek() 查看顶层数据

   func (sk *Stack) Peek() string {
       if sk.IsEmpty() {
           panic("under stack flow.")
       }
       ps := sk.items[len(sk.items)-1]
       return ToString(ps)
   }
  

  • 执行pop() 将顶层输出取出

    ns.Pop()

2 复杂度

由于堆操作每次只能访问一个元素，因此在其中执行push，pop操作 总是需要O(1)时间。

3 小结

它可以用于模拟一些问题的解决，比如 N皇后，中缀表示到前缀表示转换的。

它也被用于回溯，比如在迷宫找到正确路径的例子，如果从一点开始要去最终点，走不通时就需要回到起点选择另一条路进行尝试。

在堆栈的应用下，我们记住到达的位置，把它放入堆，万一走错了，可以堆弹出最后一点然后返回到最后一点，这称为回溯。

这也是深度优先搜索的例子，它查找从起始顶点到达路径图的所有顶点。 分支界限是一种此类回溯搜索的技术，无序穷尽所有空间。

它也被用于编译时内存空间管理，因为许多语言也是面向堆的。 因此也容易产生安全漏洞和受到攻击。同样一些扫描算法和安全算法也使用它。

有兴趣的查看代码

https://github.com/hahamx/utools/blob/main/utils/queues/stack.go