一、队列

为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

循环队列和普通队列有所不同，需要注意的是队空队满
为了区分队空还是队满的情况，有多种处理方式（这里选的是第一种）：

方式1： 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，即约定以"队头指针在队尾指针的下一位置作为队满的标志"
方式2： 增设表示队列元素个数的数据成员size，此时，队空和队满时都有front==rear。
方式3： 增设tag数据成员以区分队满还是队空

二、代码

1.头文件与宏定义

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAXSIZE 50
#define QueueElemType char

2.循环队列的定义及主要操作

typedef struct {
	QueueElemType elem[MAXSIZE];
	int front;  //头
	int rear;	//尾
}SeqQueue;

// 初始化
void InitQueue(SeqQueue* Q) {
	Q->front = Q->rear = 0;
}

// 判断队列是否为空
int IsEmpty(SeqQueue Q) {
	if (Q.front == Q.rear) {
		return TRUE;
	}
	else {
		return FALSE;
	}
}

// 入队
int EnterQueue(SeqQueue* Q, QueueElemType x) {
	if ((Q->rear + 1) % MAXSIZE == Q->front) {
		//队列已满
		return FALSE;
	}
	else {
		Q->elem[Q->rear] = x;
		Q->rear = (Q->rear + 1) % MAXSIZE;	//重新设置队尾
		return TRUE;
	}
}

// 出队
int DeleteQueue(SeqQueue* Q, QueueElemType* x) {
	if (Q->front == Q->rear) {
		//队列为空
		return FALSE;
	}
	else {
		*x = Q->elem[Q->front];
		Q->front = (Q->front + 1) % MAXSIZE;
		return TRUE;
	}
}

// 求队的长度
int LenQueue(SeqQueue Q) {
	return ((Q.rear + MAXSIZE - Q.front) % MAXSIZE);
}

// 输出队中元素
int PrintQueue(SeqQueue Q) {
	if (Q.front == Q.rear) {
		//队列为空
		return FALSE;
	}
	while(TRUE) {
		if (Q.rear == Q.front) {
			return TRUE;
		}
		else {
			printf("%c ", Q.elem[Q.front++]);
		}
	}
}

3.主函数（测试函数）

int main() {
	SeqQueue Q;
	int i, n, flag, len;
	QueueElemType x;
	//初始化循环队列
	InitQueue(&Q);

	//判断队列是否为空
	printf("当前队列是否为空： ");
	flag = IsEmpty(Q);
	if (flag) {
		printf(" 当前队列为空。\n");
	}
	else {
		printf(" 当前队列不为空。\n");
	}

	//入队
	printf("请输入入队数量：\n");
	scanf("%d", &n);
	getchar();
	printf("请输入元素：\n");
	for (i = 0; i < n; i++) {
		x = getchar();
		getchar();	
		flag = EnterQueue(&Q, x);
		if (!flag) {
			printf("当前队列已满！！\n");
			break;
		}
	}

	//出队
	printf("出对一个元素并输出\n");
	flag = DeleteQueue(&Q, &x);
	if (flag) {
		printf("%c \n", x);
	}
	else {
		printf("队列为空！！！\n");
	}

	//当前队列元素的个数
	len = LenQueue(Q);
	printf("当前队列元素的个数：%d\n", len);

	//入队
	printf("请输入入队数量：\n");
	scanf("%d", &n);
	getchar();
	printf("请输入元素：\n");
	for (i = 0; i < n; i++) {
		x = getchar();
		getchar();
		flag = EnterQueue(&Q, x);
		if (!flag) {
			printf("当前队列已满！！\n");
			break;
		}
	}

	//当前队列元素的个数
	len = LenQueue(Q);
	printf("当前队列元素的个数：%d\n", len);

	//所有元素出队
	printf("所有元素出队：\n");
	while (TRUE){
		flag = DeleteQueue(&Q, &x);
		if (!flag) {
			break;
		}
		else {
			printf("%c ", x);
		}
	}
	printf("\n");

	//判断队列是否为空
	printf("当前队列是否为空： ");
	flag = IsEmpty(Q);
	if (flag) {
		printf(" 当前队列为空。\n");
	}
	else {
		printf(" 当前队列不为空。\n");
	}

	return 0;
}

三.运行结果

一、队列的定义
队列( queue )是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。如图所示：

