堆疊與佇列

使用陣列建立佇列

#define MAXQUEUE 10 /* 佇列的最大容量

*/ int queue[MAXQUEUE]; /* 佇列的陣列宣告

*/ int front = -1; /* 佇列的前端

*/ int rear = -1; /* 佇列的尾端

*/ extern intisQueueEmpty();

externintdequeue();

使用陣列建立佇列-存入元素

函數enqueue()是將資料存入佇列的rear尾端，其步驟如下所示：

– Step 1：將尾端指標rear往前移動，也就是將指標 rear加1。

– Step 2：將值存入尾端指標rear所指的陣列元素。queue[++rear] = d;

使用陣列建立佇列-取出元素

函數dequeue()是從佇列的front前端取出資料，其步驟如下所示：

– Step 1：檢查佇列是否已空，如果沒有：

– Step 2：將前端指標front往前移，即把其值加1

– Step 3：取出前端指標front所指的陣列元素

return queue[++front];

使用陣列建立佇列-佇列是否已空

在取出資料5後，指標front(4)與佇列rear指標(5)相差1，表示目前尚有1個元素，front 指標是指向目前佇列中第1個元素的前一個元素。•換句話說，只需比較兩個front和rear指標是否相等，就可以知道佇列是否已空。•如果front指標是指向佇列中的第1個元素，當取出資料6後，front指標就已經和指標 rear相同，都是索引值5。

使用陣列建立佇列-問題

陣列實作的佇列有一個大問題，因為front和 rear變數的指標都是往同一個方向遞增，如果rear指標到達一維陣列的邊界 MAXQUEUE-1，就算佇列尚有一些空間，也需要位移佇列元素，才有空間存入其它佇列元素，如下圖所示：