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