資結筆記|佇列(Queue)

資結筆記|佇列(Queue)

更新於 發佈於 閱讀時間約 4 分鐘

基本觀念


  佇列(queue)是一種線性的資料結構,特色是從一端插入資料,另一端讀取資料,資料讀取完後就從佇列中移除。插入資料進佇列稱為enqueue,讀取資料稱為dequeue。因為每筆資料都是從佇列的一端進入,從另一段離開,這個過程稱之為先進先出(Firt In First Out)。佇列可以想像成去餐廳點餐,先點的餐點會先被製作,完成的餐點會被從佇列刪除。

raw-image

資料插入與讀取


  資料的插入和讀取比較簡單,所以不花太多篇幅描寫僅簡單的條列出一些重點

1、讀取資料時,已讀取的資料會被從佇列中移出。

2、必須先讀取先進入的資料,所以不能從佇列的中間讀取。



佇列程式實作


  我們使用串列模擬佇列的功能,假設從頭部插入資料,可以用python內建insert(0,data)達到enqueue的效果。從尾部讀取資料,使用pop達到dequeue的效果。大家可以自行使用python tutor 跑跑看程式,會更了解佇列的運作。

  class Queue():
def __init__(self):
self.queue = [] #使用串列模擬

def enqueue(self,data): #插入資料
self.queue.insert(0,data)

def dequeue(self): #讀取資料
if len(self.queue):
return self.queue.pop()
return "佇列是空的"


q = Queue()
q.enqueue('apple')
q.enqueue('guava')
q.enqueue('banana')

print("讀取佇列:",q.dequeue())
print("讀取佇列:",q.dequeue())
print("讀取佇列:",q.dequeue())
print("讀取佇列:",q.dequeue())

以下是輸出的結果,可以看到先輸入的的資料會先被輸出,並且輸出完後會將資料從佇咧移除,所以最後佇列會是空的。


raw-image

與佇列有關的python模組


  除了用陣列模擬佇列之外,也提供一個python內建的模組,可以使用佇列的功能,但因為python tutor 沒有支援這個模組,所以大家可以在自己的電腦安裝python環境和這個模組再試試看,有興趣的讀者不仿可以自己研究看看。

from queue import Queue

q = Queue()
for i in range(3): #輸入0~2至佇列中
q.put(i)

while not q.empty():
print(q.get()) #讀取佇列內的資料

以下是用電腦的環境輸出的結果,程式碼寫著從0輸入到2進入佇列,然後再一一讀取出來。


raw-image


avatar-img
資治通艦的沙龍
3會員
37內容數
人生中有的時候你會感知到,現在就是那個命運的分歧點,如果我不挽起袖子努力的話,我這一輩子大概就這樣了,所以我決定開始這個部落格,記錄我每天的努力,也希望可以分享學習的筆記與心得,大家可以一起交流學習。
留言
avatar-img
留言分享你的想法!
資治通艦的沙龍 的其他內容
鏈結串列(linked list)表面上也是一串數列,但與陣列不同的地方是,陣列的資料元素是在記憶體的連續空間,鏈結串列的資料是散落在記憶體的各處。而我們會將存放資料的地方稱為節點,每個節點包含2個區塊,一個區塊是資料區用來存放數據,另一個區塊是指標區用來指向下一個節點元素。
陣列(array)就是指將資料放在連續的記憶體空間,其中的每筆資料我們稱為元素。
快速排序法是一種高效的排序演算法,本文圖解說明其運作原理,並包含時間複雜度分析及程式碼實作範例。
本文介紹泡沫排序法的基本概念、圖解說明、時間複雜度計算以及程式碼實作。泡沫排序法是一種簡單易懂的排序演算法,通過不斷比較相鄰元素並交換位置,最終將最大值或最小值移動到數列的一端。文章詳細闡述了泡沫排序法的運作過程,並分析了其時間複雜度,以及如何優化演算法以提高效率。
這篇文章探討演算法的效能分析,著重於時間複雜度和空間複雜度的概念。文章首先說明如何判斷演算法的好壞,接著深入分析時間複雜度的計算方法,並以程式碼範例說明Big-O表示法。此外,文章也簡述空間複雜度的概念及其重要性,並提及常見的資料結構。
這篇文章說明演算法的定義、特徵以及一個有趣的小知識。演算法被定義為解決問題的流程,並以機車故障為例說明。文章也列出演算法的五個特徵:輸入、有限性、明確性、有效性及輸出。最後,文章提及世界上公認的第一個演算法是歐幾裡德演算法。
鏈結串列(linked list)表面上也是一串數列,但與陣列不同的地方是,陣列的資料元素是在記憶體的連續空間,鏈結串列的資料是散落在記憶體的各處。而我們會將存放資料的地方稱為節點,每個節點包含2個區塊,一個區塊是資料區用來存放數據,另一個區塊是指標區用來指向下一個節點元素。
陣列(array)就是指將資料放在連續的記憶體空間,其中的每筆資料我們稱為元素。
快速排序法是一種高效的排序演算法,本文圖解說明其運作原理,並包含時間複雜度分析及程式碼實作範例。
本文介紹泡沫排序法的基本概念、圖解說明、時間複雜度計算以及程式碼實作。泡沫排序法是一種簡單易懂的排序演算法,通過不斷比較相鄰元素並交換位置,最終將最大值或最小值移動到數列的一端。文章詳細闡述了泡沫排序法的運作過程,並分析了其時間複雜度,以及如何優化演算法以提高效率。
這篇文章探討演算法的效能分析,著重於時間複雜度和空間複雜度的概念。文章首先說明如何判斷演算法的好壞,接著深入分析時間複雜度的計算方法,並以程式碼範例說明Big-O表示法。此外,文章也簡述空間複雜度的概念及其重要性,並提及常見的資料結構。
這篇文章說明演算法的定義、特徵以及一個有趣的小知識。演算法被定義為解決問題的流程,並以機車故障為例說明。文章也列出演算法的五個特徵:輸入、有限性、明確性、有效性及輸出。最後,文章提及世界上公認的第一個演算法是歐幾裡德演算法。