线性数据结构-栈

在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._top
        this._top = node
        this._size++
    }

    pop() {
        if (this.isEmpty()) {
            return undefined;
        }  
        this._size--
        const removedNode = this._top
        this._top = this._top.next
        return removedNode._value
    }

    peek() {
        if (this.isEmpty()) {
          return undefined
        }
        return this._top.value;
    }

    getSize() {
        return this._size;
    }
}