EnlightenCode

Appearance

栈与队列完全指南 🚀 ​

一、栈(Stack)的世界 ​

1. 什么是栈？ ​

想象一叠盘子 🍽️，你只能从顶部放入或取出盘子。这就是栈的工作原理！

  • 后进先出(LIFO: Last In First Out)
  • 只能在一端(栈顶)进行操作

2. 栈在前端中的应用 ​

  • 浏览器的前进/后退功能
  • JavaScript的调用栈
  • 括号匹配验证
  • 撤销/重做功能
  • 路由历史记录

3. 栈的实现 ​

js
class Stack {
    #items = [];  // 私有属性，外部无法直接访问
    
    // 入栈
    push(element) {
        this.#items.push(element);
    }
    
    // 出栈
    pop() {
        return this.#items.pop();
    }
    
    // 查看栈顶元素
    peek() {
        return this.#items[this.#items.length - 1];
    }
    
    // 检查栈是否为空
    isEmpty() {
        return this.#items.length === 0;
    }
    
    // 获取栈的大小
    size() {
        return this.#items.length;
    }
    
    // 清空栈
    clear() {
        this.#items = [];
    }
}

4. 实战应用示例 ​

括号匹配检查器 🎯 ​

js
function isValidBrackets(str) {
    const stack = new Stack();
    const brackets = {
        '(': ')',
        '[': ']',
        '{': '}'
    };
    
    for (const char of str) {
        if (brackets[char]) {
            // 遇到左括号，入栈
            stack.push(char);
        } else {
            // 遇到右括号，检查是否匹配
            const last = stack.pop();
            if (brackets[last] !== char) {
                return false;
            }
        }
    }
    
    return stack.isEmpty();
}

// 使用示例
console.log(isValidBrackets('({[]})')); // true
console.log(isValidBrackets('({[})')); // false

二、队列(Queue)的奥秘 ​

1. 什么是队列？ ​

就像排队买奶茶 🧋，先来的人先买，后来的人要排在队尾。这就是队列！

  • 先进先出(FIFO: First In First Out)
  • 一端进(队尾)，另一端出(队头)

2. 队列在前端中的应用 ​

  • 事件循环(Event Loop)
  • 异步任务队列
  • 打印任务队列
  • 消息队列
  • 请求队列管理

3. 队列的实现 ​

js
class Queue {
    #items = {};  // 使用对象实现，性能更好
    #firstCount = 0;  // 队头指针
    #lastCount = 0;   // 队尾指针
    
    // 入队
    enqueue(element) {
        this.#items[this.#lastCount] = element;
        this.#lastCount++;
    }
    
    // 出队
    dequeue() {
        if (this.isEmpty()) {
            return undefined;
        }
        const result = this.#items[this.#firstCount];
        delete this.#items[this.#firstCount];
        this.#firstCount++;
        return result;
    }
    
    // 查看队头元素
    front() {
        return this.#items[this.#firstCount];
    }
    
    // 检查队列是否为空
    isEmpty() {
        return this.size() === 0;
    }
    
    // 获取队列大小
    size() {
        return this.#lastCount - this.#firstCount;
    }
    
    // 清空队列
    clear() {
        this.#items = {};
        this.#firstCount = 0;
        this.#lastCount = 0;
    }
}

4. 实战应用示例 ​

请求队列管理器 🔄 ​

js
class RequestQueue {
    constructor(maxConcurrent = 2) {
        this.queue = new Queue();
        this.maxConcurrent = maxConcurrent;
        this.runningCount = 0;
    }
    
    async addRequest(requestFn) {
        if (this.runningCount < this.maxConcurrent) {
            // 直接执行请求
            await this.executeRequest(requestFn);
        } else {
            // 加入队列等待
            this.queue.enqueue(requestFn);
        }
    }
    
    async executeRequest(requestFn) {
        this.runningCount++;
        try {
            await requestFn();
        } finally {
            this.runningCount--;
            // 检查队列中是否有等待的请求
            if (!this.queue.isEmpty()) {
                const nextRequest = this.queue.dequeue();
                this.executeRequest(nextRequest);
            }
        }
    }
}

// 使用示例
const requestQueue = new RequestQueue(2);
requestQueue.addRequest(() => fetch('api/data1'));
requestQueue.addRequest(() => fetch('api/data2'));
requestQueue.addRequest(() => fetch('api/data3')); // 会进入队列等待

三、性能对比 📊 ​

操作栈队列(数组实现)队列(对象实现)
插入O(1)O(1)O(1)
删除O(1)O(n)O(1)
查看顶部元素O(1)O(1)O(1)
空间占用中等较大较小

四、最佳实践建议 💡 ​

  1. 选择合适的实现方式

    • 小数据量：数组实现简单直观
    • 大数据量：对象实现性能更好

  2. 注意边界情况

    • 空栈/空队列的处理
    • 容量限制的考虑
    • 类型检查

  3. 合理使用TypeScript

    typescript
    class Stack<T> {
    private items: T[] = [];
    // ... 其他方法
}

五、常见面试题 📝 ​

  1. 用栈实现队列
  2. 用队列实现栈
  3. 实现一个最小栈
  4. 如何用栈实现浏览器的前进后退功能？

六、扩展阅读 📚 ​