#14 資料結構 Queue

在基礎的資料結構裡,Stack有一個好兄弟,長的跟它有一點像,但是提供的行為結果卻剛好相反,它的名字叫 Queue.在 Stack 中有一個可以把資料放入的行為叫 push,而把資料讀出來的行為叫 pop,並且最重要的重點是最先放進去的資料將會後最後被讀取的,所以這是一種先進後出或後進先出的情況.

類似於 Stack,Queue 也提供了方法可以將資料寫進去和讀出來,習慣稱為 Enqeueue 和 Dequeue.而跟 Stack 最大的不同就是 Queue 先寫進去的資料將會是先被讀出來,是一種先進先出或後進後出的情況.

你可以在資料結構的課本看到以上的內容,也可以找到 Queue 是如何被實做的,通常來說用 Array 來實做 Queue 會比較單純一點,只要一個 Array 加上兩個 index 用來記錄資料的起點和結束點.

我們在這邊不談論 Queue 實做的細節,我們來談談在什麼情況下它會派上用場.

在 Stack 的文章裡,你曾聽我講故事提到有關文字編輯程式中常用的 "上一步" 功能,透過 Stack 的實作讓我們可以清楚地製做 "上一步". 所以,你可以感受到當你在用 Stack 的時候,資料的順序會被倒過來.例如,你放 A B C 三個資料到 Stack,而讀出來時的順序是 C B A.所以,當你遇到需要這種資料巔倒的特性時,別忘了使用 Stack.

那 Queue 的特性呢 ? 你會很直覺地發現它並沒有提供什麼特別的效果,因為 A B C 的資料寫進去之後,讀出來的順序也是 A B C,那它有什麼過人之處需要我用到它呢 ? 若你能這樣直覺地想,其實也沒錯,因為若沒有什麼特別考量的話,資料先進先出的行為是帶來不了太多的好處. 但我想到了一個情況,如果你今天撰寫一個 API ,而你回傳的資料有規定必須要從頭開始讀取,如果你只是回傳一個 List 或一個 Array,那麼拿到資料的人就很容易違反規則,可以從中間或是從最後面開始讀取資料, 如果你回傳的資料結構是一個 Queue,那麼就等於限制了使用資料的人必須要從第一個資料開始讀,而且讀過之後就不能再重覆讀取相同的內容.我想這才是 Queue 所要展現的特性.

所以,Queue 的特點之一就在於第一個資料要被讀取之後,第二個資料才能被讀取. 這樣的特性似乎可以帶來某種程度的資料準確性,因為中間不會有資料被忽略而未被讀取.所以某些作業系統裡面或是某些商業產品便會依據這種特點來做成一個功能或產品,稱為 Queue system,例如在 Windows 作業系統中有 MSMQ (Microsoft Message Queue),而 IBM 也有 MQ 的產品.只不過這些產品的範圍更大,是用在多台電腦環境下的資料傳送,而傳送的特性就是跟 Queue 一樣,前面的資料要先讀取,後面的資料才能讀取.

在不同的需求情況下,我們可以依據資料結構的特性來找出適合應用的地方,到目前為止,我介紹了基本的資料結構有 Array, List, Stack, Queue 以及 Hash table. 這些基本的資料結構常常在日常的工作中被使用到,而且也幾乎滿足了大部份的工作需要.所以,好好了解這幾個資料結構,對一個不複雜的軟體開發工作來說就相當足夠了.

不過,因為我後面有許多內容會談到資料庫,所以還需要多介紹一個基本的資料結構叫 Tree,這是下一篇的內容.

Share: