佇列


佇列的簡介

  • 佇列可以定義為有序列表,它允許在一端執行插入操作,稱為REAR,刪除操作在另一端執行,稱為FRONT
  • 佇列被稱為先進先出列表。
  • 例如,排隊等候鐵路車票的人佇列。

佇列的應用

由於佇列以先進先出的方式執行操作,這對於操作的排序是相當公平的。 佇列的各種應用如下所述。

  • 佇列被廣泛用作單個共用資源(如列印機,磁碟,CPU)的等待列表。
  • 佇列用於非同步資料傳輸(例如,資料不以兩個進程之間的相同速率傳輸)。 管道,檔案IO,通訊端。
  • 佇列在大多數應用程式中用作緩衝區,如MP3媒體播放器,CD播放器等。
  • 佇列用於維護媒體播放器中的播放列表,以便新增和刪除播放列表中的歌曲。
  • 佇列在作業系統中用於處理中斷。

時間複雜性

時間複雜性 存取 搜尋 插入 刪除
平均情況 θ(n) θ(n) θ(1) θ(1)
最壞情況 θ(n) θ(n) θ(1) θ(1)