Day-21 队列(Queue)与循环对列(Circular Queue)

队列(queue)介绍

队列就如同堆叠一般，是一种线性表，与堆叠不同的地方在於，堆叠的push和pop操作都是在栈顶(Top)的地方进行操作，而队列则是插入元素在一端进行，而删除则是在另外一端执行。

队列的基本操作为Enqueue(入队)，他是在表的末端(称为队尾(rear))插入元素。另一个操作为Dequeue(出队)，作用为删除(或是回传)表头(又称为(front))的元素。

而元素推入Queue，是遵循着先进先出的原则(First In First Out)。假设我们依序将2和3进行Enqueue，看起来会像是以下

1. 将2进行Enqueue
   
2. 将3进行Enqueue(在队尾(rear)插入元素)
   
3. 进行Dequeue(删除头(front)元素)
   
4. 进行Dequeue
   

我们可以观察到，2为最先进入Queue的元素(Enqueue)，也是最先出队(Enqueue)的元素，也就是所谓First In First Out的特性。

队列的概念与操作

我们实作队列无论使用串列还是阵列的方式，对其进行的任何操作皆为，以下为如何使用阵列实作出队列。

首先，我们需要阵列Queue，以及位置front和rear，他们代表着Queue这个阵列的头端和末端，除此之外，我们还需要纪录阵列的大小，也就是阵列中元素的多寡size。所有这一些资讯作为结构(struct)的成员(member)并包装起来

首先，先针对入队(Enqueue)进行分析

入队(Enqueue)

其实我们所进行的事情，就只是改变队尾(rear = rear + 1)，并将元素放入队尾(Queue[rear] = X)，没有涉及到需要移动到整个阵列的操作，因此，时间复杂度为。就像是排队一样，来的人只要接在原来排队人群的後面就可以了。

出队(Dequeue)

接着，针对出队(Dequeue)进行分析，出队为将头(front)元素移除的操作，就像是排队一样，排头的人走了，那其余的人就必须往前进一格，也因此出队会涉及到整个阵列的移动，时间复杂度为。

原本排队情形

排头的人取得商品後走掉了

後面的人需要跟着往前进一格

以Queue阵列的结构图演示就如同以下

但出队需要的时间复杂度为，有没有办法将它简化到，其实是有办法的，只要我们不要限制队头(front)一定要在0号的位置，也就是排头的位置，就可以不用涉及阵列所有元素移动的操作了，如同下图所示

为了避免当只有一个元素时，队头(front)和队尾(rear)重合的问题，我们使用两个指标进行处理，front指标指向Queue阵列的队头，==rear指向Queue阵列的队尾元素的下一个位置==，如下图所示

执行Dequeue

执行Dequeue

执行Dequeue

我们可以发现，当front和rear重合时，就表示Queue为空的

空间不足的问题，与假溢出(False overflow)问题

下图为长度为5的阵列，经过入队(Enqueue)a1,a2,a3,a4的操作後的情况

然後我们将a1,a2出队(Dequeue)

在将a5入队(Enqueue)

我们会发现，当我们执行入队(Enqueue)时，需要将rear + 1，他会跑到阵列界线以外的地方，造成错误，而且我们还发现到，当我们要将元素入队时，如将a6入队，Queue明明还有0号和1号的位置，却无法将元素加入，因为会有rear越界的问题，而这个问题，我们称之为假溢出问题(False overflow)。

解决假溢出问题，使用循环阵列(circular array)

要解决假溢出的问题，其实我们只要将rear跑到阵列界线时，再往下走一格会回到阵列的头就可以解决了，也就是使阵列的头尾相接，这种阵列我们称之为循环阵列(circular array)。

而回到刚刚将a6入队(Enqueue)的问题，我们使用循环阵列就能够顺利地解决了，原本将a5入队会发生的状况使用循环阵列後如下图所示

然後我们将a6入队

接着将a7入队

此时我们又发现新的问题了，前面说过，当front和rear相等时，表示Queue为空的，在单向时行得通，但在循环阵列时就发生问题了，这里我们的front和rear发生了重合，但是Queue却不为空，我们要如何解决这个问题?

