queue[線性表]

queue[線性表]

佇列是一種特殊的線性表,是一種先進先出(FIFO)的數據結構。它只允許在表的前端(front)進行刪除操作,而在表的後端(rear)進行插入操作。進行插入操作的端稱為隊尾,進行刪除操作的端稱為隊頭。佇列中沒有元素時,稱為空佇列。

基本信息

簡介

在佇列這種數據結構中,最先插入在元素將是最先被刪除;反之最後插入的元素將最後被刪除,因此佇列又稱為“先進先出”(FIFO—first in first out)的線性表。

佇列空的條件:front=rear

佇列滿的條件: rear = MAXSIZE

佇列可以用數組Q[1…m]來存儲,數組的上界m即是佇列所容許的最大容量。在佇列的運算中需設兩個指針:head,隊頭指針,指向實際隊頭元素的前一個位置;tail,隊尾指針,指向實際隊尾元素所在的位置。一般情況下,兩個指針的初值設為0,這時佇列為空,沒有元素。圖1 ( a)畫出了一個由6個元素構成的佇列,數組定義Q[1…10]。Q(i) i=3,4,5,6,7,8頭指針head=2,尾指針tail=8。佇列中擁有的元素個數為:L=tail-head現要讓排頭的元素出隊,則需將頭指針加1。即head=head+1這時頭指針向上移動一個位置,指向Q(3),表示Q(3)已出隊。見圖1 (b)。如果想讓一個新元素入隊,則需尾指針向上移動一個位置。即tail=tail+1這時Q(9)入隊。當隊尾已經處理在最上面時,即tail=10,如果還要執行入隊操作,則要發生"上溢",但實際上佇列中還有三個空位置,所以這種溢出稱為"假溢出"。

克服假溢出的方法有兩種。一種是將佇列中的所有元素均向低地址區移動,顯然這種方法是很浪費時間的;另一種方法是將數組存儲區看成是一個首尾相接的環形區域。當存放到n地址後,下一個地址就"翻轉"為1。在結構上採用這種技巧來存儲的佇列稱為循環佇列。

佇列和棧一樣只允許在端點(前端或者後端)處插入和刪除元素。

循環隊的入隊算法如下:

1、tail=tail+1;

2、若tail=n+1,則tail=1;

3、若head=tail尾指針與頭指針重合了,表示元素已裝滿佇列,則作上溢出錯處理;

4、否則,Q(tail)=X,結束(X為新入出元素)。

佇列和棧一樣,有著非常廣泛的套用。

佇列的基本運算

(1)初始化佇列 Qini (Q)

(2)入隊 QADD(Q,X)

(3)出隊 QDel(Q,X)

(4)判斷佇列是否為空 qempty(Q)

(5)判斷佇列是否為滿qfull(Q)

C++中的套用

語法

queue類是為程式設計師提供了一個佇列的功能的容器適配器,具體而言,一個FIFO(先入先出)的數據結構

在頭檔案<queue>中定義(在程式開頭輸入#include <queue>,切記不可寫為#include <queue.h>)。

原型

成員函式

q.empty()判斷佇列q是否為空,當佇列q空時,返回true;否則為false(值為0(false)/1(true))。
q.size()訪問佇列q中的元素個數。不可寫成sizeof(q)或size(q)
q.push()會將一個元素a置入佇列q中
q.front()返回佇列q內的第一個元素(也就是第一個被置入的元素)。(不可寫成front(q))
q.back()會返回佇列q中最後一個元素(也就是最後被插入的元素)。(不可寫成back(q))
q.pop()會從佇列q中移除第一個元素。(不可寫成pop(q))

•注意:pop()雖然會移除下一個元素,但是並不返回它。

•front()和back()返回下一個元素但並不移除該元素。

•在stack庫中的函式與queue很類似,但是stack中要返回元素時,只能返回最後一個元素,且函式名不一樣(stack中為s.top()),需要區分。

相關詞條

相關搜尋

熱門詞條