在上一篇文章中悯辙，我們介紹了自定義的鏈式棧結(jié)構(gòu)及其接口的實現(xiàn)方式。這篇文章里货裹，我們來介紹如何實現(xiàn)自定義的順序隊列嗤形。
順序隊列結(jié)構(gòu)定義
在順序隊列中喉镰，我們采用一維數(shù)組進行存儲隊列元素浓体，為充分利用內(nèi)存空間崇众，我們采取 循環(huán)隊列 形式對元素進行組織管理嘉涌。
我們首先給出順序結(jié)構(gòu)的定義及其接口聲明蒜鸡，如下代碼所示：
#ifndef _SQQUEUE_H_
#define _SQQUEUE_H_
#include <cstdio>
#include <cstdlib>
#include <cstring>
typedef int POSITION;
struct stQueue {
size_t MAXNUM;
size_t length;
ELEMTYPE *buffer;
POSITION head, rear;
};
typedef struct stQueue * Psqueue;
Psqueue create(int num);
bool enqueue(Psqueue queue, ELEMTYPE x);
bool dequeue(Psqueue queue);
bool front(Psqueue queue, ELEMTYPE &x);
bool clear(Psqueue queue);
bool length(Psqueue queue);
bool isEmpty(Psqueue queue);
bool isFull(Psqueue queue);
bool destroy(Psqueue &queue);
bool print(Psqueue queue);
#endif
在 sqqueue.h 頭文件中灵疮，給出了隊列的結(jié)構(gòu)體定義敢课，該結(jié)構(gòu)包含如下結(jié)構(gòu)體成員變量：
- MAXNUM：表示隊列元素緩沖區(qū)長度快压，亦即表示隊列最多可容納元素個數(shù)拯田；
- length：表示隊列中當(dāng)前元素個數(shù)历造，length <= MAXNUM；
- buffer：表示隊列用于存儲元素的緩沖區(qū)首地址船庇；
- head：表示隊頭在緩沖區(qū)的下標吭产；
- rear：表示隊尾在緩沖區(qū)的下標；
判斷循環(huán)隊列 隊滿鸭轮、 隊空 條件分別為：
- 隊滿：(rear + 1)%MAXNUM == head
- 隊空：head == rear
或者根據(jù) stqueue 結(jié)構(gòu)體中 length 與 MAXNUM的關(guān)系進行判斷：
- 隊滿：length == MAXNUM
- 隊空：length == 0
順序隊列各接口實現(xiàn)
下面我們來依次介紹順序循環(huán)隊列的各接口實現(xiàn)臣淤。
創(chuàng)建順序隊列-create接口
創(chuàng)建順序隊列操作如下圖所示，可以分為兩步：
- 分配順序隊列結(jié)構(gòu)體空間窃爷，并初始化結(jié)構(gòu)體成員邑蒋；
- 分配順序隊列元素存儲空間；
分配順序隊列結(jié)構(gòu)體以及分配順序表元素存儲空間按厘，均通過動態(tài)內(nèi)存分配函數(shù) malloc 進行操作即可医吊；此外，初始化結(jié)構(gòu)體成員亦比較簡單刻剥，length 初始化為 0遮咖，head、rear也均初始化為 0造虏。
#include "sqqueue.h"
#include <iostream>
using namespace std;
Psqueue create(int num)
{
Psqueue queue = (Psqueue) malloc(sizeof(struct stQueue));
if (queue != NULL)
{
queue->buffer = (ELEMTYPE *) malloc(sizeof(ELEMTYPE)*num);
if (queue->buffer != NULL)
{
queue->MAXNUM = num;
queue->length = 0;
queue->head = 0;
queue->rear = 0;
return queue;
}
free(queue);
}
return NULL;
}
以上代碼對應(yīng)文件 sqqueue.cpp御吞，需要注意的是，初始化 head 和 rear 下標均為 0漓藕；此外陶珠，當(dāng)分配 buffer 緩沖區(qū)失敗時，我們需要將第1步分配的順序隊列結(jié)構(gòu)體空間也釋放掉享钞。
順序隊列判空-isEmpty接口
在實現(xiàn)順序隊列 入隊(enqueue)揍诽、出隊(dequeue) 操作前诀蓉，我們先來實現(xiàn)順序隊列的 判空(isEmpty) 及 判滿(isFull) 操作。
根據(jù)本文前面的討論暑脆，判斷隊列為空的條件可以是：
head == rear 或 length == 0
以下為 isEmpty 操作接口的實現(xiàn)：
bool isEmpty(Psqueue queue)
{
if (queue == NULL)
{
return false;
}
// method 1
//return queue->length == 0;
// method 2
return queue->head == queue->rear;
}
注: 當(dāng)傳遞的 queue 指針為空時渠啤，需返回為 true，大家可以思考下為什么添吗。
順序隊列判滿-isFull接口
順序隊列判滿操作的條件是：
(rear + 1)%MAXNUM == head 或 length == MAXNUM
兩個條件是有所區(qū)別的沥曹，第一個條件下，實際上隊列元素緩沖區(qū)還剩余 1 個元素存儲空間碟联；第二個條件下妓美，緩沖區(qū)所有元素存儲空間都被充分利用。
以下是 isFull 操作接口的實現(xiàn)：
bool isFull(Psqueue queue)
{
if (queue == NULL)
{
return true;
}
// method 1
//return queue->length == queue->MAXNUM;
// method 2
return (queue->rear+1)%queue->MAXNUM == queue->head;
}
順序隊列入隊-enqueue操作
在順序隊列為非滿時鲤孵，順序隊列才可進行入隊操作壶栋。
此外，由 圖1 及 圖2 可知 rear指向的緩沖區(qū)當(dāng)前為隊尾普监，且該位置尚未存儲元素贵试。因此，元素入隊時鹰椒，先將元素存儲在 rear 指向的緩沖區(qū)中锡移，然后再改變 rear 指向新隊尾。
bool enqueue(Psqueue queue, ELEMTYPE x)
{
if (queue == NULL)
{
return false;
}
if (isFull(queue))
{
return false;
}
queue->buffer[queue->rear] = x;
queue->rear = (queue->rear + 1) % queue->MAXNUM;
queue->length = queue->length + 1;
return true;
}
元素入隊后漆际，改變 rear 隊尾下標時，需考慮 rear + 1 >= MAXNUM 的情況(可通過 % 取模運算實現(xiàn))夺饲。
順序隊列出隊-dequeue操作
與入隊操作相反奸汇，當(dāng)順序隊列為非空時，才能進行元素出隊操作往声。
元素出隊后擂找，需要更新 head 隊頭下標，往后移動一個位置浩销，同時也需要考慮當(dāng) head 已經(jīng)在緩沖區(qū)尾部時進行 +1 操作需要將 head 重新移動到緩沖區(qū)頭部(可通過 % 取模運算實現(xiàn))贯涎。
bool dequeue(Psqueue queue)
{
if (queue == NULL)
{
return false;
}
if (isEmpty(queue))
{
return false;
}
queue->length = queue->length - 1;
queue->head = (queue->head + 1) % queue->MAXNUM;
return true;
}
取隊頭元素-front操作
當(dāng)順序隊列不為空時，可以取當(dāng)前隊列隊頭元素慢洋。取隊頭元素并不影響當(dāng)前順序隊列狀態(tài)塘雳。
首先，來看看 front 接口操作聲明：
bool front(Psqueue queue, ELEMTYPE &x);
front 操作中我們使用了C++語言的 引用類型 存放順序隊列隊頭元素普筹。當(dāng) front 操作的返回值為 true 時败明，ELEMTYPE 類型的引用變量才被賦值為順序隊列隊頭元素。
以下是 front 接口操作的實現(xiàn)：
bool front(Psqueue queue, ELEMTYPE &x)
{
if (queue == NULL)
{
return false;
}
if (isEmpty(queue))
{
return false;
}
x = queue->buffer[queue->head];
return true;
}
完成上述幾個接口后太防，應(yīng)該可以編寫測試代碼對其進行測試了(盡可能早的對項目進行測試)妻顶，由于篇幅的原因，這里就不在贅述。
清空隊列-clear接口
由于是順序隊列讳嘱，因此清空隊列只需要對隊列的 head幔嗦、 rear 下標進行更新即可，以下給出 clear 接口操作的實現(xiàn)：
bool clear(Psqueue queue)
{
if (queue == NULL)
{
return false;
}
queue->head = 0;
queue->rear = 0;
queue->length = 0;
return true;
}
隊列長度-length接口
由于在順序隊列結(jié)構(gòu)體中沥潭，我們使用 length 保存當(dāng)前隊列中的元素個數(shù)邀泉，因此求隊列長度的操作反而變得簡單直接了。
唯一需要注意的是叛氨，如果當(dāng)順序隊列指針 queue 為空時呼渣，length 接口返回值為 -1。
int length(Psqueue queue)
{
if (queue == NULL)
{
return -1;
}
return queue->length;
}
銷毀隊列-destroy接口
銷毀隊列需要做與創(chuàng)建隊列相反的事情：
- 釋放隊列元素緩沖區(qū)寞埠；
- 釋放隊列結(jié)構(gòu)體所在內(nèi)存空間屁置；
bool destroy(Psqueue &queue)
{
if (queue == NULL)
{
return false;
}
free((queue)->buffer);
free(queue);
queue = NULL;
return true;
}
在 destroy 接口中(queue 類型為Psqueue引用類型)，完成相關(guān)內(nèi)存空間釋放操作后仁连，我們還將 queue 指針置為空蓝角，避免其變成野指針。
打印隊列元素-print接口
最后我們給出打印隊列所有元素的接口饭冬，為了直觀方便使鹅，我們以如下格式顯示隊列元素及隊列狀態(tài)：
a b c d e f g h i j k l * * *
H R
* * * d e f g h i j k l * * *
H R
q * * d e f g h i j k l m n p
R H
其中，H昌抠、R 分別表示隊列的隊頭指針和隊尾指針患朱；*號表示當(dāng)前緩沖區(qū)未存儲隊列元素。
以下是 print 接口操作的實現(xiàn)：
bool print(Psqueue queue)
{
POSITION p;
char *index = NULL;
int flag = 0;
if (queue == NULL)
{
return true;
}
p = 0;
#ifdef DEBUG
index = (char *) malloc(sizeof(char)*queue->MAXNUM);
if (index != NULL)
{
memset(index, ' ', queue->MAXNUM);
index[queue->rear] = 'R';
index[queue->head] = 'H';
}
#endif
if (queue->rear < queue->head)
{
flag = 1;
}
for (p = 0; p < queue->MAXNUM; p++)
{
if (flag && p >= queue->rear && p < queue->head)
{
printf("* ");
}
else if (!flag && (p < queue->head || p >= queue->rear))
{
printf("* ");
}
else
{
printf("%-2c", queue->buffer[p]);
}
}
printf("\n");
#ifdef DEBUG
if (index != NULL)
{
for (p = 0; p < queue->MAXNUM; p++)
{
printf("%-2c", index[p]);
}
}
printf("\n");
#endif
if (index != NULL)
{
free(index);
index = NULL;
}
return true;
}
測試代碼
完成順序隊列的所有接口后炊苫，我們給出其對應(yīng)的測試文件 main.cpp裁厅。 在該文件中，我們對 create侨艾，enqueue执虹，dequeue，isEmpty唠梨，top袋励，print，destroy 等接口進行了直接測試当叭，而其他接口則進行了間接的測試茬故。
#include "sqqueue.h"
int main ()
{
Psqueue queue;
ELEMTYPE x;
int i;
queue = create(15);
if (queue != NULL)
{
for (i = 0; i < 12; i++)
{
enqueue(queue, 'a'+i);
}
print(queue);
for (i = 0; i < 3; i++)
{
dequeue(queue);
}
print(queue);
for (i = 0; i <= 3; i++)
{
enqueue(queue, '1' + i);
}
print(queue);
while (!isEmpty(queue))
{
dequeue(queue);
}
print(queue);
while (!isFull(queue))
{
enqueue(queue, 'X');
}
print(queue);
destroy(queue);
print(queue);
}
return 0;
}
對項目進行編譯后，程序運行結(jié)果如下所示：
[localhost@queue xgqin]$g++ -o sqQueueTest main.cpp sqqueue.cpp -DDEBUG -g
[localhost@queue xgqin]$ ./sqQueueTest
a b c d e f g h i j k l * * *
H R
* * * d e f g h i j k l * * *
H R
4 * * d e f g h i j k l 1 2 3
R H
* * * * * * * * * * * * * * *
H
* X X X X X X X X X X X X X X
R H
至此科展，我們完成了自定義順序循環(huán)隊列的定義及接口實現(xiàn)均牢。
