likes
comments
collection
share

附2 堆的例子和应用

作者站长头像
站长
· 阅读数 5

功能

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

在堆栈中,元素的放入和弹出只发生在一侧,这可以被称之为 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…

转载自:https://juejin.cn/post/7183963710291968061
评论
请登录