二、循环队列的引出
为了避免当队中只剩一个元素的时候，队头队尾重合使处理变得麻烦。所以我们引入两个指针，front指针指向队头元素，rear指针指向队尾元素。这样当front=rear时，队列中不是只剩一个元素，而是它是一个空队列。而且这样也大大方便了我们删除队头元素。这样就当我们删除队头元素时就只需要移动front指针，这样可以大大降低算法的时间复杂度。
但是当删除元素的时候，front不断后移，前面的位置不断空出来。插入元素时rear指针 b不断后移。对于一个有限的队列来说，在不断得插入元素时rear最终会指向一个无效位置。具体情况如下图所示：
删除元素时：

插入元素时：

用循环队列可以巧妙得解决这个问题。
三、循环队列
1、循环队列的定义
**我们把队列的这种头尾相接的顺序存储结构称为循环队列。**如下图所示：
循环队列满时：

循环队列空时：

判断循环队列空的条件是：

front == rear;

判断循环队列满的条件是：

(rear+1)%6==front

为了区别判空和判满的状态，我们总在插入元素时牺牲一个空间来区别这两种状态，这也是为啥判满的时候是(rear+1)%6==front
2、循环队列的简单实现
（1）循环队列的整体结构的设计

typedef int ElemType;
#define MAX_SIZE 10
typedef structc Queue
{
	ElemType arr[MAX_SIZE];
	int front;//队头指针
	int rear;//队尾指针
};Queue,pQueue

2、初始化(init)
初始化的时候我们只需要将我们的头指针和尾指针置成0即可。

void init(pQueue pqu)
{
	if(pqu != NULL)
	{
	pqu->front = pqu->rear = 0;
	}
} 

3、入队操作(enqueue)
在进行入队操作之前我们首先应该对队列进行判满的操作。如果队列是满的，我们就插入不了元素。如果队列不满我们就可以进行我们的入队操作。
判满

int full(pQueue pqu)
{
	return (pqu->rear + 1)%MAX_SIZE == front ? 1 : 0;
}

插入元素
插入元素时，我们只需要将这个队列中的rear指针的下标置成我们要插入的元素即可。

int enqueue(pQueue pqu,ElemType val)
{
	if(full(pqu))
	{
	return 0;
	}
	pqu->arr[pqu->rear] = val;
	pqu->rear = (pqu->rear + 1)%MAX_SIZE;
	return 1;
}

4、出队操作(dequeue)
在进行出队操作时，我们首先要判断的是队列是否为空。若队列中的元素为空，则就无法进行出队的操作。
判空

int empty(pQueue pqu)
{
	return (pqu->rear == pqu->front) ? 1 : 0;
}

出队操作

int dequeue(Pqueue pqu)//只是删除元素
{
	if(empty(pqu))
	{
	return 0;
	}
	pqu->front = (pqu->front + 1) % MAX_SIZE;
	return 1;
}

5、获取队头元素(front)

int front(pQueue pqu)
{
	if(empty(pqu))
	{
	return -1;//牺牲一个数值位
	}
	return pqu->arr[pqu->front];
}

6、获取队尾元素(back)

int back(pQueue pqu)
{
	if(empty(pqu))
	{
	return -1;//队列为NULL
	}
	return pqu->arr[(pqu->rear + MAX_SIZE - 1)%MAX_SIZE];
}

一、队列的基本概念

1.1 队列的定义

  队列(Queue) 简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队。删除元素称为出队或离队。这和我们日常生活中的排队是一致的，最早排队的也是最早离队的，其操
作的特性是先进先出(First In First Out, FIFO)，如：

队头(Front)： 允许删除的一-端，又称队首。
队尾(Rear)。： 允许插入的一-端。
空队列： 不含任何元素的空表。

1.2 队列常见的基本操作

InitQueue(&Q)： 初始化队列，构造-一个空队列 Q.
QueueEmpty(Q)： 判队列空，若队列Q为空返回true,否则返回false.
EnQueue(&Q,x)： 入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue (&Q, &x)： 出队，若队列e非空，删除队头元素，并用x返回。
GetHead(Q,&x)： 读队头元素，若队列Q非空，则将队头元素赋值给x。

注意： 栈和队列是操作受限的线性表，因此不是任何对线性表的操作都可以作为栈 和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。

二、队列的顺序存储结构

  队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针:队头指针front 指向队头元素,队尾指针rear 指向队尾元素的下一个位置 (也可以让rear指向队尾元素、front 指向队头元素) 。
  顺序结构可描述为：

typedef struct SqQueue
{
	ElemType data[MaxSize];	//存放队列元素
	int front;	//队头指针
	int rear;	//队尾指针
}SqQueue;

  初始状态(队空条件)：Q.front==Q.rear==0
  进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。
  出队操作：队不空时，先取队头元素值，再将队头指针加1。

