数据结构 堆与堆栈_堆栈vs堆–数据结构中堆栈和堆的区别
数据结构 堆与堆栈
In this tutorial you will learn about stack vs heap data structures.
在本教程中，您将学习堆栈与堆数据结构。
Stack
叠放
Stack is a simple data structure used for storing data. In stack, the order in which the data arrives is important. A suitable example for stack is, a pile of plates in kitchen. When we want a plate we will take which was last placed in that pile. This is the main property of stack we say Last in first Out (LIFO) or First in Last out (FILO). So stack is a ordered list in which insertion and deletion are done at one end, called top.
堆栈是用于存储数据的简单数据结构。 在堆栈中，数据到达的顺序很重要。 适用于堆叠的示例是厨房中的一堆盘子。 当我们想要一个盘子时，我们将把最后放在盘子里的盘子拿走。 这是堆栈的主要属性，我们说后进先出(LIFO)或先进先出(FILO)。 因此，堆栈是一个有序列表，其中插入和删除在一端完成，称为top。
Stack Operations:
堆栈操作：
Push: When an element inserted into the stack, we call it as push operation.
推入：将元素插入堆栈时，我们将其称为推入操作。
Top: When we want to know what is the top element of the stack we get it by top operation.
顶部：当我们想知道什么是堆栈的顶部元素时，我们可以通过顶部操作来获得它。
Pop: When we remove an element from the top of the stack, we call it as pop operation.
弹出：当我们从堆栈顶部删除元素时，我们称其为弹出操作。
IsEmptyStack(): To check whether stack is empty or not.
IsEmptyStack ()：检查堆栈是否为空。
IsFullStack(): To check stack is full or not.
IsFullStack()：检查堆栈是否已满。
And some other properties are,
还有其他一些特性，
Stack underflow: When we want to pop an element from the empty stack, that situation is called stack underflow.
堆栈下溢：当我们要从空堆栈中弹出一个元素时，这种情况称为堆栈下溢。
Stack overflow: When we want to push an element to a full stack (i.e stack elements equal to stack size), that situation is called stack overflow.
堆栈溢出：当我们想将一个元素压入一个完整的堆栈(即等于堆栈大小的堆栈元素)时，这种情况称为堆栈溢出。
Also Read: Difference Between Stack and Queue
另请阅读： 堆栈和队列之间的区别
Heap
堆
Heap is a tree with some special property. That special property of the heap is, the value of a node must be >= or <= to its children. And one most important property of heap is all leaves must be at level h or at h-1. (where h is the height of the tree). This also called heap must be a complete binary tree.
堆是具有某些特殊属性的树。 堆的特殊属性是，节点的子节点的值必须> =或<=。 堆的最重要属性是所有叶子必须位于h或h-1处。 (其中h是树的高度)。 这也称为堆，必须是完整的二叉树。
Types of Heaps:
堆的类型：
Min Heap: The value of the node must be less than or equal to the values of its children.
最小堆：节点的值必须小于或等于其子节点的值。
Max Heap: The value of the node must be greater than or equal to the values of its children.
最大堆：节点的值必须大于或等于其子节点的值。
Finding minimum element, deleting minimum element, are easy operations in min heap.
查找最小元素，删除最小元素是最小堆中的简单操作。
Finding maximum element, deleting maximum element, are easy operations in max heap.
查找最大元素，删除最大元素是最大堆中的简单操作。
Binary Min Heap
二进制最小堆
Binary Max Heap
二进制最大堆
堆栈与堆–堆栈与堆之间的区别 (Stack vs Heap – Difference between Stack and Heap)
| Stack | Heap |
| 1) Stack is a linear data structure. | 1) Heap is a hierarchical data structure. |
| 2) Elements in stack follow LIFO or FILO property. | 2) Elements in heap follow heap property (mentioned above). |
| 3) Push, Pop, Top are the only allowed operations on the stack. | 3) Almost all tree operations can be applied on heaps. Heapifying an element, find minimum, find maximum are some examples. |
| 4) All mentioned operations, push, pop, top, IsEmptyStack(), IsFullStack(), Size(), takes O(1) time in stack. | 4) In heap, insertion takes O(log n) time. And finding min, deleting min (in min – heap), finding max, deleting max (in max – heap) takes O(1) time. |
| 5) Stack can be implemented in 3 ways that, simple array based, dynamic array based and Linked list based implementation. | 5) Heap can be implemented using arrays, and trees. |
| 6) We can limit stack size, so that stack overflow, stack underflow conditions will occur. | 6) There is no case of overflow and underflow in heap. |
| 7) Balancing of symbols, infix – to – postfix conversions, undo sequence in a text editor, implementing function calls (especially recursion) are some applications of stacks. | 7) Heaps can be useful for heapsort (best performance), selection algorithms (finding min, finding max, finding median, kth largest/smallest, etc), Graph algorithms. |
| 叠放 | 堆 |
| 1)堆栈是线性数据结构。 | 1)堆是分层数据结构。 |
| 2)堆栈中的元素遵循LIFO或FILO属性。 | 2)堆中的元素遵循堆属性(如上所述)。 |
| 3)Push，Pop，Top是堆栈上唯一允许的操作。 | 3)几乎所有树操作都可以应用于堆。 重整元素，找到最小值，找到最大值是一些示例。 |
| 4)所有提到的操作，push，pop，top，IsEmptyStack()，IsFullStack()，Size()，在堆栈中花费O(1)时间。 | 4)在堆中，插入需要O(log n)时间。 找到min，删除min(在min –堆中)，找到max，删除max(在max –堆中)需要O(1)时间。 |
| 5)堆栈可以通过三种方式实现，即基于简单数组，基于动态数组和基于链表的实现。 | 5)可以使用数组和树来实现堆。 |
| 6)我们可以限制堆栈大小，以使堆栈溢出，发生堆栈下溢情况。 | 6)堆中没有上溢和下溢的情况。 |
| 7)栈的一些应用包括符号的平衡，后缀到后缀的转换，文本编辑器中的撤消序列，实现函数调用(尤其是递归)。 | 7)堆可用于堆排序 (最佳性能)，选择算法(查找最小值，查找最大值，查找中位数，第k个最大/最小等)，图算法。 |
Comment below if you have queries related to above tutorial for stack vs heap.
如果您对以上教程的堆栈与堆有疑问，请在下面评论。
翻译自: https://www.thecrazyprogrammer.com/2018/01/stack-vs-heap.html
数据结构 堆与堆栈