佇列(Queue)

Da-Wei Chiang

大綱

  • 何謂佇列
  • 圖例佇列
    • 佇列的結構
    • 新增元素
    • 刪除元素
  • 實作練習
  • python的Queue模組
  • 佇列的時間複雜度

何謂佇列

  • 佇列是一種線性結構, 英文稱為Queue
  • 佇列讀取資料, 相當於將資料從佇列中刪除
  • 將資料放入佇列中稱為enqueue
  • 將資料從佇列中取出稱為dequeue
  • 整個Queue的存取資料過程具有「先進先出(first in first out)」的特性

圖例佇列

  • 佇列的結構
  • 新增佇列元素
  • 讀取(刪除)佇列元素

佇列的結構

  • 佇列的結構就像一個水管, 等待資料進入

新增佇列元素(enqueue)

讀取佇列元素(dequeue)

  • first in first out

練習

  • 使用array或list撰寫一個名為Queue的類別, 模擬Queue的結構
  • 該類別具備新增元素(enqueue)、讀取元素(dequeue)、查看Queue元素個數、查看整個Queue元素
  • 建構Queue的物件, 測試使用四種方法

python的Queue模組

#引用
from queue import Queue

put(data) : 新增元素
get() : 讀取元素
empty() : 判斷Queue是否為空
In [18]:
## 範例

from queue import Queue

my_queue = Queue()
print(my_queue.empty())
my_queue.put('芭樂')
my_queue.put('橘子')
print(my_queue.empty())
get_value = my_queue.get()
print("第一次讀取", get_value)
get_value = my_queue.get()
print("第二次讀取", get_value)

True
False
第一次讀取 芭樂
第二次讀取 橘子

練習

  • 請自行練習python內建queue模組

佇列的時間複雜度

  • search queue:O(n)
  • enqueue:O(1)
  • dequeue:O(1)