队列的操作：

顺序存储结构存在的问题：

  出队a1、a2，则front指针指向下标为2的位置，rear 不变，如左图所示，再入队a5,此时front 指针不变，rear 指针移动到数组之外。嗯?数组之外，那么就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做 “假溢出”。如右图所示。

三、循环队列

  为了解决假溢出的问题，引入了循环队列，使其头尾相连。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

3.1 实现思路

  当队首指针Q. front=MaxSize-1后，.再前进一个位置就自动到0，这可以利用 除法取余运算(%) 来实现。.
  初始时: Q.front=Q.rear=0。
  队首指针进 1: Q.front= (Q.front+1) % MaxSize。
  队尾指针进 1: Q.rear= (Q.rear+1) % MaxSize。
  队列长度: (Q. rear +MaxSize-Q. front) % MaxSize。
  出队入队时:指针都按顺时针方向进1 (如图所示)

3.2 循环队列队空和队满的判断条件

  循环队列队空和队满的判断条件是什么呢?显然,队空的条件是Q.front==Q.rear
若入队元素的速度快于出队元素的速度，则队尾指针很快就会赶上队首指针，如图(d1)所示，此时可以看出队满时也有Q.front==Q.rear。
  为了区分队空还是队满的情况，有三种处理方式:

1. 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，
   约定以 “队头指针在队尾指针的下一位置作为队满的标志”，如图(d2)所示。
   队满条件: (Q.rear+1) % MaxSize==Q.front
   队空条件仍为: Q.front==Q.rear。
   队列中元素的个数: (Q. rear-Q. front+MaxSize)各MaxSize.
2. 类型中增设表示元素个数的数据成员。这样，队空的条件为Q.size==0;队满的条件为
   Q.size==MaxSize。这两种情况都有Q. front==Q. rear.
3. 类型中设置一个标志变量 flag，以区分是队满还是队空。flag 等于 0 时，若因删除导致
   Q.frontQ.rear ,则为队空; flag 等于 1 时，若因插入导致Q. frontQ. rear,则为队满。（常用）
   

3.3 循环队列的操作

#include<stdio.h>
#include<malloc.h>


#define MaxSize 20
typedef int ElemType;

typedef struct SqQueue
{
	ElemType *data;	//存放队列元素
	int front;	//队头指针
	int rear;	//队尾指针
}SqQueue;

void InitQueue(SqQueue *Q);	//初始化队列
bool isEmpty(SqQueue Q);	//判断队列是否为空
bool isFull(SqQueue Q);	//判断队列是否已满
bool EnQueue(SqQueue *Q,ElemType e);	//入队
bool DeQueue(SqQueue *Q,ElemType *e);	//出队
void PrintQueue(SqQueue pQ);

int main()
{
	SqQueue Q;
	ElemType e;
	InitQueue(&Q);

	EnQueue(&Q,1);
	EnQueue(&Q,2);
	EnQueue(&Q,3);
	EnQueue(&Q,4);
	EnQueue(&Q,5);
	EnQueue(&Q,6);
	EnQueue(&Q,7);
	
	PrintQueue(Q);

	if(DeQueue(&Q,&e))
		printf("出队成功，出队元素为：%d\n",e);
	else
		printf("出队失败\n");

	PrintQueue(Q);

	return 0;
}


void InitQueue(SqQueue *Q)
{
	Q->data = (ElemType *)malloc(sizeof(ElemType)* MaxSize);
	Q->front = Q->rear = 0;
}


bool isEmpty(SqQueue Q)
{
	if(Q.rear == Q.front)
		return true;
	else
		return false;
}

bool isFull(SqQueue Q)
{
	if((Q.rear + 1) % MaxSize == Q.front)
		return true;
	else
		return false;
}

bool EnQueue(SqQueue *Q,ElemType e)
{
	if((Q->rear + 1) % MaxSize == Q->front)
		return false;	//队满报错
	Q->data[Q->rear] = e;
	Q->rear = (Q->rear +1) % MaxSize;	//队尾指针加1取模
	return true;
}

bool DeQueue(SqQueue *Q,ElemType *e)
{
	if(Q->rear == Q->front)
		return false;	//队空报错
	*e = Q->data[Q->front];
	Q->front = (Q->front +1) % MaxSize;	//队头指针加1取模
	return true;
}

void PrintQueue(SqQueue pQ)
{
	int i = pQ.front;

	while(i != pQ.rear)
	{
		printf("%d ",pQ.data[i]);
		i = (i+1) % MaxSize;
	}
	printf("\n");
}

