线性数据结构-栈
在JavaScript中，栈（Stack）是一种遵循后进先出（Last In First Out, LIFO）原则的数据结构。这意味着最后进入栈的元素将会是第一个被移除的元素。栈通常被用于限制线性数据的访问顺序，使得数据的插入和删除操作只能在栈的一端进行。
栈的基本操作包括：
- push：将一个元素放入栈顶。
- pop：移除栈顶的元素，并返回被移除的元素。
- peek 或 top：返回栈顶的元素，但不移除它。
- isEmpty：检查栈是否为空。
- size：返回栈中元素的数量。
数组实现栈：
- 数组实现的栈在大多数情况下提供了更好的缓存性能，因为数组元素在内存中是连续存储的，这有助于利用现代处理器的缓存机制。
- 数组的push和pop操作通常是高效的，时间复杂度为O(1)。
- 但是，如果数组需要频繁地扩容（当数组满时），这将涉及到创建新数组并复制旧数组元素的操作，这个操作的时间复杂度为O(n)。不过，这种操作并不经常发生，因为数组扩容通常是成倍增长的，所以在多次push操作后才会触发。
class Stack {constructor() {this.items = []}push(value) {this.items.push(value)}pop() {return this.items.pop()}isEmpty(){return this.items.length === 0}peek() {if(this.isEmpty()){return undefined}return this.items[this.items.length - 1]}size() {return this.items.length}
}
链表实现栈
- 链表实现的栈在动态内存分配方面更加灵活，因为链表节点可以分散在内存中，不需要连续的内存空间。
- 链表的插入和删除操作（对应栈的push和pop）也是时间复杂度为O(1)，但是因为这些操作需要处理指针，可能会有一些额外的开销。
- 链表实现的栈不会遇到数组扩容的问题，因为链表可以根据需要动态地分配节点。
class Node {constructor(val) {this._value = val;this._next = null;}
}class Stack {constructor() {this._top = null;this._size = 0;}isEmpty() {return this._size === 0;}push(value) {const node = new Node(value)if (this.isEmpty()) {this._top = node} node.next = this._topthis._top = nodethis._size++}pop() {if (this.isEmpty()) {return undefined;} this._size--const removedNode = this._topthis._top = this._top.nextreturn removedNode._value}peek() {if (this.isEmpty()) {return undefined}return this._top.value;}getSize() {return this._size;}
}