python 堆与栈

【一】堆与栈

【 1 】简介

栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。

由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

1、栈区（stack）— 由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。

2、堆区（heap） — 一般由程序员分配释放，若程序员不释放，程序结束时可能由OS回收。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。

3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放。。

4、文字常量区—常量字符串就是放在这里的。程序结束后由系统释放。

5、程序代码区—存放函数体的二进制代码。

【 2 】堆与栈的区别

堆与栈实际上是操作系统对进程占用的内存空间的两种管理方式，主要有如下几种区别：
（1）管理方式不同。栈由操作系统自动分配释放，无需我们手动控制；堆的申请和释放工作由程序员控制，容易产生内存泄漏；

（2）空间大小不同。每个进程拥有的栈大小要远远小于堆大小。理论上，进程可申请的堆大小为虚拟内存大小，进程栈的大小 64bits 的 Windows 默认 1MB，64bits 的 Linux 默认 10MB；

（3）生长方向不同。堆的生长方向向上，内存地址由低到高；栈的生长方向向下，内存地址由高到低。

（4）分配方式不同。堆都是动态分配的，没有静态分配的堆。栈有 2 种分配方式：静态分配和动态分配。静态分配是由操作系统完成的，比如局部变量的分配。动态分配由alloca()函数分配，但是栈的动态分配和堆是不同的，它的动态分配是由操作系统进行释放，无需我们手工实现。

（5）分配效率不同。栈由操作系统自动分配，会在硬件层级对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是由C/C++提供的库函数或运算符来完成申请与管理，实现机制较为复杂，频繁的内存申请容易产生内存碎片。显然，堆的效率比栈要低得多。

（6）存放内容不同。栈存放的内容，函数返回地址、相关参数、局部变量和寄存器内容等。当主函数调用另外一个函数的时候，要对当前函数执行断点进行保存，需要使用栈来实现，首先入栈的是主函数下一条语句的地址，即扩展指针寄存器的内容（EIP），然后是当前栈帧的底部地址，即扩展基址指针寄存器内容（EBP），再然后是被调函数的实参等，一般情况下是按照从右向左的顺序入栈，之后是被调函数的局部变量，注意静态变量是存放在数据段或者BSS段，是不入栈的。出栈的顺序正好相反，最终栈顶指向主函数下一条语句的地址，主程序又从该地址开始执行。堆，一般情况堆顶使用一个字节的空间来存放堆的大小，而堆中具体存放内容是由程序员来填充的。

从以上可以看到，堆和栈相比，由于大量malloc()/free()或new/delete的使用，容易造成大量的内存碎片，并且可能引发用户态和核心态的切换，效率较低。栈相比于堆，在程序中应用较为广泛，最常见的是函数的调用过程由栈来实现，函数返回地址、EBP、实参和局部变量都采用栈的方式存放。虽然栈有众多的好处，但是由于和堆相比不是那么灵活，有时候分配大量的内存空间，主要还是用堆。

无论是堆还是栈，在内存使用时都要防止非法越界，越界导致的非法内存访问可能会摧毁程序的堆、栈数据，轻则导致程序运行处于不确定状态，获取不到预期结果，重则导致程序异常崩溃，这些都是我们编程时与内存打交道时应该注意的问题。

【二】什么是堆和栈，它们在哪儿？

栈：
- 栈是一种后进先出（LIFO）的数据结构，类似于一摞盘子或者书籍，你只能在顶部放置新的盘子或者拿走顶部的盘子。
- 在编程语言中，栈通常用于存储函数调用的信息（局部变量、参数、返回地址等）。每次函数调用时，相关的信息被压入栈中；当函数返回时，这些信息被弹出。
- 栈是一块连续的内存区域，其大小在程序启动时就被确定。

堆：
- 堆是一种用于动态分配内存的数据结构，它的内存空间可以动态地增长或缩小。
- 在编程语言中，堆通常用于存储动态分配的数据，比如对象、数组等。由于堆的动态性质，数据的存储位置和大小可以在运行时动态确定。
- 堆并不需要连续的内存区域，它的分配和释放由程序员显式地控制。

总的来说，栈和堆是计算机内存中两种重要的数据结构，它们分别用于不同的目的和场景。栈主要用于存储函数调用信息，而堆主要用于动态分配内存以存储复杂的数据结构。在编程中，了解栈和堆的特点对于有效地管理内存和理解程序的执行过程非常重要。

【三】栈结构实现

使用

栈可以用顺序表实现，也可以用链表实现。

栈的操作

Stack() 创建一个新的空栈
push(item) 添加一个新的元素item到栈顶
pop() 弹出栈顶元素
peek() 返回栈顶元素
is_empty() 判断栈是否为空
size() 返回栈的元素个数

1 class Stack(object):
 2     """栈"""
 3     def __init__(self):
 4          self.items = []
 5 
 6     def is_empty(self):
 7         """判断是否为空"""
 8         return self.items == []
 9 
10     def push(self, item):
11         """加入元素"""
12         self.items.append(item)
13 
14     def pop(self):
15         """弹出元素"""
16         return self.items.pop()
17 
18     def peek(self):
19         """返回栈顶元素"""
20         return self.items[len(self.items)-1]
21 
22     def size(self):
23         """返回栈的大小"""
24         return len(self.items)
25 if __name__ == "__main__":
26     stack = Stack()
27     stack.push("hello")
28     stack.push("world")
29     stack.push("itcast")
30     print stack.size()
31     print stack.peek()
32     print stack.pop()
33     print stack.pop()
34     print stack.pop()

利用python中列表的方法实现数据结构中堆栈的“后进先出”的性质

列表方法使得列表可以很方便的作为一个堆栈来使用，堆栈作为特定的数据结构，最先进入的元素最后一个被释放（后进先出）。

用 append() 方法可以把一个元素添加到堆栈顶。用不指定索引的 pop() 方法可以把一个元素从堆栈顶释放出来。例如：

>>> stack = [1, 2, 3]
>>> stack.append(4)
>>> stack.append(5)
>>> stack
[1, 2, 3, 4, 5]
>>> stack.pop()
5
>>> stack
[1, 2, 3, 4]
>>> stack.pop()
4
>>> stack.pop()
3
>>> stack
[1, 2]

【四】堆结构实现

使用

在 Python 中，可以使用 heapq 模块来实现堆结构。heapq 提供了一些函数和工具，可以方便地进行堆操作。

以下是使用 heapq 模块实现最小堆的示例代码：

import heapq

class MinHeap:
    def __init__(self):
        self.heap = []

    def insert(self, item):
        heapq.heappush(self.heap, item)

    def extract_min(self):
        if self.is_empty():
            return None
        return heapq.heappop(self.heap)

    def is_empty(self):
        return len(self.heap) == 0

    def get_min(self):
        if self.is_empty():
            return None
        return self.heap[0]

在这个示例中，我们定义了一个 MinHeap 类，并使用 heapq 模块提供的函数来实现堆操作：

__init__(): 初始化一个空堆。
insert(item): 向堆中插入元素。
extract_min(): 弹出并返回堆中的最小元素。
is_empty(): 判断堆是否为空。
get_min(): 返回堆中的最小元素，但不弹出。

可以使用以下代码测试上述实现的最小堆：

h = MinHeap()
print(h.is_empty())  # True

h.insert(5)
h.insert(3)
h.insert(8)
h.insert(2)
print(h.extract_min())  # 2

print(h.is_empty())  # False
print(h.extract_min())  # 3
print(h.extract_min())  # 5
print(h.extract_min())  # 8
print(h.is_empty())  # True