[科普中國]-隊(duì)列元素

簡介

隊(duì)列元素是指隊(duì)列中的數(shù)據(jù)元素。在計(jì)算機(jī)中，隊(duì)列是經(jīng)常被使用的數(shù)據(jù)結(jié)構(gòu)之一，不同的應(yīng)用中，隊(duì)列元素的類型也是各不相同。對(duì)隊(duì)列元素進(jìn)行有關(guān)操作，首先要符合隊(duì)列的有關(guān)操作要求。為了方便對(duì)隊(duì)列元素進(jìn)行管理，在有關(guān)程序和應(yīng)用中，一般都設(shè)置了隊(duì)列元素的最大長度。同時(shí)防止隊(duì)列元素溢出，系統(tǒng)中都設(shè)置了緩沖管理。

緩沖區(qū)在計(jì)算機(jī)系統(tǒng)中，緩沖區(qū)是指多個(gè)以不同速度或優(yōu)先級(jí)運(yùn)行的硬件或程序進(jìn)程共享的數(shù)據(jù)區(qū)，緩沖區(qū)的存在使它們之間的相互等待變少了，提高了系統(tǒng)的運(yùn)行效率。先結(jié)束的可以把結(jié)果放入緩沖區(qū)內(nèi)，進(jìn)行下面的工 作；而后干完的可以從緩沖區(qū)內(nèi)取出原來的數(shù)據(jù)繼續(xù)工作；不用像原來那樣，先干完的必須等待后干完的，這樣的等待在計(jì)算機(jī)內(nèi)是十分耗時(shí)的。為了使這種相互等待變得比較少，對(duì)緩沖區(qū)大小的處理及緩沖算法一定要十分小心地選擇。緩 沖區(qū)的作用是：(1)在高速和低速設(shè)備之間起一個(gè)速度平滑作用；(2)暫時(shí)存儲(chǔ)數(shù)據(jù)；(3)經(jīng)常訪問的 數(shù)據(jù)可以放進(jìn)緩沖區(qū)，減少對(duì)慢速設(shè)備的訪問，以提高效率。緩沖區(qū)溢出（buffer overflow），是針對(duì)程序設(shè)計(jì)缺陷，向程序輸入緩沖區(qū)寫入使之溢出的內(nèi)容（通常是超過緩沖區(qū)能保存的最大數(shù)據(jù)量的數(shù)據(jù)），從而破壞程序運(yùn)行、趁中斷之并獲取程序乃至系統(tǒng)的控制權(quán)。緩沖區(qū)溢出原指當(dāng)某個(gè)數(shù)據(jù)超過了處理程序限制的范圍時(shí)，程序出現(xiàn)的異常操作。造成此現(xiàn)象的原因有：存在缺陷的程序設(shè)計(jì)。例如C語言，不像其他一些高級(jí)語言會(huì)自動(dòng)進(jìn)行數(shù)組或者指針的邊界檢查，增加溢出風(fēng)險(xiǎn)，另外C語言中的C標(biāo)準(zhǔn)庫還具有一些非常危險(xiǎn)的操作函數(shù)，使用不當(dāng)也為溢出創(chuàng)造條件。

隊(duì)列元素操作有關(guān)函數(shù)add( );

增加一個(gè)元素，如果隊(duì)列已滿，則拋出一個(gè)異常。

remove( );

移除并返回隊(duì)列頭部的元素，如果隊(duì)列為空，則拋出一個(gè)異常。

element( );

返回隊(duì)列頭部的元素，如果隊(duì)列為空，則拋出一個(gè)異常。

offer( );

添加一個(gè)元素并返回true ，如果隊(duì)列已滿，則返回false。

poll( );

移除并返問隊(duì)列頭部的元素，如果隊(duì)列為空，則返回null。

peek( ) ;

返回隊(duì)列頭部的元素，如果隊(duì)列為空，則返回null。

put( );

添加一個(gè)元素，如果隊(duì)列滿，則阻塞。

get( ) ;

移除并返回隊(duì)列頭部的元素，如果隊(duì)列為空，則阻塞。

