栈和堆的数据结构

总结

都是计算机科学中常用的数据结构

栈（stack）

栈是一种先进后出（LIFO）的数据结构

堆（heap）

栈是一种先进后出（LIFO）的数据结构，类似于一个弹夹或书堆，只能从栈顶插入和删除元素。当你把东西放在栈里时，它们就被放在最顶端，取出时也只能从最顶端开始取出。栈通常用于实现程序调用（函数调用）和表达式求值等操作。

堆是一种动态分配内存的数据结构，也称为动态存储器或自由存储器。堆是由程序员手动申请并管理的内存区域，可以用于存储各种类型的数据。堆通常用于动态分配内存，如在运行时创建一个新的对象或数据结构时。

在许多编程语言中，栈和堆都是程序中内存的一部分。栈是静态内存，大小在编译时就已经确定，而堆是动态内存，大小在运行时确定。由于栈的空间有限，它更适合存储较小的数据结构，而堆则更适合存储较大的数据结构，如数组和对象等。

栈（stack）是一种常见的数据结构，其特点是后进先出（LIFO，Last In First Out），类似于把数据放在一摞书的顶端，取出数据时只能从顶端一个个取出。

栈可以用数组或链表实现，其主要操作包括：

1. push：将一个元素压入栈顶，即在栈顶插入一个元素。
2. pop：将栈顶元素弹出，即删除栈顶元素。
3. top/peek：返回栈顶元素，但不弹出。
4. empty：判断栈是否为空。
5. size：返回栈中元素的数量。

堆（heap）是一种常见的数据结构，是一棵树形结构，其中每个节点都有一个值，且每个节点的值都比其子节点的值大（或小），这样的堆被称为大根堆（或小根堆）。

堆常常用于实现优先队列等数据结构，其主要操作包括：

1. insert：将一个元素插入堆中，通常是将元素插入堆的最后一个位置，然后根据堆的性质将其向上调整。
2. extract-max（或 extract-min）：删除堆中的最大（或最小）元素，并返回该元素。
3. delete：删除堆中的一个元素，通常是先将其标记为删除，然后再向上或向下调整堆，使其满足堆的性质。
4. heapify：将一个无序的序列转化为堆的形式，通常是从最后一个非叶子节点开始，依次向下调整堆。
5. peek-max（或 peek-min）：返回堆中的最大（或最小）元素，但不删除它。

下面是一个用数组实现的简单大根堆的示例代码：