佇列是先進先出（ First-In-First-Out，FIFO）的線性表。它只允許在表的一端進行插入，而在另一端刪除元素。佇列是一種常用的數據結構。佇列存取法是指採用佇列這種數據結構來訪問一組序列中的一個組件。這種訪問方法的特點是組件先來先被訪問。
基本介紹
- 中文名：佇列存取法
- 外文名：queue access method
- 學科：計算機
- 定義：採用佇列這種結構來訪問數據
- 有關術語：佇列
- 領域：計算機編程
順序佇列,循環佇列,
簡介
在計算機中，存取是一個動作合成詞，存指代計算機的寫入，取指代計算機的讀取（閱讀或複製取出）。
佇列存取法即採用佇列這種數據結構來訪問一組序列中的一個組件。在計算機編程中，經常採用佇列這種數據結構訪問一組元素。這種方法的特點是先來先服務。新元素只有添加到佇列的後端才能存取。佇列存取法一般與佇列的種類有關。佇列一般可以分為順序佇列和循環佇列。
順序佇列
建立順序佇列結構必須為其靜態分配或動態申請一片連續的存儲空間，並設定兩個指針進行管理。一個是隊頭指針front，它指向隊頭元素；另一個是隊尾指針rear，它指向下一個入隊元素的存儲位置，如圖所示
每次在隊尾插入一個元素是，rear增1；每次在隊頭刪除一個元素時，front增1。隨著插入和刪除操作的進行，佇列元素的個數不斷變化，佇列所占的存儲空間也在為佇列結構所分配的連續空間中移動。當front=rear時，佇列中沒有任何元素，稱為空佇列。當rear增加到指向分配的連續空間之外時，佇列無法再插入新元素，但這時往往還有大量可用空間未被占用，這些空間是已經出隊的佇列元素曾經占用過得存儲單元。
順序佇列中的溢出現象：
（1） "下溢"現象：當佇列為空時，做出隊運算產生的溢出現象。“下溢”是正常現象，常用作程式控制轉移的條件。
（2）"真上溢"現象：當佇列滿時，做進棧運算產生空間溢出的現象。“真上溢”是一種出錯狀態，應設法避免。
（3）"假上溢"現象：由於入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠無法重新利用。當佇列中實際的元素個數遠遠小於向量空間的規模時，也可能由於尾指針已超越向量空間的上界而不能做入隊操作。該現象稱為"假上溢"現象。
循環佇列
在實際使用佇列時，為了使佇列空間能重複使用，往往對佇列的使用方法稍加改進：無論插入或刪除，一旦rear指針增1或front指針增1 時超出了所分配的佇列空間，就讓它指向這片連續空間的起始位置。自己真從MaxSize-1增1變到0，可用取余運算rear%MaxSize和front%MaxSize來實現。這實際上是把佇列空間想像成一個環形空間，環形空間中的存儲單元循環使用，用這種方法管理的佇列也就稱為循環佇列。除了一些簡單套用之外，真正實用的佇列是循環佇列。
在循環佇列中，當佇列為空時，有front=rear，而當所有佇列空間全占滿時，也有front=rear。為了區別這兩種情況，規定循環佇列最多只能有MaxSize-1個佇列元素，當循環佇列中只剩下一個空存儲單元時，佇列就已經滿了。因此，佇列判空的條件時front=rear，而佇列判滿的條件時front=（rear+1）%MaxSize。
