擁抱「資料結構」的「演算法」(08) - 佇列 Queue
前言
今天要介紹的佇列跟堆疊很相似，不同於堆疊的是佇列可以在兩個端點去做新增與刪除，就讓我們一起來認識佇列吧！
生活常識
你有沒有排隊的經驗呢？
光想到今年年初大家忙著排口罩的日子就覺得可怕，因為常常的人龍，有時候要等 1 個小時，你會不會希望前面櫃台處理的速度快一點，這樣才可以快點輪到你呢？排隊這件事情我們可以分 3 個部分來看
- 櫃檯的處理速度：當處理速度越快，就可以越快服務下一位民眾
- 排隊的人龍：
最早排隊的人，最早領到口罩，越晚到的人，等待時間越久
櫃台人員忙著發口罩，但民眾卻一直源源不絕的排隊，形成一邊在減少，一邊在追加的形況，那你還有什麼也是一邊在減少，一邊在增加的例子嗎？像某些停車場，也有規劃一進一出的通道
摩天輪大家有坐過嗎？當我們在排隊的時候，看到很多人從車廂下來的時候，就表示排隊的隊伍會往前進，就快輪到我們搭乘了
圖片來源:https://www.pexels.com/zh-tw/photo/3330203/
專業知識 - 佇列 Queue
佇列
特性：
- 有兩個端點，分為
前端與後端 - 後端只可
新增資料 - 前端只可
刪除與讀取資料 - 資料的存取必須符合
先進先出(First In First Out, FIFO)
如下圖：Alice先排隊，後面陸陸續續來了很多人，那因為 Alice 先排隊，於是就會優先拿到口罩
佇列的 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
如果來到第十一天，那就把第一天的從前端刪除，並將第十一天從尾端加入，front = 1，rear = 0
優先佇列
可應用在系統的作業排程上，比如在排隊的時候，有一些持有 VIP 的人，他們就可以插隊，變成優先處理，不需要符合 FIFO 特性雙向佇列
前端與後端都可以執行輸入或取出資料
今日小結
佇列與堆疊都是抽象資料型態(Abstract Data Type, ADT)，可以透過陣列或串列去實作，我自己覺得這幾天認真了解之後，才發現生活中有很多實例，自己平時寫程式時用了很多陣列與串列，在操作資料時就有用到佇列與堆疊的特性，卻不自知，才了解到自己對於資料結構真的是一知半解，但現在終於慢慢有種撥雲見日的感覺了，繼續努力加油
今日謎題
小花買了一台榨汁機
圖片來源:momo
小花每天早上都要喝一杯精力湯，他依序將以下蔬果放入榨汁機的入口：
- 草莓
- 百香果
- 黃金奇異果
- 小黃瓜
- 藍莓
- 蝶豆花
- 葡萄
請問小花打完蔬果之後，殘渣蒐集桶會呈現什麼顏色呢？請畫出來
昨日解謎
解題說明：每個人輪流拿一張牌，發玩牌之後，依拿到牌的順序閱讀，就可以發現小花與小明的牌加起來是：STACK & LIFO
發牌影片
留言
張貼留言