队列的笔记

注（80%来自于大话数据结构，在此只为做笔记而整理） 队列的定义：

队列（Queue）是只允许在一端进行插入 *** 作，而在另一端进行删除 *** 作的线性表

队列是一种先进先出（First In First Out）的线性表，简称FIFO。

允许插入的一端，称为队尾，允许删除的一端称为队头。

循环队列：

假设是长度为5的数组，初始状态是空队列，front与rear指针均指向下标为0的位置。

然后入队a1,a2,a3,a4,front指针依然指向下标为0位置，而rear指针指向下标为4的位置。

出队a1,a2,则front指针指向下标为2的位置，rear不变，再入队a5，此时front指针不变，rear指针移动到数组之外。

嗯？？？rear指针怎么到数组外面去了，那里会是哪里？问题不止于此。

假设队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。

我们把这种现象叫做“假溢出”

循环队列的定义：

所以我们解决假溢出的办法就是后面满了，就再重头开始，也就是头尾相接的循环。

我们把队列的这种头尾相接的顺序存储结构称为循环队列

刚才的例子继续，先前的溢出的rear可以改为指向下标为0的位置，这样就不会造成指针指向不明的问题了！

队列满的条件是 （rear+1）% QueueSize == front 通用的计算队列长度的公式为：（rear-front+QueueSize）%QueueSize 有了这些讲解，下面就是队列的顺序结构以及链式结构的代码：

#include
#include
#include

#define MAXSIZE 10
#define OK 1
#define ERROR -1

//队列的顺序结构
typedef int QElemType; //QElemType类型根据实际情况而定，这里假设为int
//循环队列的顺序存储结构
typedef struct
{
	QElemType data[MAXSIZE];
	int front; //头指针
	int real;  //尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;

//初始化一个空队列Q
int InitQueue(SqQueue *Q)
{
	Q->front=0;
	q->rear=0;
	return OK;
}

//返回Q的元素个数，也就是队列的当前长度
int QueueLength(SqQueue Q)
{
	return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

//若队列未满，则插入元素e为Q的新队尾元素
int EnQueue(SqQueue *Q,QElemType e)
{
	if( (Q->rear+1)%MAXSIZE == Q->front) //队列满的判断
		return ERROR;
	Q->data[Q->rear]=e;                  //将元素e赋值给队尾
	Q->rear=(Q->rear+1)%MAXSIZE;         //rear指针向后移一位置，若到最后则转到数组头部

	return OK;
}

//若队列不空，则删除Q中头元素，用e返回其值
int DeQueue(SqQueue *Q,QElemType *e)
{
	if( Q->front == Q->rear) //判断队列是否为空
		return ERROR;
	*e=Q->data[Q->front];
	Q->front=(Q->front+1)%MAXSIZE;

	return OK;
}

//队列的链式结构—链队列
typedef int QElemType;   //QElemType类型根据实际情况而定，这里假设为int

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

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

//入队 *** 作
//插入元素e为Q的新的队尾元素
int EnQueue(LinkQueue *Q,QElemType e)
{
	QueuePtr s=(QueuePtr)malloc(sizeof(QNode)); //s是新的结点
	if( !s )                //存储分配失败
		return ERROR;
	s->data=e;
	s->next=NULL;
	Q->rear->next=s;        //把拥有元素e的新结点s赋值给原队尾结点的后继，见大话数据结构P100图中①
	Q-rear=s;               //把当前的s设置为队尾结点，rear指向s，见大话数据结构P100图中②
	return OK;
}

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