iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 8
0
Software Development

擁抱「資料結構」的「演算法」系列 第 8

擁抱「資料結構」的「演算法」(08) - 佇列 Queue

前言

今天要介紹的佇列跟堆疊很相似,不同於堆疊的是佇列可以在兩個端點去做新增與刪除,就讓我們一起來認識佇列吧!


生活常識

你有沒有排隊的經驗呢?
https://ithelp.ithome.com.tw/upload/images/20200922/20129841PVshMIlh6T.png
圖片來源:https://www.pexels.com/zh-tw/photo/4481/

光想到今年年初大家忙著排口罩的日子就覺得可怕,因為常常的人龍,有時候要等 1 個小時,你會不會希望前面櫃台處理的速度快一點,這樣才可以快點輪到你呢?排隊這件事情我們可以分 3 個部分來看

  1. 櫃檯的處理速度:當處理速度越快,就可以越快服務下一位民眾
  2. 排隊的人龍:最早排隊的人,最早領到口罩,越晚到的人,等待時間越久

櫃台人員忙著發口罩,但民眾卻一直源源不絕的排隊,形成一邊在減少,一邊在追加的形況,那你還有什麼也是一邊在減少,一邊在增加的例子嗎?像某些停車場,也有規劃一進一出的通道
https://ithelp.ithome.com.tw/upload/images/20200922/20129841BPV4YagXe6.png

摩天輪大家有坐過嗎?當我們在排隊的時候,看到很多人從車廂下來的時候,就表示排隊的隊伍會往前進,就快輪到我們搭乘了
https://ithelp.ithome.com.tw/upload/images/20200920/201298413oOQzkvYKc.png
圖片來源:https://www.pexels.com/zh-tw/photo/3330203/


專業知識 - 佇列 Queue

佇列

特性:

  • 有兩個端點,分為前端後端
  • 後端只可新增資料
  • 前端只可刪除讀取資料
  • 資料的存取必須符合先進先出(First In First Out, FIFO)

如下圖:Alice先排隊,後面陸陸續續來了很多人,那因為 Alice 先排隊,於是就會優先拿到口罩
https://ithelp.ithome.com.tw/upload/images/20200922/20129841RL4R9ONN5x.png

佇列的 ADT

只要某一類別有提供以下的方法,我們都可以稱這個類別是一種列:

  • Create : 可建立一個空的佇列
  • Add : 可在後端新增資料,並得到一個新的佇列
  • Delete : 可刪除前端資料,並得到一個新的佇列
  • Front : 回傳前端的資料

佇列的實作

一般可以使用陣列或串列去實作出佇列,但程式碼的部分就先不討論,我們可以使用 C# 內建的 Queue 類別來操作看看

依序將12345,使用 Enqueue 方法,存入堆疊前端,然後再依序將資料印出

Queue<string> numbers = new Queue<string>();
numbers.Enqueue("1"); //將資料加入的後端
numbers.Enqueue("2");
numbers.Enqueue("3");
numbers.Enqueue("4");
numbers.Enqueue("5");

foreach( string number in numbers )
{
    Console.WriteLine(number);
}

//從的前端頭移除最早加入的元素
Console.WriteLine("\n取出前端的資料 : "+ numbers.Dequeue());  
輸出結果:
1
2
3
4
5

取出前端的資料 : 1

透過上述程式碼與輸出,可觀察出 C# 的 Queue 類別有符合後進先出(First In First Out, FIFO)的特性,也有提供 ADT 所定義的方法

實際應用

可以使用陣列串列去實作出佇列

  • 環狀佇列
    應用在行車紀錄器或監視器,只儲存最近 10 天的紀錄,可使用陣列實作,宣告一個長度為 10 的陣列,索引是 0 ~ 9,如果 10 天都存滿時,front = 0,rear = 9

https://ithelp.ithome.com.tw/upload/images/20200922/20129841m8x90nJlfJ.png

如果來到第十一天,那就把第一天的從前端刪除,並將第十一天尾端加入,front = 1,rear = 0
https://ithelp.ithome.com.tw/upload/images/20200922/20129841AROQJtUBBM.png

  • 優先佇列
    可應用在系統的作業排程上,比如在排隊的時候,有一些持有 VIP 的人,他們就可以插隊,變成優先處理,不需要符合 FIFO 特性

  • 雙向佇列
    前端與後端都可以執行輸入或取出資料


今日小結

佇列與堆疊都是抽象資料型態(Abstract Data Type, ADT),可以透過陣列串列去實作,我自己覺得這幾天認真了解之後,才發現生活中有很多實例,自己平時寫程式時用了很多陣列與串列,在操作資料時就有用到佇列與堆疊的特性,卻不自知,才了解到自己對於資料結構真的是一知半解,但現在終於慢慢有種撥雲見日的感覺了,繼續努力加油


今日謎題

小花買了一台榨汁機
https://ithelp.ithome.com.tw/upload/images/20200922/20129841HAiWEd47u7.png
圖片來源:momo

小花每天早上都要喝一杯精力湯,他依序將以下蔬果放入榨汁機的入口:

  1. 草莓
  2. 百香果
  3. 黃金奇異果
  4. 小黃瓜
  5. 藍莓
  6. 蝶豆花
  7. 葡萄

請問小花打完蔬果之後,殘渣蒐集桶會呈現什麼顏色呢?請畫出來

昨日解謎

解題說明:每個人輪流拿一張牌,發玩牌之後,依拿到牌的順序閱讀,就可以發現小花與小明的牌加起來是:STACK & LIFO

https://ithelp.ithome.com.tw/upload/images/20200922/201298410T3wgQuDxB.png

發牌影片


上一篇
擁抱「資料結構」的「演算法」(07) - 堆疊 Stack
下一篇
擁抱「資料結構」的「演算法」(09) - 樹 Tree
系列文
擁抱「資料結構」的「演算法」30

尚未有邦友留言

立即登入留言