順序隊列
順序隊列
()順序隊列的定義
隊列的順序存儲結構稱為順序隊列順序隊列實際上是運算受限的順序表
() 順序隊列的表示
①和順序表一樣順序隊列用一個向量空間來存放當前隊列中的元素
②由於隊列的隊頭和隊尾的位置是變化的設置兩個指針front和rear分別指示隊頭元素和隊尾元素在向量空間中的位置它
們的初值在隊列初始化時均應置為
() 順序隊列的基本操作
①入隊時將新元素插入rear所指的位置然後將rear加
②出隊時刪去front所指的元素然後將front加並返回被刪元素
注意
①當頭尾指針相等時隊列為空
②在非空隊列裡隊頭指針始終指向隊頭元素尾指針始終指向隊尾元素的下一位置
順序隊列基本操作【 參見動畫演示 】
()順序隊列中的溢出現象
① 下溢現象
當隊列為空時做出隊運算產生的溢出現象下溢是正常現象常用作程序控制轉移的條件
② 真上溢現象
當隊列滿時做進棧運算產生空間溢出的現象真上溢是一種出錯狀態應設法避免
③ 假上溢現象
由於入隊和出隊操作中頭尾指針只增加不減小致使被刪元素的空間永遠無法重新利用當隊列中實際的元素個數遠遠小於
向量空間的規模時也可能由於尾指針已超越向量空間的上界而不能做入隊操作該現象稱為假上溢現象
【例】假設下述操作序列作用在初始為空的順序隊列上
EnQueueDeQueueEnQueueDeQueue…
盡管在任何時刻隊列元素的個數均不超過但是只要該序列足夠長事先定義的向量空間無論多大均會產生指針越界錯誤
From:http://tw.wingwit.com/Article/program/sjjg/201311/23923.html