循環隊列演算法ppt

① 數據結構與演算法06——隊列之循環隊列

與棧不同，他就是現實中排隊一樣，講究先來後到，即 先進先出 。

打個比方，你告訴朋友我們做地鐵去西湖，你輸入 " s-u-b ", 如果按照棧 先入後出後入先出 的方式，朋友會收到 b-u-s , what？有地鐵，我們幹嘛做兩個小時的汽車？？？ 隊列就可以讓朋友按你輸入的順序依次收到 s-u-b 。

簡單的看一下隊列，是線性結構，想到什麼？非常熟悉的 線性表 ，有兩種存儲結構， 順序存儲和鏈式存儲 。
我們今天先講一講隊列的順序存儲結構—— 循環隊列

但是，，，如果如下圖，出隊到只剩最後一個元素，front和rear又都指向了一個同元素，而且僅在隊尾，又要認為隊列為空？不可能啊，明明最後一塊存儲單元還有一個元素，而且卻不能繼續入隊新元素，超出了存儲范圍，如果要繼續利用前面出隊的空餘空間，又該怎麼用？

如果 我們把隊列設計成下面這樣：

哈哈，循環了。隊尾rear指向下一個位置，而不是當前的隊尾元素。

這就是循環隊列的工作流程

將上面的過程做一下整理：

指定隊列最大存儲5個單元，方便觀看

② 求循環隊列的元素個數演算法，已知front 和 rear，還有容量數，怎麼求隊列中的循環元素個數

如果是用數組實現的 用隊尾減隊頭再模數組長度；如果是鏈表 就要有個計數變數了。

front為對頭指針，rear為對尾指針，n為隊列最大元素個數。隊列元素個數=(rear-front+1+n)%n %是求余數。

循環隊列的元素個數計算公式：

如果rear<front結果是rear-front+maxsize；

如果rear>front結果是rear-front；

為了用一個表達式同時表達兩者，用(rear-front+maxsize)%maxsize；

假設maxsize=10；

rear=1 front=9，那麼結果是2；

rear=9 front=1，那麼結果是8。

(2)循環隊列演算法ppt擴展閱讀

循環隊列中，由於入隊時尾指針向前追趕頭指針；出隊時頭指針向前追趕尾指針，造成隊空和隊滿時頭尾指針均相等。因此，無法通過條件front==rear來判別隊列是"空"還是"滿"。

解決這個問題的方法至少有兩種：

① 另設一布爾變數以區別隊列的空和滿；

②另一種方式就是數據結構常用的： 隊滿時：(rear+1)%n==front，n為隊列長度（所用數組大小），由於rear，front均為所用空間的指針，循環只是邏輯上的循環，所以需要求余運算。

隊已滿，但是rear（5）+1=6！=front（0），對空間長度求余，作用就在此6%6=0=front（0）。

③ 在循環隊列中怎樣實現入隊和出隊操作 數據結構 C語言

入隊操作
功能：將元素 x 插入到Q的隊尾。
演算法：Status EnQueue(SqQueue &Q, QElemType e) {
if ((Q.rear+1) % MaxQsize == Q.front) return ERROR; // 隊列滿
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1) % MaxQsize;
return OK;
}
出隊操作
功能：刪除Q的隊頭元素，並返回其值。
演算法： Status DeQueue(SqQueue &Q, QElemType &e) {
if (Q.front == Q. rear) return ERROR; // 隊列空
e = Q.base[Q.front];
Q.front=(Q.front+1) % MaxQsize;
return OK;
}

④ 數據結構—隊列

隊列 (queue)是一種先進先出的線性表。它只允許在表的一端進行插入，在另一端進行刪除，這如同我們日常生活中的排列是一致的，最早入隊的元素最早離開。

隊尾 (rear)是隊列中允許插入的一端， 隊頭 (front)是隊列中允許刪除的一端。

隊列如同棧一樣，也同樣有兩種存儲表示，分別是順序表示和鏈式表示。

和順序棧類似，在隊列的順序存儲結構中，除了用一組地址連續的存儲單元依次存放從隊列頭到對列尾的元素之外，需要設置兩個指針front和rear分別指示隊列頭元素和尾元素的位置。

隊列的順序存儲結構表示如下：

