堆和栈(Java数据结构)
博客专区 > 晓阳 的博客 > 博客详情
堆和栈(Java数据结构)
晓阳 发表于3年前
堆和栈(Java数据结构)
  • 发表于 3年前
  • 阅读 62
  • 收藏 0
  • 点赞 0
  • 评论 0

移动开发云端新模式探索实践 >>>   

摘要: 堆和栈(Java数据结构)

常见使用场景:

(英语:heap)亦被称为: 优先队列 (英语:priority queue),是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中,调度程序反复提取队列中第一个作业并运行,因而实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

n个元素序列{k1,k2...ki...kn},当且仅当满足下列关系时称之为堆: 
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2) 

性质 :

堆的实现通过构造二叉堆(binary heap),实为二叉树的一种;由于其应用的普遍性,当不加限定时,均指该数据结构的这种实现。这种数据结构具有以下 性 质。 任意节点小于它的所有后裔,最小元在堆的根上(堆序性)。堆总是一棵完全树。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆栈(栈)

(英语:stack),也可直接称栈。在计算机科学中,是一种特殊的串行形式的数据结构,它的特殊之处在于只能允许在链结串行或阵列的一端(称为堆栈顶端指标,英语:top)进行加入资料(英语:push)和输出资料(英语:pop)的运算。 

由于堆栈数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。 
堆栈数据结构使用两种基本操作:推入(push)和弹出(pop): 
推入:将数据放入堆栈的顶端(阵列形式或串行形式),堆栈顶端top指标加一。 
弹出:将顶端数据资料输出(回传),堆栈顶端资料减一。 


  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 9
博文 69
码字总数 52360
×
晓阳
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: