第三章队列

3.1队列定义：先进先出

队列是一种只允许前端（front，队首）进行删除操作，而在后端（rear，队尾）进行插入操作的数据结构。正是因为规定了从队首删除队尾插入的性质，因此最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的数据结构。

队列是一种使用很广泛的数据结构，比如操作系统的进程调度就是用的队列，图的广度优先遍历也使用的是队列。

队列也是一种很好理解的数据结构。比如人们去银行办事，就是排成一队，新到的人从队尾插入，而银行工作人员都是从队首开始受理业务，受理完，队首的人就离开队列（从队列中删除）。

3.2队列结构：尾部插入，前端删除

如下图所示，队列底层数据结构可以使用链表或者数组。在使用链表的时候，如下图左边部分所示，用front和rear两个指针分别指向队列的前端和后端。在使用数组的时候，分别用2个整数front和rear做数组的下标，指向数组的前端和尾端。

需要注意的是，如果用数组作为队列的底层结构，那么在不断的插入元素和删除元素的时候，数组的内存空间将会不断的向上滑动（如下图中间部分所示），这在实际应用过程中肯定是不好的，因此假如数组的长度为MAX，通过用rear=(rear+1)%MAX和front=(front+1)%MAX来移动数组的前端和尾端，可以限制它们在数组的当前空间，这样就构成了一个循环队列（如下图右边部分所示）。

3.3队列基本操作

队列包含创建，入队，出队，队空判断，对满判断等操作。

1. 创建

int CreateQue();

用于创建一个队列，一般需要初始化队列的前端和后端指针。

2. 入队

int EnQueue(int e);

将特定的元素e从队列的尾部插入。

3. 出队

int DeQueue(int *e);

获取队列头部的数据并从队列删除。

4. 判断队列满

int IsQueueFull();

判断队列是否已满，如果队列满了就不能再从尾部插入数据了，只对基于数组的队列有效。

5. 判断队列空

int IsQueueEmpty();

判断队列是否为空，如果队列为空，就不能从队首删除数据了，在构造基于链表的队列的时候，队列为空，插入第一个元素的时候，也需要特别的处理。

3.4基于链表的链队

链表结点的存储结构如下：

typedef struct _node

{

int value;

struct _node *next;

}node,*pnode;

其中值的部分存放的是一个整数data，这部分数据可以自己再定义，增减。

node *front=NULL; //队头指针，由于是全局变量，请注意多线程安全

node *rear=NULL; //队尾指针，由于是全局变量，请注意多线程安全

在实现队列的基本操作的时候，最好是先画出队列的图形，如上图所示，然后按照图形来写各种操作的代码，思路就会比较清晰（注意，在多线程环境下，下面的代码没有提供加锁机制，需要另外处理）。

//创建队列

int CreateQueue()

{

front = rear = NULL;//将front和rear置为NULL

return 1;

}

//判断队列是否为空

int IsQueueEmpty()

{

if(front==NULL&&rear==NULL)//front和rear等于NULL是队列为空的标志

{

return 1;

}

return 0;

}

//入队

int EnQueue(int e)

{

node *p = (node *)malloc(sizeof(node));

if(p==NULL)

{

return -1;

}

memset(p,0,sizeof(node));

p->value = e;

p->next = NULL;

if(IsQueueEmpty())//队列为空，直接将rear和front指向该结点

{

rear=front=p;

return 1;

}

//队列不为空，插入尾部

rear->next = p;

rear = p;

return 1;

}

//出队

int DeQueue(int *e)//必须传指针，否则出队的值无法获取

{

if(IsQueueEmpty())

{

return -1;

}

if(e==NULL)

{

return -1;

}

//只有一个结点的时候

if(rear==front && rear!=NULL)

{

*e = rear->value;

free(rear);

front=rear=NULL;

return 1;

}

//多个结点的时候

*e = front->value;

node *q =front;

front = front->next;

free(q);

return 1;

}

//遍历队列

void TraverseQueue()

{

while(!IsQueueEmpty())

{

int value;

DeQueue(&value);

printf("%d ",value);

}

printf("\n");

}

//队列测试代码

int _tmain(int argc, _TCHAR* argv[])

{

int value;

CreateQueue();

EnQueue(3);

EnQueue(1);

EnQueue(0);

EnQueue(5);

DeQueue(&value);

printf("value:%d\n", value);

EnQueue(18);

EnQueue(27);

DeQueue(&value);

printf("value:%d\n", value);

DeQueue(&value);

printf("value:%d\n", value);

TraverseQueue();

return 0;

}

3.5基于数组的循环队列

如下图所示，基于数组的循环队列，有3种形态：

1，队列为空，这个时候front等于rear，如下图左边部分所示。

2，正常形态，这个时候，front指向队首元素，rear指向队尾元素的下一个位置，如下图中间部分所示。

3，队列满，这个时候，队尾指针指向队首指针的前一个位置（空位）。如下图右边部分所示。

因此，循环队列在队列满的时候，会浪费一个空间，这主要是为了区分队列空和队列满的2个状态的。否则，如果最后一个空间也存放元素，那么rear在加1后，就和front相等了，这和队列为空的判断条件是冲突的。

在实现基于数组的队列的基本操作的时候，结合上面3个队列的基本形态来写代码，会显得思路清晰。下面是具体的代码与数据结构（注意，在多线程环境下，下面的代码没有提供加锁机制，需要另外处理）：

#define MAXSIZE 100//数组的元素个数

int Queue[MAXSIZE]={0};//队列的底层数据结构，数组，支持100个元素

int rear = 0;//队列后端，插入的位置

int front = 0;//队列前端，删除的位置

创建队列，将前端和后端置0

int CreateQueue()

{

rear = front = 0;

return 1;

}

判断队列是否为空

int IsQueueEmpty()

{

return rear==front?1:0;//front等于rear，队列即为空

}

判断队列是否满

int IsQueueFull()

{

return (rear+1)%MAXSIZE == front?1:0;//注意判断标准

}

入队：

int EnQueue(int e)

{

if(IsQueueFull())

{

return -1;

}

Queue[rear]=e;

rear = (rear+1)%MAXSIZE;

return 1;

}

出队

int DeQueue(int *e)

{

if(IsQueueEmpty())

{

return -1;

}

if (e==NULL)

{

return -1;

}

*e = Queue[front];

front = (front + 1)%MAXSIZE;

return 1;

}

队列遍历：

void TraverseQue()

{

while(!IsQueueEmpty())

{

int val;

DeQueue(&val);

printf("%d ",val);

}

printf("\n");

}

接口测试：

int _tmain(int argc, _TCHAR* argv[])

{

for(int i=0;i<200;i++)

{

EnQueue(i);

}

int val = 0;

DeQueue(&val);

printf("val:%d\n",val);

DeQueue(&val);

printf("val:%d\n",val);

TraverseQue();

return 0;

}