為方便C語言描述起見，約定：初始化建空隊列時，front=rear=0,每當插入新元素至隊尾時，「尾指針增一」，每當刪除頭元素時，「頭指針增一」。因此，在非空隊列中，頭指針始終指向隊列頭元素，而尾指針始終指向隊尾元素的下一個位置。

循環對列 是將順序隊列變成一個環狀的空間，用這種方法可以解決隊列「假溢出」問題。

「假溢出」 是指隊列實際可用空間沒有占滿，但是不能向隊列中添加新的隊尾元素，否則會出現溢出的現象的情況。

在循環隊列中，頭尾指針以及隊列元素之間的關系不發生改變，只是在循環隊列中頭尾指針「依次循環增一」的操作可用模運算實現。通過取模，頭指針和尾指針就可以在順序表空間內以頭尾銜接的方式「循環」移動。

循環隊列的基本操作演算法描述：

鏈隊是指採用鏈式存儲結構實現的隊列。通常鏈隊用單鏈表來表示，一個鏈隊顯然需要兩個分別指示對頭和隊尾的指針（分別稱為頭指針和尾指針）才能唯一確定。為了操作方便，同線性表的單鏈表一樣，為鏈隊添加頭結點，並規定頭指針始終指向頭結點。

鏈隊列存儲結構表示如下：

鏈隊操作即為單鏈表插入和刪除操作的特殊情況，只是需要進一步修改尾指針或頭指針。

鏈隊列的基本操作演算法描述：

⑤ 隊列的隊列的基本運算

（1）初始化隊列：Init_Queue(q) ，初始條件：隊q 不存在。操作結果：構造了一個空隊；
（2）入隊操作： In_Queue(q,x),初始條件： 隊q 存在。操作結果： 對已存在的隊列q，插入一個元素x 到隊尾，隊發生變化；
（3）出隊操作： Out_Queue(q,x)，初始條件: 隊q 存在且非空，操作結果： 刪除隊首元素，並返回其值，隊發生變化；
（4）讀隊頭元素：Front_Queue(q,x)，初始條件: 隊q 存在且非空，操作結果： 讀隊頭元素，並返回其值，隊不變；
（5）判隊空操作：Empty_Queue(q)，初始條件： 隊q 存在，操作結果： 若q 為空隊則返回為1，否則返回為0。 操作 類型 作用 返回值 例子 length(s) 函數 求字元串s的長度 整型 s:='123456789';
l:=length(s);{l的值為9} （s,w,k) 函數 復制s中從w開始的k位 字元串 s:='123456789';
s1:=(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中，對隊列的使用很是較完美
下面給出循環隊列的運算演算法:
(1)將循環隊列置為空
//將隊列初始化
SeQueue::SeQueue()
{ front=0;
rear=0;
cout<<init!<<endl;
}
(2)判斷循環隊列是否為空
int SeQueue::Empty()
{ if(rear==front) return(1);
else return(0);
}
(3)在循環隊列中插入新的元素x
void SeQueue::AddQ(ElemType x)
{ if((rear+1) % MAXSIZE==front) cout<< QUEUE IS FULL! <<endl;
else{ rear=(rear+1) % MAXSIZE;
elem[rear]=x;
cout<< OK!;
}
}
(4)刪除隊列中隊首元素
ElemType SeQueue::DelQ()
{ if(front==rear)
{ cout<< QUEUE IS EMPTY! <<endl; return -1;}
else{ front=(front+1) % MAXSIZE;
return(elem[front]);
}
}
(5)取隊列中的隊首元素
ElemType SeQueue::Front()
{ ElemType x;
if(front== rear)
cout<<QUEUE IS EMPTY <<endl;
else x= elem[(front+1)%MAXSIZE];
return (x);
}

⑥ 循環隊列中入隊與出隊演算法

如果循環隊列每個元素有兩個指針，一個指向其前面的元素pPre，一個指向後面的元素pNext，出對和入隊就是修改一下指針啊。
比如指向要出隊的元素的指針是 pDel,那麼出隊就應該是：
pDel->pPre->pNext = pDel->pNext;
pDel->pNext->pPre = pDel->pPre;

如果循環隊列每個元素只有一個指向其後元素的指針pNext，那麼需要遍歷整個隊列，找到要出隊元素的前一個元素，然後就和上面的演算法差不多了。

如果經常要進行出隊操作，在設計數據結構的時候還是建議每個元素使用兩個指針。