Javascript数据结构之栈和队列详解

本文将详细讲解Javascript中常用的数据结构之一，栈和队列。

栈

什么是栈？

栈是一种“后进先出（LIFO）”的数据结构，也就是说最后进入栈的元素被最先移除。栈一般用数组或链表实现。

栈的操作

常用的栈操作有：

• push: 将一个元素添加到栈的顶部。
• pop: 从栈的顶部移除一个元素，并返回它。
• peek: 返回栈顶部的元素，但不删除它。

代码示例

下面是一个用数组实现栈的示例代码：

class Stack {
  constructor() {
    this.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 = [];
  }
}

下面是对示例代码的解释：

• constructor方法用来创建一个items数组。
• push方法将一个元素添加到items数组的末尾。
• pop方法从items数组的末尾移除一个元素，并返回它。
• peek方法返回items数组的末尾元素。
• isEmpty方法返回items数组是否为空。
• size方法返回items数组的长度。
• clear方法将items数组清空。

栈的应用

栈在计算后缀表达式、括号匹配、HTML和XML解析等方面有广泛的应用，这里就不一一展开说明。

队列

什么是队列？

队列是一种“先进先出（FIFO）”的数据结构，也就是说最先进入队列的元素被最先移除。队列一般用数组或链表实现。

队列的操作

常用的队列操作有：

• enqueue: 将一个元素添加到队列的尾部。
• dequeue: 从队列的头部移除一个元素，并返回它。
• front: 返回队列头部的元素，但不删除它。

代码示例

下面是一个用数组实现队列的示例代码：

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

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    return this.items.shift();
  }

  front() {
    return this.items[0];
  }

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

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

  clear() {
    this.items = [];
  }
}

下面是对示例代码的解释：

• constructor方法用来创建一个items数组。
• enqueue方法将一个元素添加到items数组的末尾。
• dequeue方法从items数组的开头移除一个元素，并返回它。
• front方法返回items数组的第一个元素。
• isEmpty方法返回items数组是否为空。
• size方法返回items数组的长度。
• clear方法将items数组清空。

队列的应用

队列在CPU调度、消息传递、排队等方面有广泛的应用，这里也就不再一一展开。

总结

栈和队列是常见的数据结构，它们在编程中有着广泛的应用。在Javascript中，栈和队列一般用数组或链表实现。本文通过示例代码详细讲解了如何用数组实现栈和队列，并解释了它们的基本操作。

示例1：用栈来判断一个字符串中的括号是否匹配

function isBracketBalanced(str) {
  const stack = new Stack();
  for (let i = 0; i < str.length; i++) {
    const char = str.charAt(i);
    if (char === '(') {
      stack.push(char);
    } else if (char === ')') {
      if (stack.isEmpty()) {
        return false;
      } else {
        stack.pop();
      }
    }
  }
  return stack.isEmpty();
}

示例2：用队列来实现斐波那契数列

function fibonacciSeries(n) {
  const queue = new Queue();
  let fibonacci = 0;

  for (let i = 1; i <= n; i++) {
    if (i === 1 || i === 2) {
      fibonacci = 1;
    } else {
      const first = queue.dequeue();
      const second = queue.front();
      fibonacci = first + second;
    }
    queue.enqueue(fibonacci);
  }

  return queue.items;
}

希望本文对你理解栈和队列有所帮助。