循环队列的实现

 循环队列的实现

在队列中也可以使用连续的内存空间存放队列元素，附设两个指针分别指向对头和队尾，初始化两个指针为0，当有元素进队时对为指针加1，有元素出对时队尾指针加1。但这样的话会有问题，就是出队列留下的地址空间就不会被利用了，且当开始分配的空间使用完时还会不停的申请空间，浪费了很对空间。若固定的空间的话队尾指针到了末尾就无法在添加元素了，而此时出队列留下的地址处还有空间无法使用。一个较好的办法是将对列构想成一个环形队列，当队尾指针到队列最后是又重最开始处使用空间，且规定队列头指针在队尾指针的下一个位置作为队列满的标志。可见队列顺序存储不能动态分配空间，需要在开始分配一个较大的空间，若无法估计队列长度，最好使用链式存储。

• 循环队列存储结构

#define OK          1
#define NULL_QUEUE      0
#define ERROR           -1

typedef struct qnode{
    elemtype        *base;
    int         front;
    int         rear;
}sqqueue;

• 初始化循环队列

int init_sqqueue(sqqueue *sq)
{
    sq->base = (elemtype *)malloc(MAXQSIZE * sizeof(elemtype));
    if (!sq->base)
        return ERROR;

    sq->front = 0;
    sq->rear = 0;

    return OK;
}

初始化时分配MAXQSIZE个元素的空间，队头和队尾下标初始化为0；

• 元素进队列

int in_sqqueue(sqqueue *sq, elemtype e)
{
    if ((sq->rear + 1) % MAXQSIZE == sq->front)
        return ERROR;
    sq->base[sq->rear] = e;
    sq->rear = (sq->rear + 1) % MAXQSIZE;
    return OK;
}

• 元素出队列

int out_sqqueue(sqqueue *sq, elemtype *e)
{
    if (sq->front == sq->rear)
        return NULL_QUEUE;

    *e = sq->base[sq->front];
    sq->front = (sq->front + 1) % MAXQSIZE;

    return OK;
}

• 取得队列长度

int get_queue_len(sqqueue sq)
{
    return (sq.rear-sq.front + MAXQSIZE) % MAXQSIZE;
}