常见判断Queue是为满(Full)还是空(NULL)的方法，front和rear的特殊对应关系

下面我们会介绍常见判断Queue是空还是满的方法，归纳上面的演示，由於rear有可能大於front，也有可能小於front，当rear和front只相差一个位置时，有可能是Queue满(Full)的状况，但也有可能相差了整整一圈。

我们归纳出了一下结论，如果Queue的最大长度为QueueSize，==则Queue为满(Full)的条件为，我们已下举几个例子来说明 :

Example 1.

如果QueueSize = 5

目前的front = 0，raer = 4
而我们带入
，而front恰好为零，符合
因此判断此Queue为满(Full)。P.S:对於Full的Queue，我们保留一个空的格子

Example 2.

如果QueueSize = 5

目前front = 2，rear = 1
而我们带入
，而front恰好为2，符合
因此判断此Queue为满(Full)。P.S:对於Full的Queue，我们保留一个空的格子

Example 3.

如果QueueSize = 5

目前front = 2, rear = 0
而我们带入
，符合
因此判断Queue未满。

Queue的长度问题(Queue中元素个数)

我们可以将Queue求长度的问题分为两个部分进行讨论

1. 当时，如下图
   
   此时Queue长度为rear - front，4 - 2 = 2

2. 当时，如下图
   
   长度的问题就必须分段讨论，一个为QueueSize - front，也就是5 - 2，另一段为0 + rear，也就是0 + 1，在将两者相加，得到Queue的长度。

我们综合了一下上方两种情况，得到了一个通用==计算Queue长度的公式

取得Queue最後一个元素

取得最後一个元素，我们在实作Queue时，会空出一个格子，而rear指标会指向这一个空格，真正有元素的位置是在rear的前一格(请见上图)，所以我们可能会以为最後一个元素即为Queue[rear - 1]，但事实上这是错的，如果遇到rear在0号位置，那rear - 1即会超出Queue的边界，造成违法存取的错误，因此，我们归纳出了一个公式，用来取得Queue的最後一个元素

Queue最後一个元素:

有了这一些结论後，我们就可以开始实作Queue了

单向队列的实作ADT

下面为使用阵列实作队列的ADT

#ifndef _Queue_h

Queue* InitQueue(Queue* Q);
void DestroyQueue(Queue* Q);
void ClearQueue(Queue* Q);
int IsEmpty(Queue* Q);
int GetHead(Queue* Q);
int Gettail(Queue* Q);
void EnQueue(Queue* Q, ElementType X);
void DeQueue(Queue* Q);
int QueueLengh(Queue* Q);
void PrintQueue(Queue* Q);
#endif /* _Queue_h */

/* Place in implementation file */
/* Queue implementation is a dynamically allocated array */
#define MaxQueueSize (number)

typedef struct Queue{
    int Front;
    int Rear;
    ElementType *Array;
}Queue;

IsEmpty实作

int IsEmpty(Queue Q)
{
    return QueueLenght(Q) == 0;
}

说明:如果长度为零，表示Queue为空。

IsFull实作

int IsFull(Queue Q)
{
    return QueueLenght(Q) == MaxQueueSize - 1;
}

说明:长度等於MaxQueueSize - 1，原因为Queue状态为满时，我们会空出一格。

InitQueue实作

Queue* InitQueue()
{
    Queue* Q = malloc(sizeof(Q));
    Q->array = malloc(sizeof(int) * MaxQueueSize);
    Q->front = 0;
    Q->rear = 0;
    return Q;
}

QueueLengh实作

int QueueLengh(Queue *Q)
{
    return (Q->rear - Q->front + MaxQueueSize) % MaxQueueSize;
}

说明:请参照上方说明。

EnQueue实作

int EnQueue(Queue *Q, int X)
{
    if((Q->rear + 1) % MaxQueueSize == Q->front)
    {
        return -1;
    }
    Q->array[Q->rear] = X;
    Q->rear = (Q->rear + 1) % MaxQueueSize;
    return 0;
}

