1、队列的基本概念

和堆栈一样队列也是一种特殊的线性表，队列的数据元素及数据元素间的逻辑关系和线性表是完全相同的，差别在于线性表允许在任意位置插入和删除数据元素，而队列只允许在其一端进行插入操作，在另外一端进行删除操作。队列中允许插入操作的一端称为队尾，允许删除操作的一端称为队头。指示队头的称为队头指示器或队头指针，指示队尾的称为队尾指示器或队尾指针。队列的插入操作称为入队列，删除操作称为出队列。根据队列的定义，每次入队列的数据元素都放在原来队尾数据元素之后成为新的队尾元素，每次出队列的数据元素都是原来的队头元素，这样一来最先入队列的数据元素总是最先出队列，所以队列是一种先进先出的结构。
如下所示是队列的示意图。

2、队列的抽象数据类型

2.1 数据集合

队列的数据集合可以表示为，每个数据元素的数据类型为DataType。

2.2 操作集合

• 初始化队列：QueueInitiate(Q)
• 非空判断QueueNotEmpty(Q)：判断队列Q是否为空，若为空函数返回0，否则返回1。
• 入队列QueueAppend(Q,x)：在队列Q的队尾插入数据元素x。
• 出队列QueueDelete(Q,x)：把队列Q的队头数据元素删除并由参数x带回，如果出队列成功则返回1，否则返回0。
• 取队头数据元素QueueGet(Q,x)：取队头数据元素并由参数x带回，如果取数据元素成功则返回1，否则返回0。

3、顺序队列

3.1 顺序队列的结构

顺序存储结构表示的队列称为顺序队列。
顺序队列的结构如下图所示：

3.1 顺序队列“假溢出”问题

假设一个顺序队列的最大存储空间容量为6，即MaxQueueSize=6，经入队列A，B，C，出队列A，B，入队列D，E的操作，其状态图如下所示：

如果此时再进行F，G的入队列操作，则在进行数据元素G入队列操作时，顺序队列将因队尾指针越出数组下边界而“溢出”。其状态如下图所示：

4、顺序循环队列

4.1、顺序循环队列的基本原理

假溢出是由于队尾指针rear的值和队头指针front的值不能由所定义的存储空间的最大值自动转为所定义存储空间的最小值而产生的，因此解决的方法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到MaxQueueSize-1后，再前进一个位置就自动到0。这样就不会出现顺序队列数据的头部已空出许多存储单元，但队列的队尾指针却因为数据下标越界而引出溢出的假溢出问题。

4.2、顺序循环队列的队空和队满判断问题

顺序循环队列存在队列空状态和队列满状态相同，无法去区别的问题。
假设顺序循环队列的MaxQueueSize=8，在队列的初始状态队头指针front=0，队尾指针rear=0，有front==rear，当入队列数据元素A、B、C、D、E、F、G、H后，顺序循环队列满，此时队头指针front=0，队尾指针rear=0，有front==rear；当出队列数据元素A、B、C、D、E、F、G、H后，顺序循环队列空，此时队头指针front=0，队尾指针rear=0，有front==rear。显然在顺序循环队列中不论是队列满状态还是队列空状态都有front==rear，这样一来在程序设计上我们将无法区分队列空和队列满这两种状态。

解决顺序循环队列的队列满和队列空状态判断问题通常有如下三种方法：
（1）少用一个存储单元
如果少用一个存储空间，则以队尾指针rear加1等于队头指针front为队列满的判断条件，即
(rear+1)%MaxQueueSize == front。队列空的判断条件仍然是rear==front
（2）设置一个标志位
设置标志位tag，初始设置为tag=0，每当入队列操作成功后就设置tag=1，每当出队列操作成功后就设置tag=0，此时队列空的判断条件是rear==front && tag==0，队列满的判断条件是rear==front && tag==1。
（3）设置一个计数器
设置一个计数器count，初始设置为count=0，每当入队列操作成功后就使count加1，每当出队列操作成功后就使count减1，此时队列空的判断条件是count==0，队列满的判断条件是rear==front && count>0或count==MaxQueueSize。
显然设置一个计数器的方式判断顺序循环队列的队空和队满状态最为简单也最为优化。

4.3、顺序循环队列的实现

根据上面对于顺序循环队列的分析，采用计数器方法解决队列空和队列满状态判断问题的顺序循环队列的结构体定义如下：

typedef struct {
    DataType queue[MaxQueueSize];
    int front;//队头指针
    int rear;//队尾指针
    int count;//计数器
} SeqQueue;

4.3.1、 初始化QueueInitiate(SeqQueue *queue)

void QueueInitiate(SeqQueue *queue) {
    queue->rear = 0;//初始化队尾指针下标值
    queue->front = 0;//初始化队头指针下标值
    queue->count = 0;//初始化计数器
}

4.3.2、 队列非空判断 QueueNotEmpty(SeqQueue queue)

判断队列是否为空，非空返回1，否则返回0

int QueueNotEmpty(SeqQueue queue) {
    if (queue.count != 0) {
        return 1;
    }
    return 0;
}

