数据结构之队列（C语言版）

     本来此篇是准备总结堆栈顺序表的一些应用，但是觉得先接着上篇把队总结完，然后再将应用总结。ok，废话不多数，我们先来看队定义：

    和栈相反，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一样的，最早进入队列的元素最早离开。在队列中允许插入的一端叫队尾（rear），允许删除的一端称为队头（front）。队在程序中经常用到。一个最典型的例子就是操作系统的排队作业。ok我们先来看队的结构图：

    队的基本概念，以及结构图弄明白了的话，我们来看队列的抽象数据类型的定义：

ADT Queue

{

    数据对象：D = {ai| ai属于ElemSet，i = 1，2，……，n， n >= 0 }

    约定a1端为队头，an队尾。

    基本操作：

    //初始化函数

    Status  InitLinkQueue(LinkQueue *q);

    //入队，入队成功返回TRUE,入队失败返回FALSE

    Status  EnterQueue(LinkQueue *q,ElemType x);

    //出队，出队成功返回TRUE,失败返回FALSE

    Status DeQueue(LinkQueue *q);

    //获取队头元素值，用x带回队头的值

    Status GetHead(LinkQueue *q,ElemType *x);

    //求长度，返回队的长度

    int GetLength(LinkQueue *q);

    //清空队列,摧毁成功返回TRUE,否则返回FALSE

    Status ClearQueue(LinkQueue *q);

    //摧毁队

    Status DestortQueue(LinkQueue *q);

    //打印队列，打印成功返回TRUE,失败返回FALSE

    Status Show_Queue(LinkQueue *q);

}

    对于队列也是受限的线性表，所以，队列也有两种存储结构，顺序队列和链式队列。但是由于顺序存储会出现假溢出，所以出现了循环队列的结构，链队列不会出现这种情况。但是从存储结构上看依然是两种链式和顺序。我们就按照顺序，先看顺序队列：

顺序队列

#define ElemType  int 
#define TRUE      1
#define FALSE     0
#define Status    int
#define MAX_SIZE   8
typedef struct listqueue
  {
    ElemType *base;
    int front;
    int rear;
  }ListQueue;

按照我个人理解的顺序队的结构就是这样：

既然队的结构弄清了，我们来看队列的的基本操作：

顺序队列初始化：

    顺序队就像顺序表一样，所以就要初始化的时候动态开辟内存或者用数组的形式为其开辟内存，除了要开辟内存外，还要初始化结构中的其他项。当front和rear相等时表示空，且是指向基地址下表。

Status InitListQueue(ListQueue  *lq)
  {
     lq->base = (ElemType*)malloc(sizeof(ElemType) * MAX_SIZE);
     if(NULL == lq->base)
          {
                printf("out of memory\n");
                return FALSE;
           }
           
     lq->front = 0;
     lq->rear = 0;
     return TRUE;
   }

顺序队列入队出队

    队列的两项重要操作就是入队和出队，队列我们也一直强调是受限的线性表，主要不同就在这里，入队和出队，入队操作只能从表尾，出队操作只能从表头，入队我们先要保证内存空间要有，所以就要先判断是否队已满，然后就是尾插，rear表示的是队尾的存储值的空间的下一个，也就是直接把值存进下标为rear 的空间。

//入队操纵，入队成功返回TRUE,入队失败返回FALSE

Status EnListQueue(ListQueue *lq,ElemType x)
 {
    if(lq->rear >= MAX_SIZE)
     {
        printf("队已满\n");
        return FALSE;
      }
      
    lq->base[lq->rear++] = x;
    return TRUE;
  }

    顺序队的出队，只能从队头出队，对于顺序队，只需要修改队头标志front 就可以，这样就可以把数据从逻辑上删除。

//出队操作，出队成功返回TRUE,出队失败返回FALSE

Status DeListQueue(ListQueue *lq)
  {
      if(lq->front == lq->rear)
        {
            printf("队已空\n");
            return FALSE;
         }
    
    lq->front++;
    return TRUE;
  }

顺序队列获取队列元素个数

    由于顺序队的内存是连续的，所以获取队列数据元素个数，只需要把rear与front相减就可以得到队列的长度。

//获取长度，

int Get(ListQueue lq)
    {
        int  length = lq.rear - lq.front;
        return length;
    }

顺序队列对头元素

    对于获取队头元素操作，由于front表示的就是首元素的下标，所以只需要把数组中front下标中的值返回就好。

//获取队头，获取成功返回TRUE,获取失败返回FALSE

Status GetHead(ListQueue *lq,ElemType *val)
{
    if(lq->front == lq->rear)
    {
        printf("队已空\n");
        return FALSE;
    }
    *val = lq->base[lq->front];
    return TRUE;
}

