数据结构<七>——队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。

以下为公用代码：

typedef int    Status;
#define OK    1
#define ERROR    0
#define TRUE    1
#define FALSE    0
typedef int QElemType;

一、队列的顺序存储（循环队列）

把队列的头尾相接的顺序存储结构称为循环队列。

为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。

知识重点：

设队列的最大尺寸为QueueSize，则

空队列的条件：front == rear

队列满的条件：(rear + 1) % QueueSize == front （取模是为了整合rear与front大小为一个问题）

队列长度计算：(rear - front + QueueSize) % QueueSize

1、存储结构

#define MAXSIZE 5
// 循环队列的顺序存储结构
typedef struct
{
QElemType data[MAXSIZE];
int front;// 头指针
int rear;// 尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;

2、初始化

// 初始化一个空队列
Status InitQueue(SqQueue *Q)
{
Q->front = 0;
Q->rear = 0;
return OK;
}

代码分析：空队列时，front与rear指针相等且均指向下标为0的位置。

3、求队列长度

// 返回Q的元素个数，也就是队列的当前长度
int QueueLength(SqQueue Q)
{
return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

代码分析：见前文所述队列长度的计算。

4、入队列操作

// 若队列未满，则插入元素e为新的队尾元素
Status EnQueue(SqQueue *Q, QElemType e)
{
if((Q->rear + 1) % MAXSIZE == Q->front)// 判断队列是否已满
return ERROR;
Q->data[Q->rear] = e;// 元素e的值赋给队尾
Q->rear = (Q->rear + 1) % MAXSIZE;// rear指针后移一位，若到最后则转到数组头部
return OK;
}

算法分析：

(1)、入队前先判断队列是否已满，判断条件见前文所述；

(2)、新元素的值赋给队尾空间；

(3)、rear指针后移一位，若到最后则转到数组头部。

5、出队列操作

// 若队列不空，则删除队头元素，用e返回其值
Status DeQueue(SqQueue *Q, QElemType *e)
{
if(Q->rear == Q->front)// 判断队列是否为空
return ERROR;
*e = Q->data[Q->front];// 将队头元素值赋给e
Q->front = (Q->front + 1) % MAXSIZE;// front指针后移一位，若到最后则转到数组头部
return OK;
}

算法分析：

(1)、出队前先判断队列是否为空，判断条件见前文所述；

(2)、把将要删除的队头元素的值赋给e；

(3)、front指针后移一位，若到最后则转到数组头部。

二、队列的链式存储

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点（这里的头结点是指队头结点的前一个结点），而队尾指针指向终端结点。

空队列时，front和rear都指向头结点，即front == rear。

1、存储结构

typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
QueuePtr front, rear;
}LinkQueue;

2、入队操作

// 插入元素e为新的队尾元素
Status EnQueue(LinkQueue *Q, QElemType e)
{
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));// 分配失败时返回NULL指针
if(!s)// 存储分配失败
exit(OVERFLOW);// exit定义在<stdlib.h>中，OVERFLOW定义在<math.h>中
s->data = e;
s->next = NULL;
Q->rear->next = s;// 把新结点s赋值给原队尾结点的后继
Q->rear = s;// 把s设为队尾结点，rear指向s
return OK;
}

算法分析：

(1)、首先分配一个存储空间s；

(2)、判断s是否分配成功；

(3)、把新元素值e赋给s的数据域；

(4)、s的指针域置空；

(5)、把新结点s赋给原队尾结点的后继；

(6)、把新结点s设为队尾结点，rear指向s。

3、出队操作：出队列时，就是头结点的后继结点出队。若链表除头结点外只剩一个元素，则需将rear指向头结点。

// 若队列不为空，删除队头元素，用e返回其值
Status DeQueue(LinkQueue *Q, QElemType *e)
{
QueuePtr p;
if(Q->front == Q->rear)// 判断队列是否为空
return ERROR;
p = Q->front->next;// 将要删除的队头结点暂存给p
*e = p->data;// 将要删除的结点的数据赋给e
Q->front->next = p->next;// 将原来队头结点的后继赋给头结点的后继
if(Q->rear == p)// 若队头是队尾，则删除后将rear指向头结点
Q->rear = Q->front;
free(p);// 释放p
return OK;
}

算法分析：

(1)、声明一指针p；

(2)、出队前先判断队列是否为空，条件如前文所述；

(3)、将要删除的队头结点暂存给p；

(4)、将要删除的结点的数据赋给e；

(5)、将p的后继赋给头结点的后继；

(6)、若队头也是队尾，则删除后将rear指向头结点；

(7)、释放p。

总结：在可以确定队列长度最大值的情况下，建议用循环队列，如果无法预估队列长度，则应用链队列。

三、sizeof与malloc()

sizeof是一个关键字，它的作用是求它的操作数的类型长度，以字节为单位表示。当sizeof的操作数是个数组名时，它返回该数组的长度，以字节为单位。

malloc()是一个函数，它的作用是分配一块内存，并返回一个指向这块内存的指针。

函数原形如下，声明于头文件<stdlib.h>中

void    *malloc(size_t size);        // size_t是一个无符号类型，定义于stdlib.h

malloc()的参数就是需要分配的内存字节数。如果内存池中的可用内存可以满足这个需求，malloc()就返回一个指向被分配的内存块起始位置的指针，其类型为 void * —— C标准表示一个void * 类型的指针可以转换为其他任何类型的指针。

如果操作系统无法向malloc()提供它所需要的内存，malloc()就返回一个NULL指针。因此，对每个从malloc()返回的指针进行检查，确保它并非NULL是非常重要的。