四、栈：后进先出（LIFO）

栈是一种受限的线性表，只允许在一端（栈顶）进行插入和删除操作。

4.1 栈的本质
就像一叠盘子：你只能从顶部取盘子，也只能在顶部放盘子。最后放上去的盘子会被最先拿走。

// 栈的操作
// push（入栈）：添加元素到栈顶
// pop（出栈）：移除并返回栈顶元素
// peek（查看栈顶）：返回栈顶元素但不移除
// isEmpty：检查栈是否为空

4.2 栈的实现

// 使用数组实现栈（最简单）
class Stack {
    constructor() {
        this.items = [];
    }

    // 入栈 - O(1)
    push(element) {
        this.items.push(element);
    }

    // 出栈 - O(1)
    pop() {
        if (this.isEmpty()) {
            return null;
        }
        return this.items.pop();
    }

    // 查看栈顶 - O(1)
    peek() {
        if (this.isEmpty()) {
            return null;
        }
        return this.items[this.items.length - 1];
    }

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

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

    // 清空栈
    clear() {
        this.items = [];
    }

    // 打印
    print() {
        console.log(this.items.join(' ← '));
    }
}

// 使用示例
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.print();  // 1 ← 2 ← 3

console.log(stack.pop());  // 3
console.log(stack.peek()); // 2
console.log(stack.size()); // 2

4.3 栈的应用1：括号匹配
这是编译器检查语法错误的基础原理。

function isValidBrackets(str) {
    const stack = new Stack();
    const brackets = {
        '(': ')',
        '[': ']',
        '{': '}'
    };

    for (let i = 0; i < str.length; i++) {
        const char = str[i];

        // 如果是左括号，压入栈
        if (brackets[char]) {
            stack.push(char);
        }
        // 如果是右括号
        else if (char === ')' || char === ']' || char === '}') {
            // 栈为空，说明没有匹配的左括号
            if (stack.isEmpty()) {
                return false;
            }

            // 弹出栈顶的左括号
            const leftBracket = stack.pop();
            // 检查是否匹配
            if (brackets[leftBracket] !== char) {
                return false;
            }
        }
    }

    // 栈为空说明所有括号都匹配
    return stack.isEmpty();
}

// 测试
console.log(isValidBrackets("()"));        // true
console.log(isValidBrackets("()[]{}"));    // true
console.log(isValidBrackets("(]"));        // false
console.log(isValidBrackets("([)]"));      // false
console.log(isValidBrackets("{[]}"));      // true

// 执行过程解析："{[]}"
// 读取 '{' → 压入栈: 栈 = ['{']
// 读取 '[' → 压入栈: 栈 = ['{', '[']
// 读取 ']' → 弹出 '['，匹配！栈 = ['{']
// 读取 '}' → 弹出 '{'，匹配！栈 = []
// 结束，栈为空 → true

4.4 栈的应用2：浏览器历史记录（后退/前进）

class BrowserHistory {
    constructor() {
        this.backStack = new Stack();   // 后退栈
        this.forwardStack = new Stack(); // 前进栈
        this.current = null;
    }

    // 访问新页面
    visit(url) {
        if (this.current !== null) {
            // 将当前页面压入后退栈
            this.backStack.push(this.current);
            // 清空前栈（新访问会覆盖前进记录）
            this.forwardStack.clear();
        }
        this.current = url;
        console.log(`访问: ${url}`);
    }

    // 后退
    back() {
        if (this.backStack.isEmpty()) {
            console.log("无法后退");
            return null;
        }

        // 当前页面压入前进栈
        this.forwardStack.push(this.current);
        // 后退栈弹出页面作为当前页面
        this.current = this.backStack.pop();
        console.log(`后退到: ${this.current}`);
        return this.current;
    }

    // 前进
    forward() {
        if (this.forwardStack.isEmpty()) {
            console.log("无法前进");
            return null;
        }

        // 当前页面压入后退栈
        this.backStack.push(this.current);
        // 前进栈弹出页面作为当前页面
        this.current = this.forwardStack.pop();
        console.log(`前进到: ${this.current}`);
        return this.current;
    }

    // 查看当前页面
    getCurrent() {
        return this.current;
    }
}

// 使用示例
const browser = new BrowserHistory();
browser.visit("google.com");   // 访问: google.com
browser.visit("github.com");   // 访问: github.com
browser.visit("stackoverflow.com");  // 访问: stackoverflow.com

browser.back();     // 后退到: github.com
browser.back();     // 后退到: google.com
browser.forward();  // 前进到: github.com

4.5 栈的应用3：表达式求值（逆波兰表达式）

// 计算逆波兰表达式（后缀表达式）
// 例如：["2", "1", "+", "3", "*"] = (2+1)*3 = 9
function evalRPN(tokens) {
    const stack = new Stack();

    for (const token of tokens) {
        if (isOperator(token)) {
            // 弹出两个操作数
            const b = stack.pop();
            const a = stack.pop();
            const result = calculate(a, b, token);
            stack.push(result);
        } else {
            // 数字直接入栈
            stack.push(Number(token));
        }
    }

    return stack.pop();
}

function isOperator(token) {
    return token === '+' || token === '-' || token === '*' || token === '/';
}

function calculate(a, b, operator) {
    switch (operator) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return Math.trunc(a / b);  // 整数除法
        default: return 0;
    }
}

