后进先出还是先进先出？堆栈/队列指南

假设理解 Big O 表示法。 JavaScript 中有示例。资料参考 Gayle Laakmann McDowell 的《Cracking the Coding Interview》

今天，我们将探讨两种基本的数据结构：堆栈和队列。我们将深入研究它们的概念、用例，并使用经典和基于原型的方法在 JavaScript 中实现它们。

---

堆栈：后进先出 (LIFO)

想象一下一堆煎饼 - 你最后放在上面的一个是你第一个吃的。这正是堆栈数据结构的工作原理。它遵循后进先出（LIFO）原则。

关键操作

• push(item): 将一个项目添加到堆栈顶部
• pop()：从堆栈中删除顶部项目
• peek()：返回顶部项目而不删除它
• isEmpty()：检查栈是否为空

使用案例

堆栈在涉及以下场景时特别有用：

• 递归算法
• 文本编辑器中的撤消机制

JavaScript 实现

经典面向对象编程

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

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

  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }

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

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

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

基于原型

function Stack() {
  this.items = [];
}

Stack.prototype.push = function(element) {
  this.items.push(element);
};

Stack.prototype.pop = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items.pop();
};

Stack.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items[this.items.length - 1];
};

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

Stack.prototype.size = function() {
  return this.items.length;
};

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

---

队列：先进先出 (FIFO)

现在，让我们将焦点转移到队列上。与堆栈不同，队列遵循先进先出（FIFO）原则。想象一下音乐会场地的排队——第一个到达的人就是第一个进入的人。

关键操作

• enqueue(item): 将一个项目添加到队列末尾
• dequeue()：从队列中删除第一项
• peek()：返回第一项而不删除它
• isEmpty()：检查队列是否为空

使用案例

队列常用于：

• 广度优先搜索算法
• 任务调度

JavaScript 实现

经典面向对象编程

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

class Queue {
  constructor() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }

  enqueue(element) {
    const newNode = new Node(element);
    if (this.isEmpty()) {
      this.start = newNode;
      this.end = newNode;
    } else {
      this.end.next = newNode;
      this.end = newNode;
    }
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    const removedData = this.start.data;
    this.start = this.start.next;
    this.size--;
    if (this.isEmpty()) {
      this.end = null;
    }
    return removedData;
  }

  peek() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.start.data;
  }

  isEmpty() {
    return this.size === 0;
  }

  getSize() {
    return this.size;
  }

  clear() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }
}

基于原型

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

function Queue() {
  this.start = null;
  this.end = null;
  this.size = 0;
}

Queue.prototype.enqueue = function(element) {
  const newNode = new Node(element);
  if (this.isEmpty()) {
    this.start = newNode;
    this.end = newNode;
  } else {
    this.end.next = newNode;
    this.end = newNode;
  }
  this.size++;
};

Queue.prototype.dequeue = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  const removedData = this.start.data;
  this.start = this.start.next;
  this.size--;
  if (this.isEmpty()) {
    this.end = null;
  }
  return removedData;
};

Queue.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  return this.start.data;
};

Queue.prototype.isEmpty = function() {
  return this.size === 0;
};

Queue.prototype.getSize = function() {
  return this.size;
};

Queue.prototype.clear = function() {
  this.start = null;
  this.end = null;
  this.size = 0;
};

---

绩效分析

堆栈和队列都提供 $O(1)$O(1) 有效实现时，其核心操作（堆栈的压入/弹出、队列的入队/出队）的时间复杂度。这使得它们在特定用例中具有高性能。

它们都为许多常见的编程问题提供了优雅的解决方案，并构成了更复杂的数据结构和算法的基础。通过在 JavaScript 中理解并实现这些结构，您就能够很好地解决各种 Leetcode/算法问题？.

以上是后进先出还是先进先出？堆栈/队列指南的详细内容。更多信息请关注PHP中文网其他相关文章！