队列是只允许在一端进行插入操作，另一端进行删除操作的线性表

• 队列是一种先进先出（First In First Out）结构，简称FIFO，允许插入的一端成为对尾，允许删除的一端成为队头，可以类比于实际生活中的队列。

本文介绍两种队列的存储结构的实现，分别是连续存储结构和链式存储结构，连续存储结构一般又称为环形缓冲区。以下的代码均在ubuntu16.04上运行，测试过。

一 环形缓冲区

队列的连续存储结构通过数组实现，队头删除数据之后，对尾添加的数据在超过数组长度时，需要插入数组前部（队头被删除的数据位置），这样，数组首尾相连，形成一个环形数组

• 队列的存储结构如下，一个数组，一个指向队头的数组index，front，一个指向对尾的index,rear，最后一个是队列中的数据个数。

#define MAX_SIZE 10
typedef struct SqQueue
{
	int data[MAX_SIZE];	// 存储数据的数组
	int front;			// 头指针
	int rear;			// 尾指针
	int flag;			// 队列中数据的个数
}SqQueue;

• 初始化一个环形缓冲区,这个环形缓冲区的位置分配在堆中

void init_queue(SqQueue **S)
{
	*S = malloc(sizeof(struct SqQueue));		// 动态内存分配
	(*S)->front = 0;	
	(*S)->rear  = 0;
	(*S)->flag  = 0;
}

• 对尾添加数据,如果队列中的数据超过了最大值，说明缓冲区已满，否则在rear位置插入一个数据，并将rear+1,在rear到达数组尾部时，让rear置为0，即指向数组首地址

void addQueue(SqQueue *S,int data)   // 队尾添加数据
{	
	if(S->flag >= MAX_SIZE)
		return;
	S->data[S->rear] = data;
	S->rear ++;
	if(S->rear == MAX_SIZE) S->rear = 0;
	S->flag++;
}

• 队头删除数据,也就是让队头index+1，并且让flag减一即可

void delQueue(SqQueue *S)    // 队头删除数据
{
	if(S->flag <= 0) 
		return;
	S->front ++;
	if(S->front == MAX_SIZE) S->front = 0;
	S->flag--;
}

• 返回队列中的元素个数,也就是返回flag的数值

int queueLength(SqQueue *S)
{
	return S->flag;
}

• 遍历环形缓冲区，打印出所有的数值,从队头打印到对尾，如果超过数组范围，仍然是回到数组首位

void printall(SqQueue *S) 
{
	int i;
	int count = S->front;
	if(S->flag == 0) return;
	for(i=0;i<S->flag;i++)
		{
			printf("%d\n",S->data[count]);
			count++;
			if(count >= MAX_SIZE)count = 0;
		}
}

二 链式队列

链式队列是一种带有限制的链表，优点在于没有长度的限制

• 链式队列的存储结构,封装了一个单链表，并且加入了队头指针，对尾指针和队列的长度。

typedef struct QNode
{
	int data;
	struct QNode *next;
}QNode,*QNodePtr;


typedef struct LinkQueue
{
	QNodePtr front;			// 表头，删除数据
	QNodePtr rear;			// 表尾，添加数据
	int count;				// 队列长度	
}LinkQueue;

• 在队尾插入数据，也就是在链表的尾部增加节点，先把旧队尾rear的next指向新增的节点，再把rear更新为这个新增的节点。

void add_LinkQueue(LinkQueue *Q,int data) // 队尾增加节点
{
	QNodePtr s = malloc(sizeof(struct QNode));
	s->data = data;
	s->next = NULL;

	Q->count++;
	Q->rear->next = s; 	    // 先前节点的next指向s 

	Q->rear = s;			// 现在的节点更新为s
	Q->rear->next = NULL;
}

• 在队头删除数据,注意这里删除的是首节点的下一个节点，并且把首节点的next指向下下个节点

void del_LinkQueue(LinkQueue *Q)	//删除队头的下一个节点（队头不删）
{
	QNodePtr p;
	if(Q->count == 0) return;
	
	p = Q->front->next;
	Q->front->next = p->next;
	
	if(Q->rear == p) Q->rear = Q->front; // 如果删除的恰好是尾结点
	Q->count --;
	free(p);
}

• 遍历整个队列,从头结点的下一个节点一直输出至队尾节点。

void printall(LinkQueue *Q)
{
	int i;
	QNodePtr p = Q->front; 
	
	printf("count = %d\r\n",Q->count);
	
	if(Q->count == 0) return;
	
	for(i=0;i< Q->count;i++){
		printf("%d\r\n",p->next->data);
		p = p->next;
	}
}

队列还有其他别的操作，如插入，删除某个特定的节点等，但是这都是建立在对队列这个数据结构非常了解的基础上的，只要真正了解了这个数据结构，就很容易实现。