功能

仓库是线性的，它是相同类型项目的调集，假如看过之前文章的朋友应该记得咱们有使用过。

在仓库中，元素的放入和弹出只发生在一侧，这能够被称之为 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()

复杂度

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

小结

它能够用于模仿一些问题的解决，比方 N皇后，中缀表明到前缀表明转化的。

它也被用于回溯，比方在迷宫找到正确途径的比方，假如从一点开始要去最终点，走不通时就需求回到起点挑选另一条路进行测验。

在仓库的应用下，咱们记住抵达的位置，把它放入堆，如果走错了，能够堆弹出最终一点然后回来到最终一点，这称为回溯。

这也是深度优先查找的比方，它查找从起始极点抵达途径图的一切极点。 分支界限是一种此类回溯查找的技能，无序尽头一切空间。

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

有兴趣的检查代码

github.com/hahamx/utoo…