栈与队列（二）

作者: 我叫卡卡算了 | 来源:发表于2016-12-02 18:07 被阅读52次

在上一篇文章中，我们介绍了自定义的链式栈结构及其接口的实现方式。这篇文章里，我们来介绍如何实现自定义的顺序队列。

顺序队列结构定义

在顺序队列中，我们采用一维数组进行存储队列元素，为充分利用内存空间，我们采取 循环队列 形式对元素进行组织管理。

图1. 循环队列结构

我们首先给出顺序结构的定义及其接口声明，如下代码所示：

#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接口

创建顺序队列操作如下图所示，可以分为两步：

图2. 创建顺序队列

分配顺序队列结构体空间，并初始化结构体成员；
分配顺序队列元素存储空间；

分配顺序队列结构体以及分配顺序表元素存储空间，均通过动态内存分配函数 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

至此，我们完成了自定义顺序循环队列的定义及接口实现。