在上一篇文章中，我们介绍了自定义的链式栈结构及其接口的实现方式。这篇文章里，我们来介绍如何实现自定义的顺序队列。
顺序队列结构定义
在顺序队列中，我们采用一维数组进行存储队列元素，为充分利用内存空间，我们采取 循环队列 形式对元素进行组织管理。
我们首先给出顺序结构的定义及其接口声明，如下代码所示：
#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 头文件中，给出了队列的结构体定义，该结构包含如下结构体成员变量：
- MAXNUM：表示队列元素缓冲区长度，亦即表示队列最多可容纳元素个数；
- length：表示队列中当前元素个数，length <= MAXNUM；
- buffer：表示队列用于存储元素的缓冲区首地址；
- head：表示队头在缓冲区的下标；
- rear：表示队尾在缓冲区的下标；
判断循环队列 队满、 队空 条件分别为：
- 队满：(rear + 1)%MAXNUM == head
- 队空：head == rear
或者根据 stqueue 结构体中 length 与 MAXNUM的关系进行判断：
- 队满：length == MAXNUM
- 队空：length == 0
顺序队列各接口实现
下面我们来依次介绍顺序循环队列的各接口实现。
创建顺序队列-create接口
创建顺序队列操作如下图所示，可以分为两步：
- 分配顺序队列结构体空间，并初始化结构体成员；
- 分配顺序队列元素存储空间；
分配顺序队列结构体以及分配顺序表元素存储空间，均通过动态内存分配函数 malloc 进行操作即可；此外，初始化结构体成员亦比较简单，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;
}
以上代码对应文件 sqqueue.cpp，需要注意的是，初始化 head 和 rear 下标均为 0；此外，当分配 buffer 缓冲区失败时，我们需要将第1步分配的顺序队列结构体空间也释放掉。
顺序队列判空-isEmpty接口
在实现顺序队列 入队(enqueue)、出队(dequeue) 操作前，我们先来实现顺序队列的 判空(isEmpty) 及 判满(isFull) 操作。
根据本文前面的讨论，判断队列为空的条件可以是：
head == rear 或 length == 0
以下为 isEmpty 操作接口的实现：
bool isEmpty(Psqueue queue)
{
if (queue == NULL)
{
return false;
}
// method 1
//return queue->length == 0;
// method 2
return queue->head == queue->rear;
}
注: 当传递的 queue 指针为空时，需返回为 true，大家可以思考下为什么。
顺序队列判满-isFull接口
顺序队列判满操作的条件是：
(rear + 1)%MAXNUM == head 或 length == MAXNUM
两个条件是有所区别的，第一个条件下，实际上队列元素缓冲区还剩余 1 个元素存储空间；第二个条件下，缓冲区所有元素存储空间都被充分利用。
以下是 isFull 操作接口的实现：
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指向的缓冲区当前为队尾，且该位置尚未存储元素。因此，元素入队时，先将元素存储在 rear 指向的缓冲区中，然后再改变 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 的情况(可通过 % 取模运算实现)。
顺序队列出队-dequeue操作
与入队操作相反，当顺序队列为非空时，才能进行元素出队操作。
元素出队后，需要更新 head 队头下标，往后移动一个位置，同时也需要考虑当 head 已经在缓冲区尾部时进行 +1 操作需要将 head 重新移动到缓冲区头部(可通过 % 取模运算实现)。
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操作
当顺序队列不为空时，可以取当前队列队头元素。取队头元素并不影响当前顺序队列状态。
首先，来看看 front 接口操作声明：
bool front(Psqueue queue, ELEMTYPE &x);
front 操作中我们使用了C++语言的 引用类型 存放顺序队列队头元素。当 front 操作的返回值为 true 时，ELEMTYPE 类型的引用变量才被赋值为顺序队列队头元素。
以下是 front 接口操作的实现：
bool front(Psqueue queue, ELEMTYPE &x)
{
if (queue == NULL)
{
return false;
}
if (isEmpty(queue))
{
return false;
}
x = queue->buffer[queue->head];
return true;
}
完成上述几个接口后，应该可以编写测试代码对其进行测试了(尽可能早的对项目进行测试)，由于篇幅的原因，这里就不在赘述。
清空队列-clear接口
由于是顺序队列，因此清空队列只需要对队列的 head、 rear 下标进行更新即可，以下给出 clear 接口操作的实现：
bool clear(Psqueue queue)
{
if (queue == NULL)
{
return false;
}
queue->head = 0;
queue->rear = 0;
queue->length = 0;
return true;
}
队列长度-length接口
由于在顺序队列结构体中，我们使用 length 保存当前队列中的元素个数，因此求队列长度的操作反而变得简单直接了。
唯一需要注意的是，如果当顺序队列指针 queue 为空时，length 接口返回值为 -1。
int length(Psqueue queue)
{
if (queue == NULL)
{
return -1;
}
return queue->length;
}
销毁队列-destroy接口
销毁队列需要做与创建队列相反的事情：
- 释放队列元素缓冲区；
- 释放队列结构体所在内存空间；
bool destroy(Psqueue &queue)
{
if (queue == NULL)
{
return false;
}
free((queue)->buffer);
free(queue);
queue = NULL;
return true;
}
在 destroy 接口中(queue 类型为Psqueue引用类型)，完成相关内存空间释放操作后，我们还将 queue 指针置为空，避免其变成野指针。
打印队列元素-print接口
最后我们给出打印队列所有元素的接口，为了直观方便，我们以如下格式显示队列元素及队列状态：
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 分别表示队列的队头指针和队尾指针；*号表示当前缓冲区未存储队列元素。
以下是 print 接口操作的实现：
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;
}
测试代码
完成顺序队列的所有接口后，我们给出其对应的测试文件 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;
}
对项目进行编译后，程序运行结果如下所示：
[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
至此，我们完成了自定义顺序循环队列的定义及接口实现。
