築夢角落

致力於用最生活化的例子讓所有人都能懂程式,也喜歡分享動漫、小說心得,以及自己的所見所聞、所思所想。

佇列(Queue)是什麼?幾個常見的佇列應用

最後更新時間 : 2023-02-03 | viewed : 1895

佇列

今天來簡單介紹什麼是佇列,以及佇列常見的應用。

 

目次

 

什麼是佇列?


佇列(Queue)是一種資料結構,也稱隊列,具有先進先出的特性,實作上經常以陣列或鏈結串列(Linked list)來實現。

所謂的先進先出,是指先進入佇列的元素可以先離開

生活中與佇列特性相似的是「排隊」,比如去電影院排隊買票,就是先來的人先買,買完之後從隊伍前方離開,後來的人就排進隊伍尾端,等待輪到自己。

 

常見應用


排隊這個行為在實務上十分常見,比如某些 Http Server 會依照先來後到的順序,依序處理客戶端請求

單執行緒

(單執行緒的情境)

 

如果 Server 是多執行緒設計,通常仍會有一個排隊佇列,讓多個執行緒去消化佇列中的請求。

多執行緒

(多執行緒的情境)

 

緩衝區


緩衝區也可以說是佇列的一種應用,它是一個暫時存放資料的地方,可以把它想像成家樂福結帳櫃台的輸送帶(不是業配XD)。

顧客在輸送帶一端逐一放上自己要購買的商品,店員在輸送帶的另一端依序取出商品、結帳,當輸送帶滿載時,顧客就暫時無法放上商品,必須等待店員處理掉輸送帶上的一個商品後,顧客才能再放入新的商品。

這種工作方式在程式裡常以「生產者、消費者」模式來稱之。

要注意的是,在家樂福結帳的例子中,顧客是生產者(把商品放上輸送帶),店員是消費者(消耗輸送帶上的商品),而緩衝區實際上也跟輸送帶一樣,通常會有固定大小,一旦緩衝區塞滿了,就必須等待消費者把東西從緩衝區取出,才能再繼續丟入東西。

生產者、消費者模式是很常見的應用,無論是萬人同時在線的大型網路服務,或是個人電腦的 I/O 設備,都能發現它的蹤影。

 

訊息佇列(Message Queue)


有一種和緩衝區概念相似的應用,叫作 MQ(Message Queue)

可以簡單把 MQ 想像成功能完善的雲端緩衝區,常用於不同的程序(Process)之間交換資料,A 把要給 B 的資料丟進 MQ 的 Queue 裡,B 有空的時候再自己從 Queue 裡取走資料。

雖然不需要使用 MQ 也同樣能交換資料,但使用 MQ 的確是有一些好處的。

舉例來說,因為 MQ 本身是一個獨立的服務(service),如果 A 跟 B 之間是透過 MQ 交換訊息,它們可以不用知道彼此的 IP 位址,只要它們都知道 MQ 的 IP 位址就可以了,某些應用情境可以增加 Server 的安全性。

 

Message Queue

 

javascript 底層機制


javascript 的底層實作也有用到佇列。

因為 javascript 是單執行緒程式,這就像是整間店只有一個店員能處理所有顧客的需求。

如果某個特別耗時需要長時間等待回應的任務獨佔了執行緒(店員),使用者(顧客)會感覺整個網頁是卡死的,想當然使用體驗會很差。

針對這個問題,佇列是可行的解法之一,需要等待回應的任務不需要讓執行緒傻傻地等,執行緒可以先去處理別的事,只要把需要等待的任務先記到佇列裡,晚點再回來接續處理就好。

日常生活中我們其實很常運用這種策略,比如去夜市買消夜的時候,跟老闆點了一份炸雞排,然後說「我等等來拿」就又去其他攤位點餐了。

 

另外,像廣度優先搜尋演算法也有使用到佇列,有興趣的人可以自行查尋相關資料,或是參考我以前寫的 SLG 這篇

 

總結


佇列和堆疊一樣,是應用廣泛的典型資料結構之一,佇列常見的應用情境大多具有一個特徵:暫時存放,稍候執行,並保證一定會按先來後到的順序執行。

很多人要做同一件事情的時候需要排隊,是用來理解佇列的一個淺顯易懂的例子,但從 javascript 跟廣度優先搜尋的例子不難發現,佇列不僅能用在多人排隊的情境,也能用在安排自己執行任務的順序。

 

 
我要留言!
 

X
暱稱(選填)
email(選填,僅站長可見。)
留言 To:#