iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 5
0

排隊?

人潮眾多的時候就需要排隊,吃東西要排隊,看電影要排隊,搭公車也要排隊。
排隊的目的就是以順序來確保公平性。
所以,第一個排隊的人可以先買到食物,先買到電影片,先上公車,而排在隊伍尾端的人,則是最後才能買東西。

佇列 Queue

可以將資料結構 佇列 比擬為排隊的隊伍,將要存放的資料比擬為人。

  • 從排隊方面來看:
    排隊隊伍的前面是先排隊的人,所以會先離開隊伍;而隊伍的尾端就是晚排隊的人,因此會晚離開隊伍。
  • 佇列的角度來看:
    先存放的資料,會先離開佇列,而後存放的資料,會較晚離開佇列。
    這就是一種先進先出 First in First out (FIFO) 的現象。
  • Stack正好相反,Stack為後進先出。*

功能

  • Enqueue -
    將新資料由佇列後端(rear)加入
    排隊的人由隊伍後面加入排隊的隊伍
  • Dequeue -
    從佇列前端(front)刪除一個資料
    到號的人從排隊的人離開隊伍
  • IsFull -
    判斷佇列是否是滿的
  • IsEmpty-
    判斷佇列是否是空的

應用

  • 工作排程 -
    於多工系統中,許多程序共享CPU的資源,就必須利用Queue來分配資源。
  • 廣度優先搜尋(BFS)

參考

細談資料結構 第六版
ISBN 978-986-312-014-8


上一篇
[Data Structure][Stack]
下一篇
[Data Structure][Graph] - Theory
系列文
學習資料結構30天30

尚未有邦友留言

立即登入留言