iT邦幫忙

2021 iThome 鐵人賽

DAY 9
0
Software Development

少女人妻在廚房裡想不通的演算法系列 第 9

【在廚房想30天的演算法】Day 09 資料結構:佇列 Queue

Aloha!又是我少女人妻 Uerica!自從寫了鐵人賽文章後,因為我跟老公都太忙,我家狗狗對我發出各種抗議,拍滑鼠、抓手手、躲在角落哭哭,早上 8 點準時用粗糙肉墊狂毆我,而且都只攻擊我 Q_Q。三十天後我家狗狗可能會精通十八般武藝了~


佇列 (Queue)

佇列與昨天的堆疊有點類似,但堆疊是優先處理最新資料,只由一個方向推入與取出,但佇則是優先處理舊有的資料,也就是新增、刪除為不同端操作。

佇列的定義與特性

佇列簡單來說有點像排隊,先排的人可以先取得服務,像這種資料的存取方式又稱為「先進先出」 (FIFO, First-In-First-Out) ,除了平常排隊外,還有點餐、任務排程、銀行辦事抽號碼牌等。若為雙向都可操作的佇列稱為雙佇列。

  • 優點
    • 可按順序處理資料元素
    • 新增與取出資料快速
  • 缺點
    • 插入或刪除某指定資料元素不易
    • 要取出最新的資料元素,須先移除前面所有資料

pNZnaxS

常見的基本操作

enqueue: 將新資料元素加入佇列

dequeue: 將最先放入的資料移出佇列

front: 回傳佇列最前方、第一筆加入的資料元素

rear: 回傳佇列最後方、最後一筆加入的資料元素

size: 取得佇列大小

UNXO9cJ

來!實作

要建立佇列,我們要將資料儲存在記憶體的連續空間,並指出第一筆加入的資料元素(front),以及最後一筆新增的資料元素(rear),所以在此也用 javaScript 提供的陣列來實作。

//建構一個 Queue 類別,並將其儲存的資料 elements 的型態宣告為陣列。
class Queue {

    constructor() {
    this.elements = [];
    }

    //用 push() 來新增一筆元素在所有資料最後方 
    enqueue(element) {
    this.elements.push(element);
    }

    //用 shift() 來移出第一筆資料元素 
    dequeue() {
    return this.elements.shift();
    }

    //用陣列索引的特性找出第一筆資料元素
    front() {
    return this.elements[0];
    }

    //用 陣列索引與 length 的特性找出最後一筆新增的資料元素
    rear() {
    return this.elements[this.elements.length - 1];
    }

    //回傳有幾筆資料元素在佇列中
    size() {
    return this.elements.length;
    }
}

來建立實體

const queue = new Queue();

//增加些資料元素在佇列中
queue.enqueue("a");
queue.enqueue("b");
queue.enqueue("c");
queue.enqueue("d");
queue.enqueue("e");

//取出一筆資料元素
console.log(queue.dequeue()); //a
//回傳目前在最前方的資料元素
console.log(queue.front()); //b
//回傳目前在最後方的資料元素
console.log(queue.rear()); //e
//回傳佇列中所有資料元素還有幾筆
console.log(queue.size()); //4

參考資料:

JavaScript # 17 — 佇列(Queue)
JavaScript 學演算法(六)- 堆疊 & 佇列
【資料結構 – 重構】佇列與迴圈佇列


感謝各位閱讀!我去遛狗啦!明天見掰掰!


上一篇
【在廚房想30天的演算法】Day 08 資料結構:堆疊 Stack
下一篇
【在廚房想30天的演算法】Day 10 資料結構:樹 Tree
系列文
少女人妻在廚房裡想不通的演算法30

尚未有邦友留言

立即登入留言