隊(duì)列實(shí)現(xiàn)方式順序隊(duì)列順序隊(duì)列的定義

采用順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列稱為順序隊(duì)列，順序隊(duì)列實(shí)際上是運(yùn)算受限的順序表。

順序隊(duì)列的表示

①和順序表一樣，順序隊(duì)列用一個(gè)向量空間來存放當(dāng)前隊(duì)列中的元素。

②由于隊(duì)列的隊(duì)頭和隊(duì)尾的位置是變化的，設(shè)置兩個(gè)指針front和rear分別指示隊(duì)頭元素和隊(duì)尾元素在向量空間中的位置，它們的初值在隊(duì)列初始化時(shí)均應(yīng)置為0。

順序隊(duì)列中的溢出現(xiàn)象

① "下溢"現(xiàn)象

當(dāng)隊(duì)列為空時(shí)，做出隊(duì)運(yùn)算產(chǎn)生的溢出現(xiàn)象?！跋乱纭笔钦，F(xiàn)象，常用作程序控制轉(zhuǎn)移的條件。

② "真上溢"現(xiàn)象

當(dāng)隊(duì)列滿時(shí)，做入隊(duì)運(yùn)算產(chǎn)生空間溢出的現(xiàn)象。“真上溢”是一種出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免。

③ "假上溢"現(xiàn)象

由于入隊(duì)和出隊(duì)操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠(yuǎn)無法重新利用。當(dāng)隊(duì)列中實(shí)際的元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模時(shí)，也可能由于尾指針已超越向量空間的上界而不能做入隊(duì)操作。該現(xiàn)象稱為"假上溢"現(xiàn)象。

鏈隊(duì)列在隊(duì)列的形成過程中，可以利用線性鏈表的原理，來生成一個(gè)隊(duì)列。

基于鏈表的隊(duì)列，要?jiǎng)討B(tài)創(chuàng)建和刪除節(jié)點(diǎn)，效率較低，但是可以動(dòng)態(tài)增長。

隊(duì)列采用的FIFO(first in first out)，新元素（等待進(jìn)入隊(duì)列的元素）總是被插入到鏈表的尾部，而讀取的時(shí)候總是從鏈表的頭部開始讀取。每次讀取一個(gè)元素，釋放一個(gè)元素。所謂的動(dòng)態(tài)創(chuàng)建，動(dòng)態(tài)釋放。因而也不存在溢出等問題。由于鏈表由結(jié)構(gòu)體間接而成，遍歷也方便。

循環(huán)隊(duì)列在實(shí)際使用隊(duì)列時(shí)，為了使隊(duì)列空間能重復(fù)使用，往往對(duì)隊(duì)列的使用方法稍加改進(jìn)：無論插入或刪除，一旦rear指針增1或front指針增1 時(shí)超出了所分配的隊(duì)列空間，就讓它指向這片連續(xù)空間的起始位置。自己真從MaxSize-1增1變到0，可用取余運(yùn)算rear%MaxSize和front%MaxSize來實(shí)現(xiàn)。這實(shí)際上是把隊(duì)列空間想象成一個(gè)環(huán)形空間，環(huán)形空間中的存儲(chǔ)單元循環(huán)使用，用這種方法管理的隊(duì)列也就稱為循環(huán)隊(duì)列。除了一些簡單應(yīng)用之外，真正實(shí)用的隊(duì)列是循環(huán)隊(duì)列。

在循環(huán)隊(duì)列中，當(dāng)隊(duì)列為空時(shí)，有front=rear，而當(dāng)所有隊(duì)列空間全占滿時(shí)，也有front=rear。為了區(qū)別這兩種情況，規(guī)定循環(huán)隊(duì)列最多只能有MaxSize-1個(gè)隊(duì)列元素，當(dāng)循環(huán)隊(duì)列中只剩下一個(gè)空存儲(chǔ)單元時(shí)，隊(duì)列就已經(jīng)滿了。因此，隊(duì)列判空的條件時(shí)front=rear，而隊(duì)列判滿的條件時(shí)front=(rear+1)%MaxSize。