算法图解-终极版-终极之栈
分类:
文章
•
2025-05-04 21:49:34
- stack (array)
栈有两种最基本的表示方法， 上图为数组表示， 是一种静态的表达方法， 好比手枪的弹仓中压入子弹， 是一种LIFO的数据结构， last in first out。
如上图，栈最小存储为0为空栈， 最大存储30个元素，栈满后无法继续存储， 只能清空后继续存储后pop后继续。所以说只能用在杀伤力小的时候， 比如手枪在近距离攻击时， 轻便， 准确， 人在作战时移动灵活。那么， 数组存储时， 如果确定元素数量， 或者数量不大时， 可以节省内存空间， 方便读取数据， 直接可以用下标， 如果元素有序， 可以用二分法查找， 达到log（n） 的 的时间复杂度， 所以说， 数组有数组的好处。
- stack(linked list)
当然， 栈最常用的还是链表的存储方式， 这样用起来更加灵活，应为大小是不固定的， 所以是动态的存储结构， 只要计算机内存足够的大， 可以无限的扩展， 而且是使用多少数据， 加入多少节点， 这样的存储效率更高。
就好比， 玩吃鸡时拿到的无限发子弹的枪， 那叫cool.
当然链表也不是完美的， 首先， 链表不能用下标引用， 这样就就定了，无法用二分法查找， 即使元素已经排好序， 但是不能用下标， 无法查找。这样也导致链表查找算数困难， T = O(n). 不像数组O（1）。
- 基本操作
关于栈的操作， 不同教科书， 用法不一， 但基本上通用的有：
push(5), 把5压入栈中
pop(), 把栈顶的元素弹出。
clear(), empty()都一样， 清空所有数据元素。
当然， 这些叫法， 只是你在建立栈的数据结构时用的名字， 也叫ADT， abstract data type, 具体应用时叫ADO， abstract data object.
不是说， 这些函数可以直接使用的， 比如需要用C语言建立数据类型， 才能使用。
而对于用户，push(5),pop()， clear()可以直接使用， 因为程序员在c文件中已经建立好了， 用户看到的只是使用界面（C头文件）， 也不需要了解细节。
而高级语言， python, 用到的pop, clear， append这些函数， 就是栈的应用。
总之栈的应用太多， 尤其是其他高级的算法， 比如深度优先， 图的算法等都会用到栈。