顺序队列清空队列

    清空顺序队列，我们只需要把front和rear下标从新指向数组的0下边即可。

//清空,清空成功返回TRUE

Status ClearListQueue(ListQueue *lq)
{
    lq->front = lq->rear = 0;
    return TRUE;
}

顺序队列的摧毁

    对于摧毁操作，我们就要把初始化中开辟的内存释放掉并且把rear和front赋值为0

//摧毁，摧毁成功返回TRUE.

Status DestoryListQueue(ListQueue *lq)
{
    free(lq->base);
    lq->base = NULL;
    lq->front = lq->rear = 0;
    return TRUE;
}

顺序队列的输出打印

    顺序队的打印输出我们时，队结构中front表示着队头元素的下标，rear表示队尾下一个位置，所以只需要打印输出从front到rear的元素。

//打印，打印成功返回TRUE,失败返回FALSE

Status ShowListQueue(ListQueue *lq)
{
    if(lq->rear == 0)
    {
        printf("队已空\n");
        return FALSE;
      }
    for(int i = lq->front; i < lq->rear; i++)
        {
            printf("%d ",lq->base[i]);
        }
    printf("\n");
    return TRUE;
}

链队列

    用链表 表示的队列称为链队列，如下图，分别是按照理解画的图，一个链队列得分别有指向队头和队尾的指针（分别称作头指针和尾指针）才能唯一确定。由于队列是限定在进行头删尾插，那么我们之前总结链表的时候说过，带头结点的头单链表更方便头删，所以这里采用带头结点的单链表表示队列。

    开篇已经把队列的抽象数据类型介绍了，所以这里直接实现链队列。

链队列定义结点类型和管理结构

#define Status   int
#define TRUE     1
#define FALSE    0
#define ElemType int 


//定义结点类型
typedef struct  QueueNode
{
	ElemType data;
	struct QueueNode *next;

}QueueNode;

//定义管理结构
typedef struct LinkQueue
{
	QueueNode *front;
	QueueNode *tail;
}LinkQueue;

链队列初始化

    我们一直强调，对于栈、队是受限的线性表，所以，初始化链队列的时候，我们联想一下之前的带头结点的单链表如何初始化，就明白了链队如何初始化了。

//初始化队列
Status  InitLinkQueue(LinkQueue *Q)
{
	QueueNode  *s = (QueueNode *)malloc(sizeof(QueueNode));

	if(NULL == s)
	{
		printf("out of memory\n");
		return FALSE;
	}

	Q->front = s;
	Q->tail = s;
	s->next = NULL;
	return TRUE;	
}

链队列进队出队

    队是受限的线性表，那么对于队列进队、出队是需要注意的操作，队的先进先出，映射到链表中就是进行头删，尾插。这里由于带头结点头插的时候，也就是入队的时候操作就简化了好多.入队出队操作就是带头结点的头删尾插，所以，我就不过多废话。

//入队操作，入队成功返回TRUE,入队失败返回FALSE
Status  EnterQueue(LinkQueue *q,ElemType x)
{
	QueueNode  *s = (QueueNode *)malloc(sizeof(QueueNode));

	if(NULL == s)
	{
		printf("out of memory\n");
		return FALSE;
	}

	s->data = x;
	s->next = NULL;
	q->tail->next = s;
	return TRUE;
}

//出队操作，出队成功返回TRUE,出队失败返回FALSE,出队的时候，需要注意释放内存，防止内存泄露
Status DeQueue(LinkQueue *q)
{
	if(q->front == q->tail )
	{
		printf("队已空\n");
		return FALSE;
	}

	QueueNode *p = q->front->next;

	q->front->next = p->next;
	free(p);
	p = q->front->next; 

	if(q->tail == p)
	{
		q->tail = q->front;
	}
	return TRUE;
}

链队列获取队头元素

    获取对头元素这里需要强调一下，获取队头元素大多数课本上是用参数中一个值带回，或者用return语句直接返回返回值，这样做呢对于顺序队、队中只有一个值的时候没有错，但是不知道你有没有想过，假如说队的结点中不是一个数据域呢？还可以用return语句直接返回直接返回返回数据域吗？不可以吧！所以呢，个人觉得用return语句直接将整个结点返回，这样需要不论他是几个都可以，之前的链表、栈中是按照之前的操作做的，后边的操作将改掉这部分的操作，采用返回结点。

//获取对头元素，获取成功返回头结点，获取失败返回NULL
 QueueNode *GetHead(LinkQueue *q)
{
	QueueNode *p = q->front->next;
	if(q->front == q->tail )
	{
		printf("队已空\n");
		return NULL;
	}

	return q->front->next;
}

