189 8069 5689
堆栈是一种执行“后进先出”算法的数据结构。
创新互联坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都做网站、网站制作、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的壶关网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！
设想有一个直径不大、一端开口一端封闭的竹筒。有若干个写有编号的小球，小球的直径比竹筒的直径略小。现在把不同编号的小球放到
竹筒里面，可以发现一种规律：先放进去的小球只能后拿出来，反之，后放进去的小球能够先拿出来。所以“先进后出”就是这种结构的
特点。
堆栈是计算机中最常用的一种数据结构，比如函数的调用在计算机中是用堆栈实现的。 堆栈可以用数组存储，也可以用以后会介绍的链
表存储。
堆栈就是这样一种数据结构。它是在内存中开辟一个存储区域，数据一个一个顺序地存入（也就是“压入——push”）这个区域之中。
有一个地址指针总指向最后一个压入堆栈的数据所在的数据单元，存放这个地址指针的寄存器就叫做堆栈指示器。开始放入数据的单元叫
做“栈底”。数据一个一个地存入，这个过程叫做“压栈”。在压栈的过程中，每有一个数据压入堆栈，就放在和前一个单元相连的后面
一个单元中，堆栈指示器中的地址自动加1。读取这些数据时，按照堆栈指示器中的地址读取数据，堆栈指示器中的地址数自动减 1。这
个过程叫做“弹出pop”。如此就实现了后进先出的原则。
推荐学习《python教程》。
堆（Heap）与栈（Stack）是开发人员必须面对的两个概念，在理解这两个概念时，需要放到具体的场景下，因为不同场景下，堆与栈代表不同的含义。一般情况下，有两层含义：
（1）程序内存布局场景下，堆与栈表示的是两种内存管理方式；
（2）数据结构场景下，堆与栈表示两种常用的数据结构。
相关推荐：《Python教程》
堆与栈实际上是操作系统对进程占用的内存空间的两种管理方式，主要有如下几种区别：
（1）管理方式不同。栈由操作系统自动分配释放，无需我们手动控制；堆的申请和释放工作由程序员控制，容易产生内存泄漏；
（2）空间大小不同。每个进程拥有的栈的大小要远远小于堆的大小。理论上，程序员可申请的堆大小为虚拟内存的大小，进程栈的大小 64bits 的 Windows 默认 1MB，64bits 的 Linux 默认 10MB；
（3）生长方向不同。堆的生长方向向上，内存地址由低到高；栈的生长方向向下，内存地址由高到低。
（4）分配方式不同。堆都是动态分配的，没有静态分配的堆。栈有2种分配方式：静态分配和动态分配。静态分配是由操作系统完成的，比如局部变量的分配。动态分配由alloca函数进行分配，但是栈的动态分配和堆是不同的，他的动态分配是由操作系统进行释放，无需我们手工实现。
（5）分配效率不同。栈由操作系统自动分配，会在硬件层级对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是由C/C++提供的库函数或运算符来完成申请与管理，实现机制较为复杂，频繁的内存申请容易产生内存碎片。显然，堆的效率比栈要低得多。
（6）存放内容不同。栈存放的内容，函数返回地址、相关参数、局部变量和寄存器内容等。当主函数调用另外一个函数的时候，要对当前函数执行断点进行保存，需要使用栈来实现，首先入栈的是主函数下一条语句的地址，即扩展指针寄存器的内容（EIP），然后是当前栈帧的底部地址，即扩展基址指针寄存器内容（EBP），再然后是被调函数的实参等，一般情况下是按照从右向左的顺序入栈，之后是被调函数的局部变量，注意静态变量是存放在数据段或者BSS段，是不入栈的。出栈的顺序正好相反，最终栈顶指向主函数下一条语句的地址，主程序又从该地址开始执行。堆，一般情况堆顶使用一个字节的空间来存放堆的大小，而堆中具体存放内容是由程序员来填充的。
从以上可以看到，堆和栈相比，由于大量malloc()/free()或new/delete的使用，容易造成大量的内存碎片，并且可能引发用户态和核心态的切换，效率较低。栈相比于堆，在程序中应用较为广泛，最常见的是函数的调用过程由栈来实现，函数返回地址、EBP、实参和局部变量都采用栈的方式存放。虽然栈有众多的好处，但是由于和堆相比不是那么灵活，有时候分配大量的内存空间，主要还是用堆。
无论是堆还是栈，在内存使用时都要防止非法越界，越界导致的非法内存访问可能会摧毁程序的堆、栈数据，轻则导致程序运行处于不确定状态，获取不到预期结果，重则导致程序异常崩溃，这些都是我们编程时与内存打交道时应该注意的问题。
可以这么说。实际上参数是存放在属于函数的栈里面。函数运行完成，释放占用的栈。
仅供参考
# coding=utf8
'''
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。
在该栈中，调用min、push及pop的时间复杂度都是O(1)。
'''
class Stack():
def __init__(self):
self.main_stack = []
# 辅助栈，每次次最小的元素压入辅助栈
self.assist_stack = []
# 记录栈中的最小元素
self._min = None
def min(self):
return self._min
def push(self, data):
self.main_stack.append(data)
if self._min is None:
self._min = data
else:
if data self._min:
self._min = data
# 将最小的元素压入辅助栈
self.assist_stack.append(self._min)
def pop(self):
if len(self.main_stack) == 0:
raise Exception('no data')
elif len(self.main_stack) == 1:
self.assist_stack.pop()
self._min = None
return self.main_stack.pop()
else:
self.assist_stack.pop()
self._min = self.assist_stack[-1]
return self.main_stack.pop()
if __name__ == '__main__':
s = Stack()
s.push(3)
s.push(4)
s.push(2)
s.push(1)
print s.min()
s.pop()
s.pop()
print s.min()
s.pop()
print s.min()
s.pop()
print s.min()
s.pop()
众所周知，Python是一门面向对象的语言，在Python无论是数值、字符串、函数亦或是类型、类，都是对象。
对象是在 堆 上分配的结构，我们定义的所有变量、函数等，都存储于堆内存，而变量名、函数名则是一个存储于 栈 中、指向堆中具体结构的引用。
要想深入学习Python，首先需要知道Python对象的定义。
我们通常说的Python都是指CPython，底层由C语言实现，源码地址： cpython [GitHub]
Python对象的定义位于 Include/object.h ，是一个名为 PyObject 的结构体：
Python中的所有对象都继承自PyObejct，PyObject包含一个用于垃圾回收的双向链表，一个引用计数变量 ob_refcnt 和 一个类型对象指针 ob_type
从PyObejct的注释中，我们可以看到这样一句：每个指向 可变大小Python对象 的指针也可以转换为 PyVarObject* （可变大小的Python对象会在下文中解释）。 PyVarObejct 就是在PyObject的基础上多了一个 ob_size 字段，用于存储元素个数：
在PyObject结构中，还有一个类型对象指针 ob_type ，用于表示Python对象是什么类型，定义Python对象类型的是一个 PyTypeObject 接口体
实际定义是位于 Include/cpython/object.h 的 _typeobject ：
在这个类型对象中，不仅包含了对象的类型，还包含了如分配内存大小、对象标准操作等信息，主要分为：
以Python中的 int类型 为例，int类型对象的定义如下：
从PyObject的定义中我们知道，每个对象的 ob_type 都要指向一个具体的类型对象，比如一个数值型对象 100 ，它的ob_type会指向 int类型对象PyLong_Type 。
PyTypeObject结构体第一行是一个PyObject_VAR_HEAD宏，查看宏定义可知PyTypeObject是一个变长对象
也就是说，归根结底 类型对象也是一个对象 ，也有ob_type属性，那 PyLong_Type 的 ob_type 是什么呢？
回到PyLong_Type的定义，第一行 PyVarObject_HEAD_INIT(PyType_Type, 0) ，查看对应的宏定义
由以上关系可以知道， PyVarObject_HEAD_INIT(PyType_Type, 0) = { { _PyObject_EXTRA_INIT 1, PyType_Type } 0} ，将其代入 PyObject_VAR_HEAD ，得到一个变长对象：
这样看就很明确了，PyLong_Type的类型就是PyType_Typ，同理可知， Python类型对象的类型就是PyType_Type ，而 PyType_Type对象的类型是它本身
从上述内容中，我们知道了对象和对象类型的定义，那么根据定义，对象可以有以下两种分类
Python对象定义有 PyObject 和 PyVarObject ，因此，根据对象大小是否可变的区别，Python对象可以划分为 可变对象（变长对象） 和 不可变对象（定长对象）
原本的对象a大小并没有改变，只是s引用的对象改变了。这里的对象a、对象b就是定长对象
可以看到，变量l仍然指向对象a，只是对象a的内容发生了改变，数据量变大了。这里的对象a就是变长对象
由于存在以上特性，所以使用这两种对象还会带来一种区别：
声明 s2 = s ，修改s的值： s = 'new string' ，s2的值不会一起改变，因为只是s指向了一个新的对象，s2指向的旧对象的值并没有发生改变
声明 l2 = l ，修改l的值： l.append(6) ，此时l2的值会一起改变，因为l和l2指向的是同一个对象，而该对象的内容被l修改了
此外，对于 字符串 对象，Python还有一套内存复用机制，如果两个字符串变量值相同，那它们将共用同一个对象：
对于 数值型 对象，Python会默认创建0~2 8 以内的整数对象，也就是 0 ~ 256 之间的数值对象是共用的：
按照Python数据类型，对象可分为以下几类：
Python创建对象有两种方式，泛型API和和类型相关的API
这类API通常以 PyObject_xxx 的形式命名，可以应用在任意Python对象上，如:
使用 PyObjecg_New 创建一个数值型对象：
这类API通常只能作用于一种类型的对象上，如：
使用 PyLong_FromLong 创建一个数值型对象：
在我们使用Python声明变量的时候，并不需要为变量指派类型，在给变量赋值的时候，可以赋值任意类型数据，如：
从Python对象的定义我们已经可以知晓造成这个特点的原因了，Python创建对象时，会分配内存进行初始化，然后Python内部通过 PyObject* 变量来维护这个对象，所以在Python内部各函数直接传递的都是一种泛型指针 PyObject* ，这个指针所指向的对象类型是不固定的，只能通过所指对象的 ob_type 属性动态进行判断，而Python正是通过 ob_type 实现了多态机制
Python在管理维护对象时，通过引用计数来判断内存中的对象是否需要被销毁，Python中所有事物都是对象，所有对象都有引用计数 ob_refcnt 。
当一个对象的引用计数减少到0之后，Python将会释放该对象所占用的内存和系统资源。
但这并不意味着最终一定会释放内存空间，因为频繁申请释放内存会大大降低Python的执行效率，因此Python中采用了内存对象池的技术，是的对象释放的空间会还给内存池，而不是直接释放，后续需要申请空间时，优先从内存对象池中获取。