全栈开发知识库

Kpsmart2025年3月7日大约 15 分钟

我将为您完善栈与队列的文档，内容全面且结构清晰。

---
title: 栈与队列
icon: javascript
order: 2
---

# 栈与队列

栈和队列是两种基本的线性数据结构，分别遵循后进先出(LIFO)和先进先出(FIFO)原则。本文将介绍如何使用数组和链表实现栈和队列，以及它们在算法和实际应用中的使用场景。

## 栈（Stack）

### 栈的基本概念

栈是一种遵循**后进先出**（Last In First Out，LIFO）原则的线性数据结构。这意味着最后添加到栈中的元素将是第一个被移除的元素。栈的操作主要集中在一端，称为栈顶。

栈的基本操作包括：
- **push**：将元素添加到栈顶
- **pop**：移除并返回栈顶元素
- **peek/top**：返回栈顶元素但不移除
- **isEmpty**：检查栈是否为空

### 使用数组实现栈

在JavaScript中，可以使用数组轻松实现栈结构：

```javascript
class ArrayStack {
  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;
  }
  
  // 清空栈
  clear() {
    this.items = [];
  }
  
  // 打印栈内容
  print() {
    console.log(this.items.toString());
  }
}

使用链表实现栈

使用链表实现栈可以避免数组动态调整大小的开销：

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedListStack {
  constructor() {
    this.top = null;
    this.size = 0;
  }
  
  // 将元素压入栈顶
  push(element) {
    const newNode = new Node(element);
    
    if (this.top === null) {
      this.top = newNode;
    } else {
      newNode.next = this.top;
      this.top = newNode;
    }
    
    this.size++;
  }
  
  // 弹出栈顶元素
  pop() {
    if (this.isEmpty()) {
      return "栈为空";
    }
    
    const temp = this.top;
    this.top = this.top.next;
    this.size--;
    
    return temp.data;
  }
  
  // 查看栈顶元素
  peek() {
    if (this.isEmpty()) {
      return "栈为空";
    }
    
    return this.top.data;
  }
  
  // 检查栈是否为空
  isEmpty() {
    return this.top === null;
  }
  
  // 获取栈的大小
  getSize() {
    return this.size;
  }
  
  // 清空栈
  clear() {
    this.top = null;
    this.size = 0;
  }
  
  // 打印栈内容
  print() {
    if (this.isEmpty()) {
      console.log("栈为空");
      return;
    }
    
    let current = this.top;
    let result = "";
    
    while (current) {
      result = `${current.data} -> ${result}`;
      current = current.next;
    }
    
    console.log(result.slice(0, -4)); // 移除最后的箭头
  }
}

栈的使用示例

// 创建并使用数组栈
const stack = new ArrayStack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log("栈顶元素:", stack.peek()); // 输出: 栈顶元素: 30
console.log("弹出元素:", stack.pop());  // 输出: 弹出元素: 30
console.log("栈大小:", stack.size());   // 输出: 栈大小: 2
stack.print();                        // 输出: 10,20

// 创建并使用链表栈
const linkedStack = new LinkedListStack();
linkedStack.push("A");
linkedStack.push("B");
linkedStack.push("C");
console.log("栈顶元素:", linkedStack.peek()); // 输出: 栈顶元素: C
console.log("弹出元素:", linkedStack.pop());  // 输出: 弹出元素: C
console.log("栈大小:", linkedStack.getSize()); // 输出: 栈大小: 2
linkedStack.print();                         // 输出: B -> A

队列（Queue）

队列的基本概念

队列是一种遵循先进先出（First In First Out，FIFO）原则的线性数据结构。这意味着第一个添加到队列中的元素将是第一个被移除的元素。队列的操作在两端进行：一端（队尾）用于添加元素，另一端（队首）用于移除元素。

队列的基本操作包括：

enqueue：将元素添加到队尾
dequeue：移除并返回队首元素
front：返回队首元素但不移除
isEmpty：检查队列是否为空

使用数组实现队列

在JavaScript中，可以使用数组实现队列结构：

class ArrayQueue {
  constructor() {
    this.items = [];
  }
  
  // 将元素添加到队尾
  enqueue(element) {
    this.items.push(element);
  }
  
  // 移除并返回队首元素
  dequeue() {
    if (this.isEmpty()) {
      return "队列为空";
    }
    return this.items.shift();
  }
  
  // 查看队首元素
  front() {
    if (this.isEmpty()) {
      return "队列为空";
    }
    return this.items[0];
  }
  
  // 检查队列是否为空
  isEmpty() {
    return this.items.length === 0;
  }
  
  // 获取队列的大小
  size() {
    return this.items.length;
  }
  
  // 清空队列
  clear() {
    this.items = [];
  }
  
  // 打印队列内容
  print() {
    console.log(this.items.toString());
  }
}

使用链表实现队列

使用链表实现队列可以提供更高效的入队和出队操作：

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedListQueue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }
  
  // 将元素添加到队尾
  enqueue(element) {
    const newNode = new Node(element);
    
    if (this.isEmpty()) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
    
    this.size++;
  }
  
  // 移除并返回队首元素
  dequeue() {
    if (this.isEmpty()) {
      return "队列为空";
    }
    
    const temp = this.front;
    
    if (this.front === this.rear) {
      this.front = null;
      this.rear = null;
    } else {
      this.front = this.front.next;
    }
    
    this.size--;
    return temp.data;
  }
  
  // 查看队首元素
  getFront() {
    if (this.isEmpty()) {
      return "队列为空";
    }
    
    return this.front.data;
  }
  
  // 检查队列是否为空
  isEmpty() {
    return this.front === null;
  }
  
  // 获取队列的大小
  getSize() {
    return this.size;
  }
  
  // 清空队列
  clear() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }
  
  // 打印队列内容
  print() {
    if (this.isEmpty()) {
      console.log("队列为空");
      return;
    }
    
    let current = this.front;
    let result = "";
    
    while (current) {
      result += `${current.data} -> `;
      current = current.next;
    }
    
    console.log(result + "null");
  }
}

队列的使用示例

// 创建并使用数组队列
const queue = new ArrayQueue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log("队首元素:", queue.front()); // 输出: 队首元素: 10
console.log("出队元素:", queue.dequeue()); // 输出: 出队元素: 10
console.log("队列大小:", queue.size()); // 输出: 队列大小: 2
queue.print(); // 输出: 20,30

// 创建并使用链表队列
const linkedQueue = new LinkedListQueue();
linkedQueue.enqueue("A");
linkedQueue.enqueue("B");
linkedQueue.enqueue("C");
console.log("队首元素:", linkedQueue.getFront()); // 输出: 队首元素: A
console.log("出队元素:", linkedQueue.dequeue()); // 输出: 出队元素: A
console.log("队列大小:", linkedQueue.getSize()); // 输出: 队列大小: 2
linkedQueue.print(); // 输出: B -> C -> null

特殊队列结构

循环队列

循环队列是一种特殊的队列，它的首尾相连，形成一个环。这种结构可以有效利用空间，避免在使用数组实现队列时频繁移动元素：

class CircularQueue {
  constructor(capacity) {
    this.capacity = capacity;
    this.items = new Array(capacity);
    this.front = 0;
    this.rear = 0;
    this.size = 0;
  }
  
  // 将元素添加到队尾
  enqueue(element) {
    if (this.isFull()) {
      return "队列已满";
    }
    
    this.items[this.rear] = element;
    this.rear = (this.rear + 1) % this.capacity;
    this.size++;
    return true;
  }
  
  // 移除并返回队首元素
  dequeue() {
    if (this.isEmpty()) {
      return "队列为空";
    }
    
    const item = this.items[this.front];
    this.items[this.front] = null;
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return item;
  }
  
  // 查看队首元素
  getFront() {
    if (this.isEmpty()) {
      return "队列为空";
    }
    
    return this.items[this.front];
  }
  
  // 检查队列是否为空
  isEmpty() {
    return this.size === 0;
  }
  
  // 检查队列是否已满
  isFull() {
    return this.size === this.capacity;
  }
  
  // 获取队列的大小
  getSize() {
    return this.size;
  }
  
  // 打印队列内容
  print() {
    if (this.isEmpty()) {
      console.log("队列为空");
      return;
    }
    
    let result = "";
    let count = 0;
    let index = this.front;
    
    while (count < this.size) {
      result += `${this.items[index]} -> `;
      index = (index + 1) % this.capacity;
      count++;
    }
    
    console.log(result + "null");
  }
}

双端队列

双端队列（Deque，Double-Ended Queue）是一种特殊的队列，它允许在两端进行插入和删除操作：

class Deque {
  constructor() {
    this.items = {};
    this.frontIndex = 0;
    this.rearIndex = 0;
  }
  
  // 在队首添加元素
  addFront(element) {
    this.frontIndex--;
    this.items[this.frontIndex] = element;
  }
  
  // 在队尾添加元素
  addRear(element) {
    this.items[this.rearIndex] = element;
    this.rearIndex++;
  }
  
  // 从队首移除元素
  removeFront() {
    if (this.isEmpty()) {
      return "双端队列为空";
    }
    
    const item = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return item;
  }
  
  // 从队尾移除元素
  removeRear() {
    if (this.isEmpty()) {
      return "双端队列为空";
    }
    
    this.rearIndex--;
    const item = this.items[this.rearIndex];
    delete this.items[this.rearIndex];
    return item;
  }
  
  // 查看队首元素
  peekFront() {
    if (this.isEmpty()) {
      return "双端队列为空";
    }
    
    return this.items[this.frontIndex];
  }
  
  // 查看队尾元素
  peekRear() {
    if (this.isEmpty()) {
      return "双端队列为空";
    }
    
    return this.items[this.rearIndex - 1];
  }
  
  // 检查双端队列是否为空
  isEmpty() {
    return this.rearIndex - this.frontIndex === 0;
  }
  
  // 获取双端队列的大小
  size() {
    return this.rearIndex - this.frontIndex;
  }
  
  // 清空双端队列
  clear() {
    this.items = {};
    this.frontIndex = 0;
    this.rearIndex = 0;
  }
  
  // 打印双端队列内容
  print() {
    if (this.isEmpty()) {
      console.log("双端队列为空");
      return;
    }
    
    let result = "";
    for (let i = this.frontIndex; i < this.rearIndex; i++) {
      result += `${this.items[i]} <-> `;
    }
    
    console.log(result.slice(0, -5)); // 移除最后的箭头
  }
}

优先队列

优先队列是一种特殊的队列，其中的元素具有优先级。优先级高的元素会被优先处理，而不是按照先进先出的顺序：

class PriorityQueue {
  constructor() {
    this.items = [];
  }
  
  // 添加元素到优先队列
  enqueue(element, priority) {
    const queueElement = { element, priority };
    let added = false;
    
    // 根据优先级插入元素
    for (let i = 0; i < this.items.length; i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }
    
    // 如果元素优先级最低，则添加到队尾
    if (!added) {
      this.items.push(queueElement);
    }
  }
  
  // 移除并返回队首元素
  dequeue() {
    if (this.isEmpty()) {
      return "优先队列为空";
    }
    
    return this.items.shift().element;
  }
  
  // 查看队首元素
  front() {
    if (this.isEmpty()) {
      return "优先队列为空";
    }
    
    return this.items[0].element;
  }
  
  // 检查优先队列是否为空
  isEmpty() {
    return this.items.length === 0;
  }
  
  // 获取优先队列的大小
  size() {
    return this.items.length;
  }
  
  // 清空优先队列
  clear() {
    this.items = [];
  }
  
  // 打印优先队列内容
  print() {
    if (this.isEmpty()) {
      console.log("优先队列为空");
      return;
    }
    
    let result = "";
    for (let i = 0; i < this.items.length; i++) {
      result += `${this.items[i].element}(优先级:${this.items[i].priority}) -> `;
    }
    
    console.log(result + "null");
  }
}

栈和队列的应用

栈的应用

函数调用栈：JavaScript引擎使用栈来管理函数调用

function firstFunction() {
  console.log("第一个函数");
  secondFunction();
  console.log("回到第一个函数");
}

function secondFunction() {
  console.log("第二个函数");
  thirdFunction();
  console.log("回到第二个函数");
}

function thirdFunction() {
  console.log("第三个函数");
}

// 调用第一个函数
firstFunction();

// 输出:
// 第一个函数
// 第二个函数
// 第三个函数
// 回到第二个函数
// 回到第一个函数

表达式求值：使用栈实现中缀表达式转后缀表达式（逆波兰表示法）并求值

// 中缀表达式转后缀表达式
function infixToPostfix(expression) {
  const precedence = {
    '+': 1,
    '-': 1,
    '*': 2,
    '/': 2,
    '^': 3
  };
  
  const stack = new ArrayStack();
  let postfix = "";
  
  // 将表达式拆分为单个字符
  const tokens = expression.split('');
  
  for (let i = 0; i < tokens.length; i++) {
    const token = tokens[i];
    
    // 如果是操作数，直接添加到后缀表达式
    if (/[0-9]/.test(token)) {
      postfix += token;
    }
    // 如果是左括号，入栈
    else if (token === '(') {
      stack.push(token);
    }
    // 如果是右括号，弹出栈中元素直到遇到左括号
    else if (token === ')') {
      while (!stack.isEmpty() && stack.peek() !== '(') {
        postfix += stack.pop();
      }
      
      // 弹出左括号
      if (!stack.isEmpty() && stack.peek() === '(') {
        stack.pop();
      }
    }
    // 如果是运算符
    else if (token in precedence) {
      while (
        !stack.isEmpty() &&
        stack.peek() !== '(' &&
        precedence[token] <= precedence[stack.peek()]
      ) {
        postfix += stack.pop();
      }
      
      stack.push(token);
    }
  }
  
  // 将栈中剩余的运算符添加到后缀表达式
  while (!stack.isEmpty()) {
    postfix += stack.pop();
  }
  
  return postfix;
}

// 计算后缀表达式的值
function evaluatePostfix(postfix) {
  const stack = new ArrayStack();
  
  // 遍历后缀表达式的每个字符
  for (let i = 0; i < postfix.length; i++) {
    const char = postfix[i];
    
    // 如果是操作数，入栈
    if (/[0-9]/.test(char)) {
      stack.push(parseInt(char));
    }
    // 如果是运算符，弹出两个操作数进行计算，然后将结果入栈
    else {
      const b = stack.pop();
      const a = stack.pop();
      
      switch (char) {
        case '+':
          stack.push(a + b);
          break;
        case '-':
          stack.push(a - b);
          break;
        case '*':
          stack.push(a * b);
          break;
        case '/':
          stack.push(a / b);
          break;
        case '^':
          stack.push(Math.pow(a, b));
          break;
      }
    }
  }
  
  // 栈顶元素就是表达式的值
  return stack.pop();
}

// 示例
const infix = "3+4*(2-1)";
const postfix = infixToPostfix(infix);
console.log(`中缀表达式: ${infix}`);
console.log(`后缀表达式: ${postfix}`);
console.log(`计算结果: ${evaluatePostfix(postfix)}`);

括号匹配：检查括号是否匹配

function isBalanced(expression) {
  const stack = new ArrayStack();
  
  for (let i = 0; i < expression.length; i++) {
    const char = expression[i];
    
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char);
    } else if (char === ')' || char === ']' || char === '}') {
      if (stack.isEmpty()) {
        return false;
      }
      
      const top = stack.pop();
      
      if (
        (char === ')' && top !== '(') ||
        (char === ']' && top !== '[') ||
        (char === '}' && top !== '{')
      ) {
        return false;
      }
    }
  }
  
  return stack.isEmpty();
}

// 示例
console.log(isBalanced("()")); // true
console.log(isBalanced("()[]{}")); // true
console.log(isBalanced("(]")); // false
console.log(isBalanced("([)]")); // false
console.log(isBalanced("{[]}")); // true

队列的应用

任务调度：使用队列实现任务调度器

class TaskScheduler {
  constructor() {
    this.taskQueue = new ArrayQueue();
    this.isRunning = false;
  }
  
  // 添加任务到队列
  addTask(task) {
    this.taskQueue.enqueue(task);
    console.log(`任务 "${task.name}" 已添加到队列`);
    
    // 如果调度器没有运行，启动它
    if (!this.isRunning) {
      this.start();
    }
  }
  
  // 启动调度器
  start() {
    if (this.isRunning) return;
    
    this.isRunning = true;
    this.processNextTask();
  }
  
  // 处理下一个任务
  processNextTask() {
    if (this.taskQueue.isEmpty()) {
      console.log("所有任务已完成");
      this.isRunning = false;
      return;
    }
    
    const task = this.taskQueue.dequeue();
    console.log(`开始执行任务 "${task.name}"`);
    
    // 模拟异步任务执行
    setTimeout(() => {
      task.execute();
      console.log(`任务 "${task.name}" 执行完成`);
      this.processNextTask();
    }, task.duration);
  }
}

// 任务类
class Task {
  constructor(name, duration, action) {
    this.name = name;
    this.duration = duration; // 任务执行时间（毫秒）
    this.action = action;
  }
  
  execute() {
    this.action();
  }
}

// 示例
const scheduler = new TaskScheduler();

// 创建任务
const task1 = new Task("任务1", 2000, () => console.log("任务1的操作"));
const task2 = new Task("任务2", 1000, () => console.log("任务2的操作"));
const task3 = new Task("任务3", 3000, () => console.log("任务3的操作"));

// 添加任务到调度器
scheduler.addTask(task1);
scheduler.addTask(task2);
scheduler.addTask(task3);

广度优先搜索：使用队列实现图的广度优先搜索

function bfs(graph, startNode) {
  const visited = new Set();
  const queue = new ArrayQueue();
  
  // 将起始节点加入队列并标记为已访问
  queue.enqueue(startNode);
  visited.add(startNode);
  
  console.log("广度优先搜索顺序:");
  
  while (!queue.isEmpty()) {
    // 出队一个节点并访问它
    const currentNode = queue.dequeue();
    console.log(currentNode);
    
    // 将所有未访问的邻接节点加入队列
    const neighbors = graph[currentNode] || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        queue.enqueue(neighbor);
        visited.add(neighbor);
      }
    }
  }
}

// 示例：图的邻接表表示
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};

// 从节点A开始进行广度优先搜索
bfs(graph, 'A');

打印机队列：模拟打印机任务队列

class Printer {
  constructor(ppm) {
    this.pagerate = ppm; // 每分钟打印页数
    this.currentTask = null;
    this.timeRemaining = 0;
  }
  
  // 打印机是否忙
  isBusy() {
    return this.timeRemaining > 0;
  }
  
  // 添加新的打印任务
  startNextTask(task) {
    this.currentTask = task;
    // 计算打印时间（秒）
    this.timeRemaining = task.getPages() * 60 / this.pagerate;
  }
  
  // 打印一秒
  tick() {
    if (this.currentTask === null) {
      return;
    }
    
    this.timeRemaining--;
    
    if (this.timeRemaining <= 0) {
      console.log(`打印任务 "${this.currentTask.getName()}" 已完成`);
      this.currentTask = null;
    }
  }
}

class PrintTask {
  constructor(name, pages) {
    this.name = name;
    this.pages = pages;
    this.timestamp = new Date();
  }
  
  getName() {
    return this.name;
  }
  
  getPages() {
    return this.pages;
  }
  
  getWaitTime(currentTime) {
    return (currentTime - this.timestamp) / 1000; // 转换为秒
  }
}

// 模拟打印队列
function simulatePrinting(numSeconds, pagesPerMinute) {
  const printer = new Printer(pagesPerMinute);
  const printQueue = new ArrayQueue();
  const waitTimes = [];
  
  // 模拟每秒的情况
  for (let currentSecond = 0; currentSecond < numSeconds; currentSecond++) {
    // 随机生成打印任务
    if (Math.random() < 0.1) { // 10%的概率生成新任务
      const task = new PrintTask(`Task-${currentSecond}`, Math.floor(Math.random() * 20) + 1);
      printQueue.enqueue(task);
      console.log(`${currentSecond}秒: 添加打印任务 "${task.getName()}" (${task.getPages()}页)`);
    }
    
    // 如果打印机空闲且队列中有任务
    if (!printer.isBusy() && !printQueue.isEmpty()) {
      const nextTask = printQueue.dequeue();
      const waitTime = nextTask.getWaitTime(new Date());
      waitTimes.push(waitTime);
      
      console.log(`${currentSecond}秒: 开始打印任务 "${nextTask.getName()}", 等待时间: ${waitTime.toFixed(2)}秒`);
      printer.startNextTask(nextTask);
    }
    
    // 打印机工作一秒
    printer.tick();
  }
  
  // 计算平均等待时间
  const averageWaitTime = waitTimes.reduce((sum, time) => sum + time, 0) / waitTimes.length;
  console.log(`模拟结束，平均等待时间: ${averageWaitTime.toFixed(2)}秒`);
}

// 示例：模拟180秒，打印机速度为10页/分钟
simulatePrinting(180, 10);

栈和队列的性能分析

栈的性能分析

操作	数组实现	链表实现
push	O(1)*	O(1)
pop	O(1)	O(1)
peek	O(1)	O(1)
isEmpty	O(1)	O(1)
size	O(1)	O(1)

*注：在JavaScript中，数组可能需要动态调整大小，此时push操作的时间复杂度可能为O(n)，但这种情况较少发生。

队列的性能分析

操作	数组实现	链表实现	循环队列
enqueue	O(1)*	O(1)	O(1)
dequeue	O(n)**	O(1)	O(1)
front	O(1)	O(1)	O(1)
isEmpty	O(1)	O(1)	O(1)
size	O(1)	O(1)	O(1)

*注：在JavaScript中，数组可能需要动态调整大小，此时enqueue操作的时间复杂度可能为O(n)，但这种情况较少发生。
**使用shift()方法从数组头部移除元素需要O(n)时间，因为所有剩余元素都需要向前移动。

栈和队列的比较

特性	栈	队列
访问顺序	后进先出(LIFO)	先进先出(FIFO)
添加元素	只能在一端(栈顶)	只能在一端(队尾)
移除元素	只能从一端(栈顶)	只能从一端(队首)
应用场景	函数调用、表达式求值、深度优先搜索	任务调度、广度优先搜索、缓冲区

栈和队列在JavaScript中的内置实现

JavaScript本身并没有直接提供栈和队列的内置实现，但可以使用数组来模拟：

// 使用数组模拟栈
const stack = [];
stack.push(1);       // 入栈
stack.push(2);
stack.push(3);
console.log(stack);  // [1, 2, 3]
console.log(stack.pop());  // 出栈，返回3
console.log(stack);  // [1, 2]

// 使用数组模拟队列
const queue = [];
queue.push(1);       // 入队
queue.push(2);
queue.push(3);
console.log(queue);  // [1, 2, 3]
console.log(queue.shift());  // 出队，返回1
console.log(queue);  // [2, 3]

实际应用示例

浏览器历史记录

浏览器的前进和后退功能可以使用两个栈来实现：

class BrowserHistory {
  constructor(homepage) {
    this.backStack = new ArrayStack();
    this.forwardStack = new ArrayStack();
    this.currentPage = homepage;
  }
  
  // 访问新页面
  visit(url) {
    this.backStack.push(this.currentPage);
    this.currentPage = url;
    this.forwardStack = new ArrayStack(); // 清空前进栈
    console.log(`当前页面: ${this.currentPage}`);
  }
  
  // 后退
  back() {
    if (this.backStack.isEmpty()) {
      console.log("无法后退，已经是最早的页面");
      return;
    }
    
    this.forwardStack.push(this.currentPage);
    this.currentPage = this.backStack.pop();
    console.log(`后退到: ${this.currentPage}`);
  }
  
  // 前进
  forward() {
    if (this.forwardStack.isEmpty()) {
      console.log("无法前进，已经是最新的页面");
      return;
    }
    
    this.backStack.push(this.currentPage);
    this.currentPage = this.forwardStack.pop();
    console.log(`前进到: ${this.currentPage}`);
  }
  
  // 显示当前页面
  getCurrentPage() {
    return this.currentPage;
  }
}

// 示例
const browser = new BrowserHistory("https://www.homepage.com");
browser.visit("https://www.google.com");
browser.visit("https://www.github.com");
browser.back();  // 回到 google.com
browser.back();  // 回到 homepage.com
browser.forward();  // 前进到 google.com
browser.visit("https://www.stackoverflow.com");  // 访问新页面，清空前进栈
browser.forward();  // 无法前进
browser.back();  // 回到 google.com

消息队列

在前端开发中，消息队列可以用于处理异步事件：

class MessageQueue {
  constructor() {
    this.queue = new ArrayQueue();
    this.processing = false;
  }
  
  // 添加消息到队列
  addMessage(message) {
    this.queue.enqueue(message);
    console.log(`消息 "${message.id}" 已添加到队列`);
    
    if (!this.processing) {
      this.processMessages();
    }
  }
  
  // 处理消息队列
  processMessages() {
    if (this.queue.isEmpty()) {
      console.log("所有消息已处理完毕");
      this.processing = false;
      return;
    }
    
    this.processing = true;
    const message = this.queue.dequeue();
    console.log(`处理消息: ${message.id}`);
    
    // 模拟异步处理消息
    setTimeout(() => {
      message.process();
      this.processMessages();
    }, message.delay);
  }
}

// 消息类
class Message {
  constructor(id, content, delay = 1000) {
    this.id = id;
    this.content = content;
    this.delay = delay;
  }
  
  process() {
    console.log(`消息内容: ${this.content}`);
  }
}

// 示例
const messageQueue = new MessageQueue();

// 创建消息
const message1 = new Message("msg1", "这是第一条消息", 2000);
const message2 = new Message("msg2", "这是第二条消息", 1000);
const message3 = new Message("msg3", "这是第三条消息", 3000);

// 添加消息到队列
messageQueue.addMessage(message1);
messageQueue.addMessage(message2);
messageQueue.addMessage(message3);

总结

栈和队列是两种基本但强大的数据结构，它们在计算机科学和日常编程中有广泛的应用。

栈遵循后进先出(LIFO)原则，适用于需要逆序处理数据的场景，如函数调用、表达式求值、括号匹配等。

队列遵循先进先出(FIFO)原则，适用于需要按顺序处理数据的场景，如任务调度、消息处理、广度优先搜索等。

在JavaScript中，我们可以使用数组或链表来实现栈和队列，也可以根据需要实现特殊的队列结构，如循环队列、双端队列和优先队列。

理解这些数据结构的原理和实现方式，对于编写高效的算法和解决复杂的编程问题至关重要。