JavaScript Stack

学习目标

理解栈的基本概念及其遵循的 LIFO（后进先出）原则
掌握使用数组和链表两种方式实现栈的方法
了解栈在实际开发中的应用场景及处理极端情况的策略

栈的概念与操作

栈是一种线性数据结构，它允许在一端（称为栈顶）进行元素的添加和移除操作。主要的操作包括：

Push：向栈顶添加一个元素。
Pop：从栈顶移除并返回一个元素。

栈遵循 LIFO 原则，即最后被加入的元素将最先被移除。这种数据结构广泛应用于函数调用管理、撤销机制以及表达式解析等场景中。

极端情况

栈下溢：尝试对空栈执行 pop 或 peek 操作时发生。
- 处理方法：在执行这些操作前检查栈是否为空。
栈上溢：当栈达到其最大容量时，尝试再执行 push 操作会发生此情况（在固定大小栈的实现中）。
- 处理方法：在执行 push 操作前检查栈是否已满。

使用数组实现栈

在 JavaScript 中，我们可以利用数组来实现栈的所有基本操作。

class Stack {
    constructor() { this.items = []; }

    // 添加元素到栈顶
    push(element) { this.items.push(element); }

    // 移除并返回栈顶元素
    pop() {
        if (this.isEmpty()) {
            return "栈为空";
        }
        return this.items.pop();
    }

    // 返回栈顶元素但不移除
    peek() {
        if (this.isEmpty()) {
            return "栈为空";
        }
        return this.items[this.items.length - 1];
    }

    // 判断栈是否为空
    isEmpty() { return this.items.length === 0; }

    // 获取栈的大小
    size() { return this.items.length; }

    // 打印栈的内容
    print() { console.log(this.items); }
}

// 示例使用
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.peek()); // 输出: 30
console.log(stack.pop());  // 输出: 30
console.log(stack.size()); // 输出: 2
console.log(stack.isEmpty());// 输出: false
stack.print();             // 输出: [ 10, 20 ]

时间复杂度：所有操作（Push, Pop, Peek, isEmpty, size）均为 O(1)，打印栈需要 O(n) 的时间。

使用链表实现栈

另一种实现栈的方式是使用链表，其中我们可以在链表的头部执行所有的栈操作。

// 节点类表示栈中的每个元素
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

// 使用链表实现的栈类
class Stack {
    constructor() {
        this.top = null;
        this.size = 0;
    }

    // 向栈顶添加元素
    push(value) {
        const newNode = new Node(value);
        newNode.next = this.top;
        this.top = newNode;
        this.size++;
    }

    // 从栈顶移除并返回元素
    pop() {
        if (this.isEmpty()) {
            console.log("栈为空！");
            return null;
        }
        const poppedValue = this.top.value;
        this.top = this.top.next;
        this.size--;
        return poppedValue;
    }

    // 返回栈顶元素但不移除
    peek() {
        return this.isEmpty() ? null : this.top.value;
    }

    // 检查栈是否为空
    isEmpty() { return this.size === 0; }

    // 返回栈的大小
    getSize() { return this.size; }

    // 打印栈的元素
    printStack() {
        let current = this.top;
        let stackValues = [];
        while (current) {
            stackValues.push(current.value);
            current = current.next;
        }
        console.log("栈:", stackValues.join(" -> "));
    }
}

// 示例使用
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.printStack();         // 输出: 栈: 30 -> 20 -> 10
console.log("栈顶元素:", stack.peek()); // 输出: 栈顶元素: 30
console.log("弹出元素:", stack.pop());  // 输出: 弹出元素: 30
stack.printStack();         // 输出: 栈: 20 -> 10

时间复杂度：所有操作（Push, Pop, Peek, isEmpty, getSize）均为 O(1)。

思考题

在实际项目中，你认为什么时候更适合使用数组实现的栈？什么时候更适合使用链表实现的栈？
如果你需要设计一个支持无限容量的栈，你会如何处理可能出现的栈上溢问题？
尝试比较数组和链表实现栈的时间复杂度和空间复杂度，并讨论各自的优缺点。

源本科技 | 码上会

学习目标

栈的概念与操作

使用数组实现栈

使用链表实现栈

思考题