四、队列的链式存储结构

4.1 队列链式存储

  队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指
针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点
  队列的链式存储如图：

可描述为：

typedef struct QNode	/* 结点结构 */
{
   ElemType data;
   struct QNode *next;
}QNode,*QueuePtr;

typedef struct			/* 队列的链表结构 */
{
   QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;

  当Q. front==NULL且Q.rear==NULL时，链式队列为空。
  出队时，首先判断队是否为空,若不空,则取出队头元素,将其从链表中摘除，并让Q. front
指向下一个结点(若该结点为最后一个结点，则置Q. front和Q. rear都为NULL)。入队时,
建立一个新结点，将新结点插入到链表的尾部，并改让Q. rear指向这个新插入的结点(若原队列为空队，则令Q. front也指向该结点)。
  不带头结点的链式队列在操作上往往比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一了。

使用场景： 用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。另外，假如程序中要使用多个队列，与多个栈的情形一样，最好使用链式
队列，这样就不会出现存储分配不合理和“溢出”的问题。

4.2 链式队列的基本操作

4.2.1 初始化

void InitQueue(LinkQueue *Q)
{ 
	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
	Q->front->next=NULL;
}

4.2.2 判队空

bool IsEmpty(LinkQueue Q)
{ 
	if(Q.front==Q.rear)
		return true;
	else
		return false;
}

4.2.3 入队

  入队操作时，其实就是在链表尾部插入结点，如图所示：

其代码如下：

bool EnQueue(LinkQueue *Q,ElemType e)
{ 
	QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
	s->data=e;
	s->next=NULL;
	Q->rear->next=s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */
	Q->rear=s;		/* 把当前的s设置为队尾结点，rear指向s，见图中② */
	return true;
}

4.2.4 出队

  出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear 指向头结点，如图所示：

其代码如下：

bool DeQueue(LinkQueue *Q,ElemType *e)
{
	QueuePtr p;
	if(Q->front==Q->rear)
		return false;
	p=Q->front->next;		/* 将欲删除的队头结点暂存给p，见图中① */
	*e=p->data;				/* 将欲删除的队头结点的值赋值给e */
	Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中② */
	if(Q->rear==p)		/* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */
		Q->rear=Q->front;
	free(p);
	return true;
}

4.3 队列链式结构完整代码

#include<stdio.h>
#include<malloc.h>

#define MaxSize 10;
typedef int ElemType;

typedef struct QNode	/* 结点结构 */
{
   ElemType data;
   struct QNode *next;
}QNode,*QueuePtr;

typedef struct			/* 队列的链表结构 */
{
   QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;


/* 构造一个空队列Q */
void InitQueue(LinkQueue *Q)
{ 
	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
	Q->front->next=NULL;
}

bool IsEmpty(LinkQueue Q)
{ 
	if(Q.front==Q.rear)
		return true;
	else
		return false;
}

/* 插入元素e为Q的新的队尾元素 */
bool EnQueue(LinkQueue *Q,ElemType e)
{ 
	QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
	s->data=e;
	s->next=NULL;
	Q->rear->next=s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */
	Q->rear=s;		/* 把当前的s设置为队尾结点，rear指向s，见图中② */
	return true;
}



/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
bool DeQueue(LinkQueue *Q,ElemType *e)
{
	QueuePtr p;
	if(Q->front==Q->rear)
		return false;
	p=Q->front->next;		/* 将欲删除的队头结点暂存给p，见图中① */
	*e=p->data;				/* 将欲删除的队头结点的值赋值给e */
	Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中② */
	if(Q->rear==p)		/* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */
		Q->rear=Q->front;
	free(p);
	return true;
}


void PrintQueue(LinkQueue Q)
{
	QueuePtr p;
	p=Q.front->next;
	while(p)
	{
		 printf("%d ",p->data);
		 p=p->next;
	}
	printf("\n");
}

int main()
{
	LinkQueue Q;
	ElemType e;

	InitQueue(&Q);

	EnQueue(&Q,1);
	EnQueue(&Q,2);
	EnQueue(&Q,3);
	EnQueue(&Q,4);
	EnQueue(&Q,5);
	EnQueue(&Q,6);
	EnQueue(&Q,7);
	
	PrintQueue(Q);

	if(DeQueue(&Q,&e))
		printf("出队成功，出队元素为：%d\n",e);
	else
		printf("出队失败\n");

	PrintQueue(Q);


	return 0;
}