链队求数据个数

    链队求队中元素个数，不在像顺序队中，直接用reat和front直接相减就可以获取队列的元素个数，链队不可以，链队的内存不连续，这里就需要用一个变量计算队列的长度，防止头指针被修改就需要用临时指针遍历链表，然后计算其长度。或者在队列管理结构中在添加一项数据项，记住队列的个数。这样的话就可以方便的获取队列的元素个数。

//求长度
int GetLength(LinkQueue *q)
{
	int length;
	QueueNode *p = q->front->next;
	while(NULL != p)
	{
		length++;
		p = p->next;
	}
	return length;
}

链队打印输出队中元素

    链表不空的话，遍历整个链表输出整个链表的数据域，为了防止头指针被修改就需要定义一个临时变量指向队列

//遍历成功返回TRUEM,遍历失败返回FALSE
Status Show_Queue(LinkQueue *q)
{
	QueueNode *p = q->front->next;
	if(q->front == q->tail )
	{
		printf("队已空\n");
		return FALSE;
	}
	while(NULL != p)
	{
		printf("%d",p->data);
	}
	printf("\n");
	return TRUE;
}

链队的清空

    链表的清空就需要把申请的所有结点释放掉，防止内存空间泄露。

//清空队列
Status ClearQueue(LinkQueue *q)
{
	if(q->front == q->tail)
	{
		return FALSE;
	}
	QueueNode *p = q->front->next;
	while(NULL != p)
	{
		q->front->next = p->next;
		free(p);
		p = q->front->next;
	}
	p = NULL;
	q->tail = q->front;
	return TRUE;
}

链队的摧毁 

    链队的摧毁就是在释放了所有结点后，再把头结点释放掉。

//链队的摧毁
Status DestortQueue(LinkQueue *q)
{
	ClearQueue(q);
	free(q->front);
	q->front = NULL;
	q->tail = NULL;
	return TRUE;
}

循环队列

    为什么会出现循环队列？上边总结顺序队列的时候提到一个问题就是顺序队列会出现假溢出，对于链队不会出现假溢出，也就不需要处理这种情况。这下我们先来看前边讲的顺序队列，当进行不断的进队出队操作后，会出现什么情况？

    我们可以从图中清晰的看出来，队列只能再插入一个元素了，但是事实上队的空间是空的。为了解决这个问题就出现了循环队列。关于循环队列大多数的书上会画下边这样一个图，来解释循环队列：

    关于这个图，不是我画的是我从课本上截的，不知道大家第一眼从课本上看到这个图什么感觉，反正我看完，没有感觉，这画的什么啊？不是队啊，咋就成圈了！后来当我理解了以后，这个图好也不好，好就是形象的说明了循环队列的情况，但是这会让人产生误会，会以为计算机中就是这样存的，ok，当然不是，如果是那就厉害了。其实呢。在C语言中实现环是通过求模实现的，当你想实现一个多大的环通过求它的模就可以把数字控制在0 到 n-1，这个想必大家没有疑问吧？那么循环队列就是通过这样控制顺序队列的下表来实现顺序队列。 ok。我们来边看代码边解释。

     循环队列是建立在顺序队列上的，所以结构一样的只是基本操作处理上不一样。

定义循环队列的结构

#define ElemType  int 
#define TRUE      1
#define FALSE     0
#define Status    int
#define MAX_SIZE   12

typedef struct listqueue
{
	ElemType *base;
	int front;
	int rear;
}ListQueue;

 循环队列的初始化

    循环链表的初始化与顺序链表的操作也一样。这也不用说

Status InitListCycQueue(ListQueue  *lq)
{
	lq->base = (ElemType*)malloc(sizeof(ElemType) * MAX_SIZE);
	if(NULL == lq->base)
	{
		printf("out of memory\n");
		return FALSE;
	}
	lq->front = 0;
	lq->rear = 0;
	return TRUE;
}

 循环队列的入队、出队

    ok入队出队进入循环队列的重点，循环队列为什么可以实现循环？我们先看顺序队列遇到了那些问题：

    问题一：由于顺序队列是通过数组实现的，即就是你的数组开辟的很大，那么也会随着不断的插入的数据导入队满是吧？这个没有错吧？也会出现上面图中那种情况rear大小等于了数组的空间大小，已经越界不能再增大了虽然front随着数据的不断出队也不断向后指向，就造成了前边的空间无法访问，那么我们可不可通过让rear从新指向数组是开头，这样就可以从新插入数据，那么实现这个就要用到我之前已经提到的求模，通过rear求数组空间大小的模就可以把rear大小控制在0 - SIZE-1 的范围内，而C语言的数组下标正好是从0开始到 SIZE - 1,ok解决了让空间循环回去的问题，我们就会遇到另一个问题这也就是

    问题二：那么我们之前的判断队满的条件已经不在适用，有人就说既然都循环了，不会存在队满，个人觉得呢！不不不，判断队满是非常有必要的，虽然循环了但是队可以容纳的有效数据是一定的，当队满时如果继续插入，就会将之前的数据覆盖掉这是不允许的！所以判断队满是非常有必要的！并且修改成循环以后还会遇到之前判断队空的条件的也不好用了，因为当采用循环以后rear == front，有可能是队空，也有可能是队满，对吧？这个大家认同吧？ok解决这个问题有两种方法：

    方法一：在结构中再引入一个标记变量，队空时一个状态值，堆满时是一个状态值。

    方法二：既然存满时rear循环回去会造成rear == front，判断困难，那么就牺牲最后一个空间，让其永远也不会相等。这样就可以解决了判断队满的条件，同时判断队空的问题也就相应解决了

    ok问题解决完了，那么循环队列也就实现了

