當前位置:編程學習大全網 - 源碼破解 - 什麽是循環隊列?

什麽是循環隊列?

對於隊列最好的方法是使用鏈表實現,因為對於數組來說,隊列可能會出現下面這種情況:

如圖所示,不可以繼續添加元素,否則會造成數組越界而遭致程序出錯。然而此時又不應該擴充數組,因為還有大量實際空間未被占用。   

此時我們應該如何解決這個問題呢?我們將其實現為循環隊列。

何謂循環隊列?首先我們要說明的是循環隊列仍然是基於數組實現的。但是為了形象化的說明問題,我們如下圖所示

 1.圖中有兩個指針(其實就是兩個整數型變量,因為在這裏有指示作用,所以這裏理解為指針)front、rear,壹個指示隊頭,壹個指示隊尾。   

2.rear和front互相追趕著,這個追趕過程就是隊列添加和刪除的過程,如果rear追到head說明隊列滿了,如果front追到rear說明隊列為空。

3.我們把它掰彎,用的是求余,這樣兩個值就不會跑出最大範圍,並且可以實現彎曲的效果,所以說對於循環隊列我們必須給定最大值MAXQSIZE。

這其實是我們臆想的,反正我們要做的就是利用循環來解決空間浪費的問題。  

當添加壹個元素時,(rear+1)%MAXQSIZE; //理解為什麽求余?

當刪除壹個元素時,(front+1)%MAXQSIZE;//理解為什麽求余?

當rear=front的時候,隊列可能是滿,也可能是空。

因為存在滿和空兩種情況,我們需要分別判斷:

滿:當隊列添加元素到rear的下壹個元素是head的時候,也就是轉圈子要碰頭了,我們就認為隊列滿了。(Q.rear+1)%MAXSIZE=Q.front

空:當隊列刪除元素到head=rear的時候,我們認為隊列空了。Q.rear==Q.front,不壹定為0。

圖示:

  • 上一篇:PHP源代碼與ASP源代碼有什麽不同呀
  • 下一篇:現在學什麽技術將來好找工作呢
  • copyright 2024編程學習大全網