后進先出還是先進先出？堆棧/隊列指南-魔扣目錄

假設理解 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;
};

登錄后復制