//循环队列入队，入队成功返回TRUE,入队失败返回FALSE
Status EnListCycQueue(ListQueue *lq,ElemType x)
{

//注意看这个判断队满的条件，这里采用刚才提到的第二种方法，牺牲队尾的最后一个空间（注意
//不一定是数组的最后一个空间，是队尾的最后一个空间）当rear + 1 时等于 front就是队满，rear//== front  依然是判断队空时的条件
	if(((lq->rear + 1) % MAX_SIZE) == lq->front)
	{
		printf("队已满\n");
		return FALSE;
	}
	lq->base[lq->rear] = x;
	lq->rear = (lq->rear + 1) % MAX_SIZE;
	return TRUE;
}

//出队，出对成功，返回TRUE,出队失败返回FALSE
Status DeListCycQueue(ListQueue *lq)
{

	if(lq->front == lq->rear)
	{
		printf("队已空\n");
		return FALSE;
	}
	lq->front = (lq->front + 1) % MAX_SIZE;
	return TRUE;
}

循环队列获取队中元素个数

//获取长度
int GetLentg(ListQueue *lq)
{
	return (lq->rear + MAX_SIZE - lq->front) % MAX_SIZE;
}

循环队列获取队头元素

    虽然采用了循环结构但是我们可以发现front依然是表述队头元素的下标，所以与顺序队的操作是没有区别的。

//获取队头
Status GetHead(ListQueue *lq,ElemType *val)
{
	if(lq->front == lq->rear)
	{
		printf("队已空\n");
		return FALSE;
	}

	*val = lq->base[lq->front];
	return TRUE;
}

循环队列的清空

    循环队列的清空同样是让队恢复到初始状态，所以操纵与顺序队的操作一样

//清空，清空成功返回TRUE
Status ClearListCycQueue(ListQueue *lq)
{
    lq->front = lq->rear = 0;
    return TRUE;
}

循环队列的摧毁

    循环队列只是再存储时进行了改变，对于摧毁，东西都不在了，与顺序队又有什么区别呢？

//摧毁,摧毁成功返回TRUE,
Status DestoryListCycQueue(ListQueue *lq)
{
free(lq->base);
lq->base = NULL;
lq->front = lq->rear = 0;
return TRUE;
}

循环队列的打印

    关于打印输出，需要注意一下，循环队列中的元素已经不能通过之前的方式访问输出了我们可以看下图：

    当采用顺序队的方式打印输出时，front本身就是大于rear所以不会进入循环打印输出数据，并且那个判断空的条件也已经不在适用了，即使循环队中有值它也会在某中情况下判断为空。那么循环队列怎样存就怎样访问输出，ok我们来看：前边已经说到循环队列中判断队空的条件修改为是front == rear，然后，由于rear是指向队尾的下一个空间的，所以循环条件只要i不等于 rear让其循环就可以，此时还要注意i的增长方式是循环的ok

Status ShowListCycQueue(ListQueue *lq)
{
	if(lq->rear == lq->front)
	{
		printf("队已空\n");
		return FALSE;
	}
	for(int i = lq->front; i != lq->rear; )
	{
		printf("%d ",lq->base[i]);
		i = (i+1) % MAX_SIZE;
	}
	printf("\n");
	return TRUE;
}

    ok关于队的基本操作就总结的到这里，博文呢按照我个人的理解，尽我最大的努力进行了总结，但也不能不能避免一些表述错误，代码是没有问题的。希望各位读者发现了其中的错误，评论指出错误，让我改正其中的错误。

    后面呢按照之前说的进行线性表，栈、队的遗留问题进行总结以及他们的应用。