堆栈与堆
Stack是一个有序列表,其中列表项的**和删除只能在称为top的一端完成。因此,堆栈被认为是后进先出(后进先出)数据结构。Heap是一种基于树的特殊数据结构,它满足一种称为Heap属性的特殊属性。另外,堆是一个完整的树,这意味着树的叶子之间没有空隙,也就是说,在一个完整的树中,每一级都在向树中添加新的级别之前被填充,并且给定级别中的节点从左到右填充。
什么是堆栈?
如前所述,stack是一种数据结构,其中元素只从称为top的一端添加和删除。堆栈只允许两个基本操作,即push和pop。push操作将新元素添加到堆栈顶部。pop操作从堆栈顶部移除元素。如果堆栈已满,则在执行推送操作时,将其视为堆栈溢出。如果在已空的堆栈上执行pop操作,则将其视为堆栈下溢。由于可以在堆栈上执行的操作数量很少,因此它被视为一个受限制的数据结构。此外,根据push和pop操作的定义方式,很明显最后添加到堆栈中的元素首先从堆栈中移出。因此堆栈被认为是一种后进先出的数据结构。
什么是堆?
如前所述,heap是满足heap属性的完整树。堆属性声明,如果y是x的子节点,则存储在节点x中的值应大于或等于存储在节点y中的值(即值(x)≥值(y))。此属性表示值最大的节点将始终放在根节点。使用此属性构造的堆称为最大堆。heap属性的另一个变体与此相反。(即值(x)≤值(y))。这意味着具有最小值的节点将始终放在根节点,因此称为最小堆。在堆上执行的操作范围很广,例如查找最小值(在最小堆中)或最大值(在最大堆中)、删除最小值(在最小堆中)或最大值(在最大堆中)、增加(在最大堆中)或减少(在最小堆中)键等。
堆栈和堆的区别是什么?