java多線程：java隊列詳解

隊列是一種特殊的線性表，它隻允許在表的前端（front）進行删除操作，而在表的後端（rear）進行插入操作。進行插入操作的端稱為隊尾，進行删除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。

在隊列這種資料結構中，最先插入的元素将是最先被删除的元素；反之最後插入的元素将是最後被删除的元素，是以隊列又稱為“先進先出”（FIFO—first in first out）的線性表。

隊列空的條件：front=rear

隊列滿的條件： rear = MAXSIZE

隊列的數組實作

隊列可以用數組Q[1…m]來存儲，數組的上界m即是隊列所容許的最大容量。在隊列的運算中需設兩個指針：head，隊 頭指針，指向實際隊頭元素的前一個位置；tail，隊尾指針，指向實際隊尾元素所在的位置。一般情況下，兩個指針的初值設為0，這時隊列為空，沒有元素。 數組定義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)已出隊。如果想讓一個新元素入隊，則需尾指針向上移動一個位 置。即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）有時候隊列中還會設定表頭結點，就是在對頭的前面還有一個結點，這個結點的資料域為空，但是指針域指向對頭元素。

（2）另外，上面的計算還可以利用下面給出的公式cq.rear=(cq.front+1)/max;

當有表頭結點時，公式變為cq.rear=(cq.front+1)/（max+1）。

隊列的連結清單實作

在隊列的形成過程中，可以利用線性連結清單的原理，來生成一個隊列。

基于連結清單的隊列，要動态建立和删除節點，效率較低，但是可以動态增長。

隊列采用的FIFO(first in first out)，新元素（等待進入隊列的元素）總是被插入到連結清單的尾部，而讀取的時候總是從連結清單的頭部開始讀取。每次讀取一個元素，釋放一個元素。所謂的動态創 建，動态釋放。因而也不存在溢出等問題。由于連結清單由結構體間接而成，周遊也友善。

隊列的基本運算

（1）初始化隊列 Qini (Q)

（2）入隊 QADD(Q,X)　（3）出隊 QDel(Q,X)

（4）判斷隊列是否為空 qempty(Q)

（5）判斷隊列是否為滿qfull(Q)

操作

類型

作用

傳回值

例子

length(s)

函數

求字元串s的長度

整型

s:='123456789';

l:=length(s);{l的值為9}

copy（s,w,k)

複制s中從w開始的k位

字元串

s1:=copy(s,3,5);{s1的值是'34567'}

val(s,k,code)

過程

将字元串s轉為數值，存在k中；code是錯誤代碼

​

var s:string;k,code:integer;

begin

s:='1234';

val(s,k,code);

write(k);{k=1234}

str(i,s)

将數值i轉為字元串s

i:=1234;

str(i,s);

write(s);{s='1234'}

Delete(s,w,k)

在s中删除從第w位開始的k個字元

s := 'Honest Abe Lincoln';

Delete(s,8,4);

Writeln(s); { 'Honest Lincoln' }

Insert(s1, S, w)

将s1插到s中第w位

S := 'Honest Lincoln';

Insert('Abe ', S, 8); { 'Honest Abe Lincoln' }

Pos(c, S)

求字元c在s中的位置

S := ' 123.5';

i :=Pos(' ', S);{i的值為1}

+

運算符

将兩個字元串連接配接起來

s1:='1234';

s2:='5678';

s:=s1+s2;{'12345678'}

在STL中，對隊列的使用很是較完美

Data_structures

▪ 集合

▪ 容器

▪ 數組

▪ 關聯數組

▪ Multimap

▪ 集

▪ 多重集

▪ 散清單

▪ 樹狀數組

▪ 清單

▪ 連結清單

▪ 隊列

▪ 堆棧

▪ 循環隊列

▪ 跳躍清單

▪ 樹

▪ 二叉查找樹

▪ 堆

▪ 線段樹

▪ 紅黑樹

▪ AVL樹

▪ 圖

▪ 有向無環圖

▪ 二進制決策圖

▪ 無向圖

擴充閱讀：