佇列元素

佇列是一種先進先出的線性表。它只允許在表的一端進行插入，而在另一端刪除元素。佇列元素是指佇列中的數據元素或指數據元素使用佇列數據結構進行有關操作。佇列數據元素的數據類型可以採用已有數據類型或自定義的數據類型。

基本介紹

• 中文名：佇列元素
• 外文名：queue element
• 學科：計算機
• 定義：佇列中的數據元素
• 有關術語：佇列
• 領域：數據結構

基本介紹

佇列元素是指佇列中的數據元素。在計算機中，佇列是經常被使用的數據結構之一，不同的套用中，佇列元素的類型也是各不相同。對佇列元素進行有關操作，首先要符合佇列的有關操作要求。為了方便對佇列元素進行管理，在有關程式和套用中，一般都設定了佇列元素的最大長度。同時防止佇列元素溢出，系統中都設定了緩衝管理。

緩衝區

在計算機系統中，緩衝區是指多個以不同速度或優先權運行的硬體或程式進程共享的數據區，緩衝區的存在使它們之間的相互等待變少了，提高了系統的運行效率。先結束的可以把結果放入緩衝區內，進行下面的工 作；而後幹完的可以從緩衝區內取出原來的數據繼續工作；不用像原來那樣，先幹完的必須等待後幹完的，這樣的等待在計算機內是十分耗時的。為了使這種相互等待變得比較少，對緩衝區大小的處理及緩衝算法一定要十分小心地選擇。緩 沖區的作用是：(1)在高速和低速設備之間起一個速度平滑作用；(2)暫時存儲數據；(3)經常訪問的 數據可以放進緩衝區，減少對慢速設備的訪問，以提高效率。緩衝區溢出（buffer overflow），是針對程式設計缺陷，向程式輸入緩衝區寫入使之溢出的內容（通常是超過緩衝區能保存的最大數據量的數據），從而破壞程式運行、趁中斷之並獲取程式乃至系統的控制權。緩衝區溢出原指當某個數據超過了處理程式限制的範圍時，程式出現的異常操作。造成此現象的原因有：存在缺陷的程式設計。例如C語言，不像其他一些高級語言會自動進行數組或者指針的邊界檢查，增加溢出風險，另外C語言中的C標準庫還具有一些非常危險的操作函式，使用不當也為溢出創造條件。

操作有關函式

add( );

增加一個元素，如果佇列已滿，則拋出一個異常。

remove( );

移除並返回佇列頭部的元素，如果佇列為空，則拋出一個異常。

element( );

返回佇列頭部的元素，如果佇列為空，則拋出一個異常。

offer( );

添加一個元素並返回true ，如果佇列已滿，則返回false。

poll( );

移除並返問佇列頭部的元素，如果佇列為空，則返回null。

peek( ) ;

返回佇列頭部的元素，如果佇列為空，則返回null。

put( );

添加一個元素，如果佇列滿，則阻塞。

get( ) ;

移除並返回佇列頭部的元素，如果佇列為空，則阻塞。

佇列實現方式

順序佇列

順序佇列的定義

採用順序存儲結構的佇列稱為順序佇列，順序佇列實際上是運算受限的順序表。

順序佇列的表示

①和順序表一樣，順序佇列用一個向量空間來存放當前佇列中的元素。

②由於佇列的隊頭和隊尾的位置是變化的，設定兩個指針front和rear分別指示隊頭元素和隊尾元素在向量空間中的位置，它們的初值在佇列初始化時均應置為0。

順序佇列中的溢出現象

① "下溢"現象

當佇列為空時，做出隊運算產生的溢出現象。“下溢”是正常現象，常用作程式控制轉移的條件。

② "真上溢"現象

當佇列滿時，做入隊運算產生空間溢出的現象。“真上溢”是一種出錯狀態，應設法避免。

③ "假上溢"現象

由於入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠無法重新利用。當佇列中實際的元素個數遠遠小於向量空間的規模時，也可能由於尾指針已超越向量空間的上界而不能做入隊操作。該現象稱為"假上溢"現象。

鏈佇列

在佇列的形成過程中，可以利用線性鍊表的原理，來生成一個佇列。

基於鍊表的佇列，要動態創建和刪除節點，效率較低，但是可以動態增長。

佇列採用的FIFO(first in first out)，新元素（等待進入佇列的元素）總是被插入到鍊表的尾部，而讀取的時候總是從鍊表的頭部開始讀取。每次讀取一個元素，釋放一個元素。所謂的動態創建，動態釋放。因而也不存在溢出等問題。由於鍊表由結構體間接而成，遍歷也方便。

循環佇列

在實際使用佇列時，為了使佇列空間能重複使用，往往對佇列的使用方法稍加改進：無論插入或刪除，一旦rear指針增1或front指針增1 時超出了所分配的佇列空間，就讓它指向這片連續空間的起始位置。自己真從MaxSize-1增1變到0，可用取余運算rear%MaxSize和front%MaxSize來實現。這實際上是把佇列空間想像成一個環形空間，環形空間中的存儲單元循環使用，用這種方法管理的佇列也就稱為循環佇列。除了一些簡單套用之外，真正實用的佇列是循環佇列。

在循環佇列中，當佇列為空時，有front=rear，而當所有佇列空間全占滿時，也有front=rear。為了區別這兩種情況，規定循環佇列最多只能有MaxSize-1個佇列元素，當循環佇列中只剩下一個空存儲單元時，佇列就已經滿了。因此，佇列判空的條件時front=rear，而佇列判滿的條件時front=(rear+1)%MaxSize。