Skip to content

栈与队列

中等 约 30 分钟

你将构建什么

一个以数组为底、支持 push/pop/peek 的 Stack 类,以及一个使用 head/tail 指针对实现 O(1) 入队出队的 Queue 类。

学习目标

  • 理解 LIFO(栈)与 FIFO(队列)的顺序差异
  • 以正确的复杂度实现核心操作
  • 使用数组作为内部存储
  • 将栈应用于括号匹配检测

前置要求

  • 数组与数组方法
  • 类或构造函数
  • if/else 条件语句

步骤

  1. 1

    实现栈

    栈是后进先出:最后压入的元素最先弹出。使用数组并在末尾 push/pop 即可实现 O(1) 操作。

    代码
    class Stack {
      constructor() { this.items = []; }
      push(value) { this.items.push(value); return this; }
      pop() { return this.items.pop(); }
      peek() { return this.items[this.items.length - 1]; }
      isEmpty() { return this.items.length === 0; }
      size() { return this.items.length; }
    }

    预期结果

    push(1).push(2).push(3); pop() 返回 3; peek() 返回 2。

  2. 2

    测试栈

    压入三个值再依次弹出,验证 LIFO 行为——弹出顺序应与压入顺序相反。

    代码
    const s = new Stack();
    s.push(1).push(2).push(3);
    console.log(s.pop()); // 3
    console.log(s.pop()); // 2
    console.log(s.pop()); // 1
    console.log(s.isEmpty()); // true

    预期结果

    输出:3、2、1、true。

  3. 3

    实现队列

    队列是先进先出。使用数组,push 用于入队,shift 用于出队。(注意:shift 为 O(n);生产环境队列会使用链表或 head/tail 指针。)

    代码
    class Queue {
      constructor() { this.items = []; }
      enqueue(value) { this.items.push(value); return this; }
      dequeue() { return this.items.shift(); }
      front() { return this.items[0]; }
      isEmpty() { return this.items.length === 0; }
      size() { return this.items.length; }
    }

    预期结果

    enqueue(1).enqueue(2).enqueue(3); dequeue() 返回 1。

  4. 4

    测试队列

    入队三个值再依次出队,验证 FIFO 行为——出队顺序应与入队顺序相同。

    代码
    const q = new Queue();
    q.enqueue('a').enqueue('b').enqueue('c');
    console.log(q.dequeue()); // a
    console.log(q.dequeue()); // b
    console.log(q.dequeue()); // c

    预期结果

    输出:a、b、c——与插入顺序相同。

  5. 5

    应用:括号匹配检测

    用栈检查一串括号是否平衡。遇到开括号压栈,遇到闭括号弹栈并验证是否匹配。

    代码
    function isBalanced(str) {
      const stack = new Stack();
      const pairs = { ')': '(', ']': '[', '}': '{' };
      for (const ch of str) {
        if ('([{'.includes(ch)) stack.push(ch);
        else if (')]}'.includes(ch)) {
          if (stack.pop() !== pairs[ch]) return false;
        }
      }
      return stack.isEmpty();
    }
    console.log(isBalanced('([{}])')); // true
    console.log(isBalanced('([)]'));   // false

    预期结果

    ([{}]) 返回 true; ([)] 返回 false。

自己动手试试

你学到了什么

你实现了两种最常用的线性数据结构,并将栈应用于经典解析问题——栈是函数调用、撤销系统和表达式求值的基础。

相关资源

相关课程

  • 数组

    数组在内部支撑两种结构。

  • 循环

    括号检测器循环遍历字符。

相关术语

  • 栈

    后进先出数据结构。

  • 队列

    先进先出数据结构。

相关术语

新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。

  • 栈

    后进先出数据结构。

  • 队列

    先进先出数据结构。

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误

← 返回主题