// 执行过程：["2", "1", "+", "3", "*"]
// 读取 "2" → 栈 = [2]
// 读取 "1" → 栈 = [2, 1]
// 读取 "+" → 弹出1和2，计算2+1=3 → 栈 = [3]
// 读取 "3" → 栈 = [3, 3]
// 读取 "*" → 弹出3和3，计算3*3=9 → 栈 = [9]
// 结果 = 9

console.log(evalRPN(["2", "1", "+", "3", "*"]));  // 9

五、队列：先进先出（FIFO）

队列就像排队买东西：先来的人先服务，后来的人排在后面。
5.1 队列的本质
队列也是一种受限的线性表，插入在一端（队尾），删除在另一端（队首）。

// 队列的操作
// enqueue（入队）：添加元素到队尾
// dequeue（出队）：移除并返回队首元素
// front（查看队首）：返回队首元素但不移除
// isEmpty：检查队列是否为空

5.2 队列的实现

// 使用数组实现队列
class Queue {
    constructor() {
        this.items = [];
    }

    // 入队 - O(1)（均摊）
    enqueue(element) {
        this.items.push(element);
    }

    // 出队 - O(n)（因为需要移动所有元素）
    // 这是数组实现的缺点
    dequeue() {
        if (this.isEmpty()) {
            return null;
        }
        return this.items.shift();  // shift 会移动所有元素
    }

    // 查看队首 - O(1)
    front() {
        if (this.isEmpty()) {
            return null;
        }
        return this.items[0];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }

    print() {
        console.log(this.items.join(' ← '));
    }
}

// 使用对象实现高效队列（所有操作 O(1)）
class EfficientQueue {
    constructor() {
        this.items = {};
        this.frontIndex = 0;
        this.rearIndex = 0;
    }

    enqueue(element) {
        this.items[this.rearIndex] = element;
        this.rearIndex++;
    }

    dequeue() {
        if (this.isEmpty()) {
            return null;
        }
        const element = this.items[this.frontIndex];
        delete this.items[this.frontIndex];
        this.frontIndex++;
        return element;
    }

    front() {
        if (this.isEmpty()) {
            return null;
        }
        return this.items[this.frontIndex];
    }

    isEmpty() {
        return this.frontIndex === this.rearIndex;
    }

    size() {
        return this.rearIndex - this.frontIndex;
    }

    print() {
        const values = [];
        for (let i = this.frontIndex; i < this.rearIndex; i++) {
            values.push(this.items[i]);
        }
        console.log(values.join(' ← '));
    }
}

5.3 队列的应用：任务调度系统

class TaskScheduler {
    constructor() {
        this.queue = new Queue();
    }

    // 添加任务
    addTask(task, priority = false) {
        if (priority) {
            // 优先级高的任务插到队首
            // 简化实现，实际可以用优先队列
            const temp = new Queue();
            temp.enqueue(task);
            while (!this.queue.isEmpty()) {
                temp.enqueue(this.queue.dequeue());
            }
            this.queue = temp;
        } else {
            this.queue.enqueue(task);
        }
        console.log(`添加任务: ${task.name}`);
    }

    // 执行任务
    run() {
        while (!this.queue.isEmpty()) {
            const task = this.queue.dequeue();
            console.log(`执行: ${task.name}`);
            task.execute();
        }
    }
}

// 使用示例
const scheduler = new TaskScheduler();
scheduler.addTask({ name: "任务1", execute: () => console.log("  完成1") });
scheduler.addTask({ name: "任务2", execute: () => console.log("  完成2") });
scheduler.addTask({ name: "紧急任务", execute: () => console.log("  完成紧急") }, true);

scheduler.run();
// 输出：
// 添加任务: 任务1
// 添加任务: 任务2
// 添加任务: 紧急任务
// 执行: 紧急任务
//   完成紧急
// 执行: 任务1
//   完成1
// 执行: 任务2
//   完成2

5.4 队列的应用：广度优先搜索（BFS）
广度优先搜索是图和树的遍历算法，核心就是使用队列。

// 使用 BFS 查找图中的最短路径
class Graph {
    constructor() {
        this.adjacencyList = new Map();  // 邻接表
    }

    // 添加顶点
    addVertex(vertex) {
        if (!this.adjacencyList.has(vertex)) {
            this.adjacencyList.set(vertex, []);
        }
    }

    // 添加边（无向图）
    addEdge(v1, v2) {
        this.adjacencyList.get(v1).push(v2);
        this.adjacencyList.get(v2).push(v1);
    }

    // BFS 查找最短路径
    shortestPath(start, end) {
        const queue = new EfficientQueue();
        const visited = new Set();
        const parent = new Map();  // 记录路径

        queue.enqueue(start);
        visited.add(start);
        parent.set(start, null);

        while (!queue.isEmpty()) {
            const current = queue.dequeue();

            // 找到目标
            if (current === end) {
                // 重建路径
                const path = [];
                let node = end;
                while (node !== null) {
                    path.unshift(node);
                    node = parent.get(node);
                }
                return path;
            }

            // 遍历邻居
            const neighbors = this.adjacencyList.get(current);
            for (const neighbor of neighbors) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    parent.set(neighbor, current);
                    queue.enqueue(neighbor);
                }
            }
        }

        return null;  // 没有路径
    }
}

// 创建图
const graph = new Graph();
['A', 'B', 'C', 'D', 'E', 'F'].forEach(v => graph.addVertex(v));

graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'E');
graph.addEdge('D', 'F');
graph.addEdge('E', 'F');

console.log(graph.shortestPath('A', 'F'));  // ['A', 'B', 'D', 'F'] 或 ['A', 'C', 'E', 'F']（取决于遍历顺序）

来源：
https://xcfsr.cn/