資料結構－Stack 與 Queue

做個簡短的筆記。

簡述

資料結構有很多種，比較常見的有：

• Array 陣列
• Linked List 鏈結串列
• Stack 堆疊
• Queue 佇列
• Tree 樹

目前只學會 Array、Stack 和 Queue，其他的等之後學會後再來補。

我覺得學資料結構的目的在於：如何挑選出最適合的資料結構，這個才是最重要的。

像 JavaScript 的 Event loop 就用到了 Stack 和 Queue 這兩個結構。我以前沒想過背後的原因是什麼，只知道這就是構成 Event loop 的要素，一直到了學會以後，才明白為什麼要用這兩個東西。

Stack

就跟疊自助餐餐盤一樣，一層一層疊上去。

按照這樣的特性，可以發現一件事：如果要拿到最下面的餐盤，就得把上面的餐盤都先拿起來，這個就是 Stack 最重要的特性了，俗稱「First In Last Out」。

用 JS 來實作也很簡單：

class Stack {
  constructor () {
    this.stack = [];
  }
  push (item) {
    this.stack.push(item);
    return this.stack;
  }
  pop () {
    this.stack.pop();
    return this.stack;
  }
}

const stack = new Stack();
console.log(stack.push('A'));  // [ 'A' ]
console.log(stack.push('B'));  // [ 'A', 'B' ]
console.log(stack.push('C'));  // [ 'A', 'B', 'C' ]
console.log(stack.pop());  // [ 'A', 'B' ]
console.log(stack.pop());  // [ 'A' ]

Queue

就是排隊囉，不準插隊。

跟 Stack 相反，排在最前面的人會第一個離開隊伍，所以是「First In First Out」。

實作方式也不難：

class Queue {
  constructor () {
    this.queue = [];
  }
  push (item) {
    this.queue.push(item);
    return this.queue;
  }
  shift () {
    this.queue.shift();
    return this.queue;
  }
}

const queue = new Queue();
console.log(queue.push('A'));  // [ 'A' ]
console.log(queue.push('B'));  // [ 'A', 'B' ]
console.log(queue.push('C'));  // [ 'A', 'B', 'C' ]
console.log(queue.shift());  // [ 'B', 'C' ]
console.log(queue.shift());  // [ 'C' ]