数据结构堆与堆栈_堆栈vs堆–数据结构中堆栈和堆的区别

野性酷女 2022-12-07 13:27 226阅读 0赞

![5c9ff23550cdc9a4737e20398cb0e9ae.png][]

数据结构 堆与堆栈

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.

**堆栈溢出：**当我们想将一个元素压入一个**完整的堆栈(即等于堆栈大小的堆栈元素)时，**这种情况称为堆栈溢出。

![Stack Data Structure][]

**Also Read: [Difference Between Stack and Queue][]**

**另请阅读： [堆栈和队列之间的区别][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 Min Heap

二进制最小堆

![Binary Max Heap][]

Binary Max Heap

二进制最大堆

## 堆栈与堆–堆栈与堆之间的区别 **(**Stack vs Heap – Difference between Stack and Heap**)** ##

<table> 
 <tbody> 
  <tr> 
   <td><strong>Stack</strong></td> 
   <td><strong>Heap</strong></td> 
  </tr> 
  <tr> 
   <td>1) Stack is a linear data structure.</td> 
   <td>1) Heap is a hierarchical data structure.</td> 
  </tr> 
  <tr> 
   <td>2) Elements in stack follow LIFO or FILO property.</td> 
   <td>2) Elements in heap follow heap property (mentioned above).</td> 
  </tr> 
  <tr> 
   <td>3) Push, Pop, Top are the only allowed operations on the stack.</td> 
   <td>3) Almost all tree operations can be applied on heaps. Heapifying an element, find minimum, find maximum are some examples.</td> 
  </tr> 
  <tr> 
   <td>4) All mentioned operations, push, pop, top, IsEmptyStack(), IsFullStack(), Size(), takes O(1) time in stack.</td> 
   <td>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.</td> 
  </tr> 
  <tr> 
   <td>5) Stack can be implemented in 3 ways that, simple array based, dynamic array based and Linked list based implementation.</td> 
   <td>5) Heap can be implemented using arrays, and trees.</td> 
  </tr> 
  <tr> 
   <td>6) We can limit stack size, so that stack overflow, stack underflow conditions will occur.</td> 
   <td>6) There is no case of overflow and underflow in heap.</td> 
  </tr> 
  <tr> 
   <td>7) Balancing of symbols, infix – to – postfix conversions, undo sequence in a text editor, implementing function calls (especially recursion) are some applications of stacks.</td> 
   <td>7) Heaps can be useful for <a href="https://www.thecrazyprogrammer.com/2013/12/c-program-for-sorting-array-using-heap-sort.html" rel="nofollow">heapsort </a>(best performance), selection algorithms (finding min, finding max, finding median, kth largest/smallest, etc), Graph algorithms.</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td> <strong>叠放</strong> </td> 
   <td> <strong>堆</strong> </td> 
  </tr> 
  <tr> 
   <td> 1)堆栈是线性数据结构。 </td> 
   <td> 1)堆是分层数据结构。 </td> 
  </tr> 
  <tr> 
   <td> 2)堆栈中的元素遵循LIFO或FILO属性。 </td> 
   <td> 2)堆中的元素遵循堆属性(如上所述)。 </td> 
  </tr> 
  <tr> 
   <td> 3)Push，Pop，Top是堆栈上唯一允许的操作。 </td> 
   <td> 3)几乎所有树操作都可以应用于堆。 重整元素，找到最小值，找到最大值是一些示例。 </td> 
  </tr> 
  <tr> 
   <td> 4)所有提到的操作，push，pop，top，IsEmptyStack()，IsFullStack()，Size()，在堆栈中花费O(1)时间。 </td> 
   <td> 4)在堆中，插入需要O(log n)时间。 找到min，删除min(在min –堆中)，找到max，删除max(在max –堆中)需要O(1)时间。 </td> 
  </tr> 
  <tr> 
   <td> 5)堆栈可以通过三种方式实现，即基于简单数组，基于动态数组和基于链表的实现。 </td> 
   <td> 5)可以使用数组和树来实现堆。 </td> 
  </tr> 
  <tr> 
   <td> 6)我们可以限制堆栈大小，以使堆栈溢出，发生堆栈下溢情况。 </td> 
   <td> 6)堆中没有上溢和下溢的情况。 </td> 
  </tr> 
  <tr> 
   <td> 7)栈的一些应用包括符号的平衡，后缀到后缀的转换，文本编辑器中的撤消序列，实现函数调用(尤其是递归)。 </td> 
   <td> 7)堆可用于堆<a href="https://www.thecrazyprogrammer.com/2013/12/c-program-for-sorting-array-using-heap-sort.html" rel="nofollow">排序</a> (最佳性能)，选择算法(查找最小值，查找最大值，查找中位数，第k个最大/最小等)，图算法。 </td> 
  </tr> 
 </tbody> 
</table>

Comment below if you have queries related to above tutorial for stack vs heap.

如果您对以上教程的堆栈与堆有疑问，请在下面评论。

> 翻译自: [https://www.thecrazyprogrammer.com/2018/01/stack-vs-heap.html][https_www.thecrazyprogrammer.com_2018_01_stack-vs-heap.html]

数据结构 堆与堆栈

[5c9ff23550cdc9a4737e20398cb0e9ae.png]: /images/20221123/a6733acecae74251bcc7b81476b645f4.png
[Stack Data Structure]: /images/20221123/4a418dbff9c24ebc82f8e535994805e8.png
[Difference Between Stack and Queue]: https://www.thecrazyprogrammer.com/2016/05/difference-between-stack-and-queue.html
[Binary Min Heap]: /images/20221123/c59bbeca2f3d4dc38ea8440a810de5f8.png
[Binary Max Heap]: /images/20221123/e2172fbf09e94c22a27f29c52238bb04.png
[https_www.thecrazyprogrammer.com_2018_01_stack-vs-heap.html]: https://www.thecrazyprogrammer.com/2018/01/stack-vs-heap.html