Stack | 栈

栈是一种逻辑结构，区别于 数组和链表(在内存中实实在在存在的物理结构)，看一张表

如果把物质层面的人体比作数据存储的物理结构，那么精神层面的人格则是数据存储的 逻辑结构。逻辑结构是抽象的概念，它依赖于 物理结构 而存在。

分类	线性结构	非线性结构
逻辑结构	eg: 顺序表、栈、队列	eg: 树、图

分类	顺序存储	链式存储结构
物理结构	eg: 数组	eg: 链表

什么是栈

一个装兵乓球的圆筒，一端是封闭的，另外一端向里填球

另外一端向外取出

所以上述简单的一个场景就是一个栈的实际应用

栈是一种线性结构，特点是: 先进后出 (first in last out)FILO, 最早进入的元素在最底下, 就是栈底(bottom), 最后进入的元素叫做栈顶(top)

这种数据结构可以用链表来实现，也可以使用数组来实现

关于栈的操作

入栈和出栈

数组举个例子

const stack = []
// [1,2,3,4,5]

// 入栈
stack.push() // stack.push(6)
// [1,2,3,4,5,6]

// 出栈
stack.pop() // stack.pop()
// [1,2,3,4,5]

入栈和出栈只会影响到最后一个元素，不涉及其他元素 的整体移动，所以无论是以数组还是以链表实现，入栈、出栈的时间复杂度 都是O(1)。

栈的应用

栈的输出顺序和输入顺序相反，所以栈通常用于对“历史”的回溯，也就是逆流而上追溯“历史”。 例如实现递归的逻辑，就可以用栈来代替，因为栈可以回溯方法的调用链。

或者例如撤销重做，在双栈中，或者是面包屑导航，也可以算是一个栈的应用

参考

漫画算法：小灰的算法之旅