4.3.3、 入队列 QueueAppend(SeqQueue *queue, DataType x)

将数据元素x插入到顺序循环队列的队尾，成功返回1，失败返回0

int QueueAppend(SeqQueue *queue, DataType x) {
    if (queue->count > 0 && queue->rear == queue->front) {
        printf("队列已满无法插入数据");
        return 0;
    }
    queue->queue[queue->rear] = x;
    queue->rear = (queue->rear + 1) % MaxQueueSize;
    queue->count++;
    return 1;
}

4.3.4、 出队列 QueueDelete(SeqQueue *queue, DataType *x)

删除顺序循环队列的对头元素并赋值给x，成功返回1，否则返回0

int QueueDelete(SeqQueue *queue, DataType *x) {
    if (queue->count == 0) {
        printf("队列已空");
        return 0;
    }
    *x = queue->queue[queue->front];
    queue->front = (queue->front + 1) % MaxQueueSize;
    queue->count--;
    return 1;
}

4.3.5、 取队头数据元素 QueueGet(SeqQueue queue, DataType *x)

取顺序循环队列的当前队头的数据元素赋给x，成功返回1，否则返回0

int QueueGet(SeqQueue queue, DataType *x) {
    if (queue.count == 0) {
        printf("队列已空");
        return 0;
    } else {
        *x = queue.queue[queue.front];
        return 1;
    }
}

从面的代码我们可以看到顺序循环队列的所有操作代码中都没有循环语句，所以顺序循环队列所有操作的时间复杂度为O(1)。

5、链式队列

链式存储结构的队列称为链式队列。

5.1、链式队列的存储结构

链式队列的队头指针在队列的当前队头结点位置，队尾指针在队列的当前队尾结点位置。不带头结点的链式队列，出队列时可直接删除队头指针所指的结点，因此链式队列没有头结点时更加方便。一个不带头结点队列中有数据元素 的链式队列的结构如下图所示。其中指针front指示的是链式队列的队头结点，指针rear指示的是链式队列的队尾结点。

链式队列中结点的结构体可以定义如下：

typedef struct qnode {
    DataType data;
    struct qnode *next;
} LQNode;

为了方便参数调用，通常把链式队列的队头指针front和队尾指针rear也定义为如下结构体：

typedef struct {
    LQNode *front;
    LQNode *rear;
} LQueue;

5.2、链式队列操作的实现

5.2.1、链式队列的初始化QueueInitiate(LQueue *queue)

void QueueInitiate(LQueue *queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

5.2.2、链式队列的非空判断 QueueNotEmpty(LQueue queue)

判断链式队列是否为空，非空返回1，否则返回0

int QueueNotEmpty(LQueue queue) {
    if (queue.front == NULL) {
        return 0;
    }
    return 1;
}

5.2.3、链式队列的入队列 QueueAppend(LQueue *queue, DataType x)

将数据元素x插入到链式队列的队尾，在这里需要注意的是如果队列原本为空时，需要修改队头指针，队列原来非空时，在队尾加入一个新的结点。

void QueueAppend(LQueue *queue, DataType x) {
    LQNode *node = (LQNode *) malloc(sizeof(LQNode));
    node->data = x;
    node->next = NULL;
    if (queue->rear != NULL) {//队列原本非空时队尾添加新结点
        queue->rear->next = node;
    }
    queue->rear = node;
    if (queue->front == NULL) {
        queue->front = node;//队列原本为空时修改队头指针
    }
}

5.2.4、链式队列的出队列 QueueDelete(LQueue *queue, DataType *x)

删除队列的当前队头数据元素，并将值由参数x带回，成功返回1，否则返回0。在这里需要注意的是如果删除最后一个结点后要将队尾指针置为空。

int QueueDelete(LQueue *queue, DataType *x) {
    if (queue->front == NULL) {
        printf("队列已空无数据元素出队列");
        return 0;
    }
    LQNode *node = queue->front;
    *x = queue->front->data;
    queue->front = queue->front->next;//出队列结点脱链
    if (queue->front == NULL) {
        queue->rear = NULL;//删除最后一个结点的时候需要将队尾指针置空
    }
    free(node);
    return 1;
}

5.2.5、去队头数据元素 QueueGet(LQueue queue, DataType *x)

获取队列的当前队头数据元素，并将值由参数x带回，成功返回1，否则返回0。

int QueueGet(LQueue queue, DataType *x) {
    if (queue.front == NULL) {
        printf("队列已空无数据元素出队列");
        return 0;
    } else {
        *x = queue.front->data;
        return 1;
    }
}

5.2.6、撤销动态申请空间 Destory(LQueue queue)

void Destory(LQueue queue) {
    LQNode *node = queue.front;
    LQNode *node1;
    while (node != NULL) {
        node1 = node;
        node = node->next;
        free(node1);
    }
}

从上面的链式队列的操作代码实现可以看出链式队列除了撤销动态申请空间函数的时间复杂度为O(n)外，其他的操作的时间复杂度为O(1)。