聊聊資料結構｜佇列之順序儲存

ecx如何按列順序選取三十個資料

今天我們來聊聊佇列這種資料結構。

佇列是一種只允許在一端插入資料，在另一端刪除資料的線性表，插入資料的一端稱作隊尾，刪除資料的一端稱作隊頭。佇列是一種先進先出的資料結構，也就是FIFO結構。關於佇列，生活中有很多例子可以加深我們對它的理解。比如我們排隊買飯，排在前面的人會先買到飯，然後離開 隊伍，自己找座位坐下吃飯。後面來到的人只能排在隊伍的後面等待著買飯。每當排在最前面的人打好了飯，大家就都會向前移動一個位置。

既然我們已經有了普通的線性表，幹嘛又搞出個佇列這種結構呢？其實主要是因為在某些場景使用佇列會更加符合我們的需求。比如網上購票，先提交訂單的使用者應該優先獲得購票權，後面下單的使用者就得先排隊等著。這種情形，就適合用佇列這種結構來儲存資料，先來的先處理。

線性表有順序結構和鏈式結構之分，佇列作為特殊的線性表，也有這兩種儲存方式，我們先來看看佇列的順序儲存結構。

佇列的順序儲存結構和線性表的表示法一致，只不過在對順序佇列操作時，刪除元素只能從隊頭刪除，新增元素只能從隊尾新增。我們在刪除元素時，可以將後面的元素都依次往前移動一個位置，但是這樣子在效能上會有些低。其實我們如果能夠確定哪些空間是閒置的，那就沒有必要每次刪除元素都把元素往前移動了。基於此想法，就有了迴圈佇列（這裡是指順序儲存的迴圈佇列，鏈式結構中也可以有迴圈佇列）。

我們來定義一下迴圈佇列的順序儲存結構：

typedef struct SqQueue{

int data［SIZE］；

int front；//用於表示隊頭所在的位置

int rear；//用於表示隊尾所在的位置

}SqQueue；

在使用某種資料結構時，我們一定要先對資料結構內的元素進行初始化操作，然後才能進行一些增刪改查的操作。當我們建立佇列時，預設使隊頭和隊尾都指向陣列第一個位置，也就是下標為0的地方。

Status initQueue（SqQueue *q）{

q->front=0；

q->rear=0；

return OK；

}

元素入隊的程式碼如下：

Status enQueue（SqQueue *q，int e）{

//佇列滿了

if（（q->rear+1）%SIZE==q->front）{

return ERROR；

}

q->data［q->rear］=e；

q->rear=（q->rear+1）%SIZE；

return OK；

}

元素出隊的程式碼如下：

Status deQueue（SqQueue *q，int *e）{

//佇列為空

if（q->front==q->rear）{

return ERROR；

}

e=q->data［q->front］；

q->front=（q->front+1）%SIZE；

return OK；

}

另外，在我們計算迴圈佇列的長度時，我們可以使用以下公式：

（q->rear-q->front+SIZE）%SIZE

迴圈佇列相對於普通的順序佇列，避免了元素出隊時移動元素的麻煩，但是順序儲存結構都可能會面臨儲存空間不夠的問題，這種情況下，我們就要考慮使用鏈式儲存結構了，我們下一篇再對此進行講解。