说明:
表示判断Queue是否为满，如果发现Queue已满，则无法再将元素入队(Enqueue)，回传错误码-1。

如果Queue不为满，则将元素入队(Enqueue)，也就是将元素加在Queue的尾巴(rear)，并改变rear的位置。

DeQueue实作

int DeQueue(Queue* Q)
{
    int front_value;
    if(Q->front == Q->rear)
    {
        return -1;
    }
    front_value = Q->array[Q->front];
    Q->front = (Q->front + 1) % MaxQueueSize;

    return front;
}

说明:
当front和rear相等时，即表示Queue为空(注意: 这是单向Queue，非循环Queue)。

如果Queue不为空，则先将Queue队头(front)的元素存入front_value中，并改变front的索引号

之後回传原先Queue头元素，也就是front_value。

printQueue实作

void printQueue(Queue *Q)
{
    for(int i = 0; i < QueueLength(Q); i++)
    {
        if(i >= 1)
        {
            printf("%s", "->");
        }
        printf("%d", Q->array[i]);
    }
}

DestroyQueue实作

void DestroyQueue(Queue* Q)
{
    free(Q->array);
    free(Q);
}

GetTail实作

int GetTail(Queue* Q)
{
    return Q->value[Q->rear - 1 + MaxQueueSize] % MaxQueueSize; 
}

Queue实作范例程序码

#include <stdio.h>
#include <stdlib.h>
#define MaxQueueSize 10

typedef struct Queue{
    int front;
    int rear;
    int *array;
}Queue;

Queue* InitQueue(void);
void DestroyQueue(Queue* Q);
void ClearQueue(Queue* Q);
int IsEmpty(Queue* Q);
int IsFull(Queue* Q);
int GetHead(Queue* Q);
int GetTail(Queue* Q);
int EnQueue(Queue* Q, int X);
int DeQueue(Queue* Q);
int QueueLength(Queue* Q);
void printQueue(Queue* Q);

int main(void)
{
    Queue *Q = InitQueue();
    EnQueue(Q, 1);
    EnQueue(Q, 2);
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    DeQueue(Q);
    DeQueue(Q);
    DeQueue(Q);
    printQueue(Q);
    printf("\nThe QueueLength is %d", QueueLength(Q));
    printf("\nThe front of Queue is %d", GetHead(Q));

    DestroyQueue(Q);
}

Queue* InitQueue()
{
    Queue* Q = malloc(sizeof(Q));
    Q->array = malloc(sizeof(int) * MaxQueueSize);
    Q->front = 0;
    Q->rear = 0;
    return Q;
}

void DestroyQueue(Queue* Q)
{
    free(Q->array);
    free(Q);
}

int QueueLength(Queue *Q)
{
    return (Q->rear - Q->front + MaxQueueSize) % MaxQueueSize;
}

int EnQueue(Queue *Q, int X)
{
    if((Q->rear + 1) % MaxQueueSize == Q->front)
    {
        return -1;
    }
    Q->array[Q->rear] = X;
    Q->rear = (Q->rear + 1) % MaxQueueSize;
    return 0;
}

int DeQueue(Queue* Q)
{
    int front;
    if(Q->front == Q->rear)
    {
        return -1;
    }
    front = Q->array[Q->front];
    Q->front = (Q->front + 1) % MaxQueueSize;

    return front;
}

void printQueue(Queue *Q)
{
    for(int i = Q->front; i < Q->rear; i++)
    {
        if(i > Q->front)
        {
            printf("%s", "->");
        }
        printf("%d", Q->array[i]);
    }
}

int IsEmpty(Queue *Q)
{
    return QueueLength(Q) == 0;
}

int IsFull(Queue *Q)
{
    return QueueLength(Q) == MaxQueueSize - 1;
}

int GetHead(Queue *Q)
{
    return Q->array[Q->front];
}

int GetTail(Queue* Q)
{
    return Q->value[(Q->rear - 1 + MaxQueueSize) % MaxQueueSize]; 
}

参考资料: 大话数据结构，C语言程序设计现代方法第2版，Introduction to algorithms 3rd，图片源於网路(flaticon)