栈 #
- 栈的概念
- 顺序栈
- 链栈
栈的概念 #
- 栈是只能在某一端插入和删除的特殊线性表，现实世界中与栈数据结构相似的是一叠盘子，联想摞盘子与取盘子时的顺序关系？
- 栈数据结构的特点：后进先出（Last In First Out – LIFO），即最后进去的数据，最先被拿出来。栈通常不允许随机访问所包含的对象
- 插入和删除操作通常称为入栈（push）和出栈（pop）
如下图所示，如果球桶中的球，每次只能从顶部取出一个，放回时也只能置于顶部，则所有的球构成了一个栈
顺序栈 #
- 顺序栈是栈的顺序存储结构，其利用一组地址连续的存储单元从栈底到栈顶依次存放
- 可以使用指针top来指示栈顶元素在顺序栈中的索引，顺序栈可以是固定长度和动态长度，当栈满时，定长顺序栈会抛出栈满异常，动态顺序栈则会动态申请空闲空间
下图顺序栈结构，使用顺序栈存储整数时，各个元素内存地址顺序存储，与数组存储结构一样，但是仅能从栈顶取出或添加元素
链栈 #
- 栈的另一种存储表示方式是使用链式存储结构，称为链栈
- push操作通过在链表头部插入元素实现，pop操作是通过从头部删除节点实现
如下图所示，因为各个数据之间不再是顺序存储，因为存储数据时需格外加一个指针，来实现下一个数据的访问
小结 #
- 掌握栈的概念
- 了解顺序栈以及链栈
习题 #
- 尽可能多的举出生活中一些后进先出的例子，考虑它们和栈结构的联系
- 说出python中已有的数据结构列表与栈的异同点
- 如果python中的list仅能够使用pop()以及append()操作函数，此时能把列表作为栈来使用吗？
