後進先出還是先進先出？堆疊/佇列指南

假設理解 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) O(1)

有效實現時，其核心操作（堆疊的壓入/彈出、佇列的入隊/出隊）的時間複雜度。這使得它們在特定用例中具有高效能。 它們都為許多常見的程式設計問題提供了優雅的解決方案，並構成了更複雜的資料結構和演算法的基礎。透過在 JavaScript 中理解並實現這些結構，您就能夠很好地解決各種 Leetcode/演算法問題？ .

以上是後進先出還是先進先出？堆疊/佇列指南的詳細內容。更多資訊請關注PHP中文網其他相關文章！