数据结构之队列

什么是队列？

队列（queue）是一种先进先出（FIFO）的数据结构。就如生活中排队一样，先排的人在队伍的最前面，后排的人在队伍的最后面。

队列的实现方式

队列的实现方式分为数组和链表两种

数组的方式实现队列需要两个指针，指向对头的front，指向队尾的rear。由于队列是对的头部删除，队的尾部插入数据，当我们在删除数据之后，数据并不会自动去补齐前面已经删除的空白的位置，这就导致有的时候整个数组并没有多少元素，但是已经不能插入数据了。从而造成资源的浪费！如果在元素出队的过程中，不断地移动元素，这样复杂所需资源非常大，也是不好的实现方法。这个时候，我们找到了另外一种实现方法：循环数组。

如下图所示，就是典型的循环数组的样子。左边为空循环队列，右边为满循环队列。但是我们仅仅用rear==front是无法判断这个队列是否是满还是空的，一般我们有两种方法，第一种是引入一个新变量，来记录队列元素的个数，插入元素加1，删除元素减1，清空队列就置0；另外一种就是定义“满”的含义，在数组中定义一个元素始终不使用，当队列满的时候，front和rear的值就不可能相同了。

当我们采用第二种方法时，我们让rear比front小1，这样就可以解决问题了。

当满足下面条件时，队列为空：(rear+1)%QUEUE_SIZE== front

当满足下面条件时，队列为满：(rear+2)%QUEUE_SIZE== front

队列还有如下的链式存储方式，也就是只允许头进尾除的线性表中只允许头进尾除的单链表。

队列的接口

#include<stdlib.h>

#define QUEUE_TYPE int     //定义队列元素类型

void create_queue(size_t size);   //创建一个队列，参数指定队列可以存储的元素的最大数量。适用于动态分配数组的队列

void destory_queue(void);   //销毁一个队列，适用于链式和动态分配数组的队列

void insert_queue(QUEUE_TYPE value);  //向队列中添加一个新元素

void delete_queue(void);  //移除一个元素并丢弃

QUEUE_TYPE first(void);    //返回队列的第一个元素的值

int is_empty(void);      //判断队列是否为空

int is_full(void);         //判断队列是否已满

队列的实现

静态数组实现循环队列

#include “queue.h”
#include <stdio.h>
#include <assert.h>

#define QUEUE_SIZE   100
#define ARRAY_SIZE    (QUEUE_SIZE + 1)

static QUEUE_TYPE queue[ARRAY_SIZE];
static size_t front = 1;
static size_t rear = 0;

void insert_queue(QUEUE_TYPE value){
assert(is_full());
rear = (rear+1)%ARRAY_SIZE;
queue[rear] = value;
}

void delete(void){
assert(is_empty());
front = (front + 1)%ARRAY_SIZE;
}

QUEUE_TYPE first(void){
assert(!is_empty());
return queue[front];
}

int is_empty(void){
    return (rear + 1) % ARRAY_SIZE == front;
}

int is_full(void){
    return (rear + 2) & ARRAY_SIZE == front;
}

动态数组实现队列

相较于静态数组，动态数组的主要区别在与初始化队列时：

void InitQueue(int size){
maxSize = size
queue = (int *)malloc(size *sizeof(int));
front = 1;
rear = 0;
}

链式队列实现

//单链队列使用链表作为基本数据结果，所以不存在伪溢出的问题，队列长度也没有限制。但插入和读取的时间代价较高  
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<stdbool.h>

#define TRUE 1
#define FALSE 0

typedef char QElemType;

/*单链队列——队列的链式存储结构*/
typedef struct QNode
{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct
{
	QueuePtr front;  /*队头指针*/
	QueuePtr  rear;  /*队尾指针*/
}LinkQueue;

LinkQueue Q;

int  InitQueue(LinkQueue *Q) 
{ /*构造一个空队列Q*/ 
	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode)); 
	if(!Q->front){
		printf("ERROR!\n");
		return FALSE;
	}
	Q->front->next=NULL;
	return TRUE;
}

int DestroyQueue(LinkQueue *Q) 
{ /*销毁队列Q(无论空否均可)*/ 
	while(Q->front)
	{
		Q->rear=Q->front->next;
		free(Q->front);
		Q->front=Q->rear;
	}
	return TRUE;
}

void ClearQueue(LinkQueue *Q) 
{ /*将Q清空为空队列*/ 
	QueuePtr p,q; 
	Q->rear=Q->front; 
	p=Q->front->next; 
	Q->front->next=NULL; 
	while(p)
	{
		q=p;
		p=p->next;
		free(q);
	}
}

bool  is_Empty(LinkQueue Q) 
{ /*若Q为空队列，则返回TRUE，否则返回FALSE*/ 
	if(Q.front->next==NULL) 
		return TRUE; 
	else 
		return FALSE; 
}	
	
int QueueLength(LinkQueue Q) 
{ /*求队列的长度*/ 
	int i=0; 
	QueuePtr p; 
	p=Q.front; 
	while(Q.rear!=p) 
	{ 
		i++; 
		p=p->next; 
	} 
	return i;	
}	
 
bool  GetHead_Q(LinkQueue Q,QElemType *e) 
{ /*若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR*/ 
	QueuePtr p; 
	if(Q.front==Q.rear) {
		printf("IS empty\n");
		return;
	}
	p=Q.front->next; 
	*e=p->data; 
	return TRUE; 
} 
	
int  InsertQueue(LinkQueue *Q,QElemType e) 
{ /* 插入元素e为Q的新的队尾元素*/ 
	QueuePtr p=(QueuePtr)malloc(sizeof(QNode)); 
	if(!p) { /*存储分配失败*/
		printf("存储分配失败\n");
		return FALSE;
	}
	p->data=e; 
	p->next=NULL; 
	Q->rear->next=p; 
	Q->rear=p; 
	return TRUE;
} 
 
int DeleteQueue(LinkQueue *Q,QElemType *e) 
{ /*若队列不空，删除Q的队头元素，用e返回其值，并返回TRUE，否则返回ERROR*/ 
	QueuePtr p; 
	if(Q->front==Q->rear) 
		return FALSE; 
	p=Q->front->next; 
	*e=p->data; 
	Q->front->next=p->next; 
	if(Q->rear==p) 
		Q->rear=Q->front; 
	free(p); 
	return TRUE; 
} 

int QueueTraverse(LinkQueue *Q) 
{ /*遍历队列Q*/ 
	QueuePtr p;
	if(Q->rear == Q->front)
		return FALSE;
	p = Q->front->next;
	printf("the queue is:");
	while(p){
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
    return TRUE; 
} 

int main(int argc,char *argv[]){
	LinkQueue Q;
	InitQueue(&Q);
	QElemType e;
	printf("please input elem:\n");
	while((e = getchar())!='\n'){
		if(e == ' ')
			continue;		
		InsertQueue(&Q,(e-0X30));
	}
	printf("output:\n");
	QueueTraverse(&Q);
	
}

参考文档：

https://www.cnblogs.com/kubixuesheng/p/4104802.html

http://blog.csdn.net/juanqinyang/article/details/51354293

http://blog.csdn.net/leichelle/article/details/7546775

《C与指针》