繁體中文
選單

什麼是佇列

最先放入的元素最先取出的先進先出（FIFO）資料結構。放入尾端的操作稱為 enqueue，從前端取出的操作稱為 dequeue。用於等待處理的隊列、工作之間的資料傳遞、廣度優先搜尋等。

日文名稱: キュー

「佇列」出現在10領域的15道練習題中（資料結構與演算法, 嵌入式與韌體, 介面與匯流排規格等）。

這個名詞所屬的領域: 資料結構與演算法

練習佇列的題目

以條件變數（condition variable）「等到佇列不為空」時，被喚醒後之所以用while敘述而非if敘述重新確認條件，其理由下列何者正確？

  1. A因為while敘述比if敘述執行得更快
  2. B因為規定if敘述不能使用條件變數
  3. C因為即使被喚醒，也可能被其他執行緒搶先取走，或無緣無故醒來，導致條件並未滿足
查看答案與解析

正確答案：C. 因為即使被喚醒，也可能被其他執行緒搶先取走，或無緣無故醒來，導致條件並未滿足

條件變數的等待，是先放開鎖並休眠，收到通知醒來後再重新取得鎖才返回。然而在醒來之前，其他執行緒可能先取得鎖並取走佇列的元素。此外，因實作上的考量，也允許在沒有通知的情況下醒來（虛假喚醒，spurious wakeup）。因此，醒來後要確認條件，若不滿足就再次等待，所以要寫成while敘述。

在RTOS中，從讀取感測器的工作傳遞資料給負責顯示的工作時，使用佇列（訊息佇列）的優點，下列何者正確？

  1. A資料經過佇列時會自動加密
  2. B接收端可休眠等待資料到來，傳送端與接收端的速度差異也能以佇列暫存來吸收
  3. C使用佇列後，工作的優先順序就不需要了
查看答案與解析

正確答案：B. 接收端可休眠等待資料到來，傳送端與接收端的速度差異也能以佇列暫存來吸收

若以共用變數與旗標傳遞資料，就需要設法防止資料競爭，以及接收端反覆去檢查的負擔。使用RTOS的佇列，傳送端只要放入資料，接收端則可在資料到來之前處於等待狀態而不佔用CPU。佇列中可暫存多筆資料，因此即使傳送端暫時較快，資料也不會遺失。

解析中的「佇列」

出現「佇列」的題目（15題）

  1. 以條件變數（condition variable）「等到佇列不為空」時，被喚醒後之所以用while敘述而非if敘述重新確認條件，其理由下列何者正確？
  2. 在RTOS中，從讀取感測器的工作傳遞資料給負責顯示的工作時，使用佇列（訊息佇列）的優點，下列何者正確？
  3. 對空的佇列依序放入 A、B、C，取出1個，放入 D 後取出1個，再放入 E 後取出1個。依序排列取出的元素，下列何者正確？
  4. 有一個把元素數為4的字串型陣列 q 環狀使用的佇列。head 與 tail 的初值為1，enq(v) 執行 q[tail] ← v 後再執行 tail ← tail mod 4 + 1，deq() 回傳 q[head] 的值後執行 head ← head mod 4 + 1。執行下列程式時，「E」會存放在 q 的哪個元素？
  5. 廣泛用於高速 SSD 與主機連接、利用 PCI Express 的介面規格是下列何者？
  6. 關於半虛擬化（paravirtualization）的說明，下列何者正確？
  7. 在嵌入式裝置中使用RTOS（即時作業系統）的主要目的，下列何者正確？
  8. 下列關於PCI Express所使用的MSI（訊息訊號中斷）之特徵，何者正確？
  9. 對於與裝置之間逐一交換數千次小量資料的程式，下列哪一種加速方法最有效？
  10. 下列關於TCP壅塞控制之基本概念的敘述，何者正確？
  11. 在瀏覽器中執行上方的JavaScript時，主控台顯示文字的順序，下列何者正確？
  12. 對空的堆疊依序進行 push 1、push 2、pop、push 3、push 4、pop、pop 的操作。依序排列以 pop 取出的值，下列何者正確？
  13. 以根為 a[0] 的陣列表示父節點值大於或等於子節點值的最大堆積。對堆積 50, 30, 40, 10, 20, 35 加入45：先放在末尾，只要比父節點大就與父節點交換。操作後的陣列為下列何者？
  14. 在邊沒有權重的圖中，想求出從起點到各頂點的最少邊數。適合的搜尋方法與所使用的資料結構組合為下列何者？
  15. 當伺服器的使用率（忙碌時間的比例）接近100%時，請求的等待時間會如何變化？

相關名詞

堆疊 RTOS（即時作業系統） 廣度優先搜尋 陣列 PCI Express 中斷 條件變數（Condition variable） 資料競爭（Data race） 取餘運算 SSD(固態硬碟)

前往名詞解釋列表