无锡手机网站,推广软文是什么,洪梅网站仿做,天猫商城官网登录【一】堆与栈
【 1 】简介 栈#xff08;stack#xff09;#xff0c;有些地方称为堆栈#xff0c;是一种容器#xff0c;可存入数据元素、访问元素、删除元素#xff0c;它的特点在于只能允许在容器的一端#xff08;称为栈顶端指标#xff0c;英语#xff1a;topstack有些地方称为堆栈是一种容器可存入数据元素、访问元素、删除元素它的特点在于只能允许在容器的一端称为栈顶端指标英语top进行加入数据英语push和输出数据英语pop的运算。没有了位置概念保证任何时候可以访问、删除的元素都是此前最后存入的那个元素确定了一种默认的访问顺序。
由于栈数据结构只允许在一端进行操作因而按照后进先出LIFO, Last In First Out的原理运作。 1、栈区stack— 由编译器自动分配释放 存放函数的参数值局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区heap — 一般由程序员分配释放 若程序员不释放程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事分配方式倒是类似于链表。
3、全局区静态区static—全局变量和静态变量的存储是放在一块的初始化的全局变量和静态变量在一块区域 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放 。。
4、文字常量区—常量字符串就是放在这里的。 程序结束后由系统释放。
5、程序代码区—存放函数体的二进制代码。
【 2 】堆与栈的区别 堆与栈实际上是操作系统对进程占用的内存空间的两种管理方式主要有如下几种区别 1管理方式不同。栈由操作系统自动分配释放无需我们手动控制堆的申请和释放工作由程序员控制容易产生内存泄漏
2空间大小不同。每个进程拥有的栈大小要远远小于堆大小。理论上进程可申请的堆大小为虚拟内存大小进程栈的大小 64bits 的 Windows 默认 1MB64bits 的 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()
5stack
[1, 2, 3, 4]stack.pop()
4stack.pop()
3stack
[1, 2]
【 四 】堆结构实现
使用 在 Python 中可以使用 heapq 模块来实现堆结构。heapq 提供了一些函数和工具可以方便地进行堆操作。
以下是使用 heapq 模块实现最小堆的示例代码
import heapqclass MinHeap:def __init__(self):self.heap []def insert(self, item):heapq.heappush(self.heap, item)def extract_min(self):if self.is_empty():return Nonereturn heapq.heappop(self.heap)def is_empty(self):return len(self.heap) 0def get_min(self):if self.is_empty():return Nonereturn self.heap[0]
在这个示例中我们定义了一个 MinHeap 类并使用 heapq 模块提供的函数来实现堆操作
__init__(): 初始化一个空堆。insert(item): 向堆中插入元素。extract_min(): 弹出并返回堆中的最小元素。is_empty(): 判断堆是否为空。get_min(): 返回堆中的最小元素但不弹出。
可以使用以下代码测试上述实现的最小堆
h MinHeap()
print(h.is_empty()) # Trueh.insert(5)
h.insert(3)
h.insert(8)
h.insert(2)
print(h.extract_min()) # 2print(h.is_empty()) # False
print(h.extract_min()) # 3
print(h.extract_min()) # 5
print(h.extract_min()) # 8
print(h.is_empty()) # True heapq 模块内部使用了优化的堆操作算法可以高效地进行堆操作。你可以根据需要在代码中添加其他操作比如获取堆顶元素或者删除指定元素以满足具体的需求。
