隊列
隊列簡稱隊, 也是一種操作受限的線性表, 隻允許在表的一端進行插入, 而在表的另一端進行删除.其特點為”先進先出(FIFO)”,故又稱為先進先出的線性表,簡單隊列如圖所示:
循環隊列
順序隊列有一個先天不足, 那就是空間使用率不高, 會産生”假溢出”現象,即:其實隊列中還有空閑的空間以存儲元素, 但我們在判斷隊列是否還有空間時, 隊列告訴我們隊列已經滿了, 是以這種溢出并不是真正的溢出, 在data數組中依然存在可以放置元素的空位置, 是以說這是一種”假溢出”;
于是我們就引入了循環隊列的概念, 将順序隊列臆造為一個環狀的空間, 即把存儲隊列元素的表從邏輯上看成一個環, 稱為循環隊列,其示意圖如下:
注意:如圖中所示,我們的循環隊列為了在實作上的便利, 會有一個位置的空閑, m_front(如圖中的front)指針總會指向一個元素值為空的位置,是以(m_front+1)%capacity才真正的指向隊首元素, 而m_rear(圖中為rear)才指向一個真實存在的隊尾元素;
補充說明
當隊列已滿時的兩類擴充操作:
擴充之後的記憶體布局:
附-測試代碼: