算法与数据结构(二)：队列

队列也是一种线性的数据结构，它与链表的区别在于链表可以在任意位置进行插入删除操作，而队列只能在一端进行插入，另一端进行删除。它对应于现实世界中的排队模型。队列有两种常见的实现方式：基于列表的实现和基于数组的实现

基于链表的实现

基于链表的队列，我们需要保存两个指针，一个指向头节点，一个指向尾节点。

这种队列不存在队列满的情况，当然也可以根据业务需求给定一个最大值。当头结点为空时表示队列为空。由于队列只能在队尾插入数据，队首删除数据，因此针对队列的插入需要采用链表的尾插法，队列元素的出队需要改变头指针。

队列节点的定义与链表节点的定义相同，下面给出各种操作的简单实现

typedef struct _QNODE
{
	  int nValue;
	  struct _QNODE *pNext;
}QNODE, *LPQNODE;

extern QNODE* g_front;
extern QNODE* g_real;

初始化

初始化操作，我们简单的对两个指针进行赋值

bool InitQueue()
{
	  g_front = g_real = NULL;
	  return true;
}

元素入队

元素入队的操作就是从队列尾部插入，当队列为空时，同时也是在队首插入元素，因此针对元素入队的操作，需要首先判断队列是否为空，为空时，需要针对队首和队尾指针进行赋值，而针对队列不为空的情况下，只需要改变队尾指针

bool EnQueue(int nVal)
{
	  QNODE *p = (QNODE*)malloc(sizeof(QNO
	  if (NULL == p)
	  {
		  return false;
	  }

    memset(p, 0x00, sizeof(QNODE));
    p->nValue = nVal;
    if (IsQueueEmpty()) //判断队列是否为空
    {
    	  g_front = g_real = p;
    }else
    {
    	  g_real->pNext = p;
    	  g_real = p;
    }

    return true;
}

判断队列是否为空

之前提到过，判断队列是否为空，只需要判断两个指针是否为空即可，因此这部分的代码如下:

bool IsQueueEmpty()
{
	  return (g_front == NULL && g_real == NULL);
}

元素出队

元素出队需要从队首出队，同样的需要判断队列是否为空。

bool DeQueue(int *pVal)
{
    if(NULL == pVal)
    {
        return false;
    }
    if (IsQueueEmpty())
    {
    	  return false;
    }

    QNODE *p = g_front;
    //出队之后需要判断队列是否为空，以便针对队首、队尾指针进行赋值
    if (NULL == g_front->pNext)
    {
      	*pVal = g_front->nValue;
      	g_front = NULL;
      	g_real = NULL;
    }else
    {
      	*pVal = g_front->nValue;
      	g_front = g_front->pNext;
    }

    free(p);
    return true;
}

基于数组的实现

线性结构的队列也可以使用数组来实现，基于数组的实现也需要两个指针，分别是指向头部的下标和指向尾部的下标

基于数组的实现中有这样一个问题，那就是内存资源的浪费问题。假设现在有一个能存储10个元素的队列，当前队列为空，随着元素的入队，此时队尾指针会一直向后偏移。当里面有部分元素的时候，来进行元素出队，这个时候队首指针会向后偏移。那么这个时候已经出队的位置在队列中再也访问不到了，但是它所占的内存仍然在那，这样就造成了内存空间的浪费，随着队列的不断使用，队列所能容纳的元素总数会不断减少。如图所示

基于这种问题，我们采用循环数组的形式来表示一个队列，循环数组的结构大致如下图所示:

这种队列的头指针不一定小于尾指针，当队首元素元素位于数组的尾部，这个时候只要数组中仍然有空闲位置来存储数据的时候，可以将队首指针再次指向数组的头部，从而实现空间的重复利用.

在这种情况下队列的头部指针的计算公式为: head = (head + 1) % MAXSIZE,尾部的计算公式为 tail = (tail + 1) % MAXSIZE

当队列为空时应该是 head == tail，注意，由于数组是循环数组，此时并不一定能保证它们二者都为0，只有当队列中从来没有过数据，也就是说是刚刚初始化完成的时候它们才都为0

那么队列为满的情况又怎么确定呢？在使用普通数组的时候，当二者相等都为MAXSIZE的时候队列为满，但是在循环队列中，并不能根据二者都等于MAXSIZE来判断队列是否已满，有可能之前进行过出队的操作，所以在队列头之前的位置仍然能存数据，所以不能根据这个条件判断。那么是不是可以根据二者相等来判断呢？答案是不能，二者相等是用来判断队列为空的，那么怎么判断呢？这时候需要空出一块位置作为队尾的结束标志，回想一下给出的循环数组的实例图，每当head与tail只间隔一个元素的时候作为队列已满的标识。这个时候判断的公式为 (tail + 1) % MAXSIZE == head

下面给出各种操作对应的代码

队列的初始化

int g_Queue[MAX_SIZE] = {0};
int g_front = 0;
int g_real = 0;

bool InitQueue()
{
    g_front = g_real = 0;
    memset(g_Queue, 0x00, sizeof(g_Queue));
    return true;
}

入队

bool EnQueue(int nVal)
{
  	if (IsQueueFull())
  	{
  		  return false;
  	}

  	g_Queue[g_real] = nVal;
  	g_real = (g_real + 1) % MAX_SIZE;
  	return true;
}

出队

bool DeQueue(int *pVal)

{

if (NULL == pVal)

{

return false;

}

if (IsQueueFull())
{
      return false;
}

*pVal = g_Queue[g_front];
g_front = (g_front + 1) % MAX_SIZE;
return true;

}

判断队空与队满

bool IsQueueEmpty()
{
	   return g_real == g_front;
}

bool IsQueueFull()
{
    return (( g_real + 1 ) % MAX_SIZE) == g_front;
}

最后从实现上来看基于数组的队列要比基于链表的简单许多，不需要考虑空指针，内存分配的问题，但是基于数组的队列需要额外考虑是否已满的情况，当然这个问题可以使用动态数组来避免。