1.队列

1.1 队列的基本概念

1. 队列的定义

队列(Queue)简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在另一端进行删除。向队列中插入元素称为入队或者进队，删除元素称为出队或者离队。特点是先进先出。如下所示

2.队列常见的基本操作

InitQueue(&Q):初始化队列,构造一个空队列Q。

QueueEmpty(Q):判断队列空，若为空则返回true,否则返回false。

EnQueue(&Q,x):入队，若队列Q未满,将x加入，使之成为新的队尾。

DeQueue(&Q,&x):出队，若队列Q非空，则删除队头元素,并用x返回。

GetHead(Q,&x):读队头元素,若队列Q非空,则将队头元素赋值给x。

1.2 队列的顺序存储结构

1. 队列的顺序存储

队列的顺序存储实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，队列的顺序存储类型如下所示

#define MaxSize 50		//定义队列中元素的最大个数
typedef	struct{
	int data[MaxSize];	//存放队列元素 
	int front,rear; 	//队头指针和队尾指针 
}SqQueue; 

初始状态(队空条件):Q.front等于Q.rear等于0。

进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。

出队操作:队不空时，先取队头元素值，再将队头指针加1。

当用Q.rear==MaxSize作为队满条件时，会出现“上溢出”，但这种溢出只是一种假溢出。

2.循环队列

将顺序队列臆造成一个环状的空间,即把存储队列元素的表从逻辑上视为一个环,称为循环队列。当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到0，这可以利用除法取余运算(%)实现。

初始化:Q.front=Q.rear=0。

队首指针进1：Q.front=(Q.front+1)%MaxSzie。

队尾指针进1：Q.rear=(Q.rear+1)%MaxSzie。

队列长度：(Q.rear+MaxSzie-Q.front)%MaxSize。

队满条件:(Q.rear+1)%MaxSize==Q.front。

队空条件：Q.rear==Q.front。

3.循环队列的操作

(1)初始化

//初始化
void InitQueue(SqQueue &Q){
	Q.rear=Q.front=0; 	//初始化队首、队尾指针 
}

(2)判断队是否为空

//判断队空
bool isEmpty(SqQueue Q){
	if(Q.rear==Q.front)		//判断队空条件 
		return true;
	else 
		return false;
}

(3)入队操作

//入队
bool EnQueue(SqQueue &Q,int x){
	if((Q.rear+1)%MaxSize==Q.front)	//队满条件 
		return false;
	Q.data[Q.rear]=x;
	Q.rear=(Q.rear+1)%MaxSize;	//队尾指针加1取模
	return true; 
} 

(4)出队操作

//出队
bool DeQueue(SqQueue &Q,int &x){
	if(Q.front==Q.rear)	 	//队满报错
		return false;
	x=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize; 	//队头指针加1取模 
} 

(5)主函数main()

    int main(){
	SqQueue Q;
	InitQueue(Q);
	int r,x,f;
	r=Q.rear;
	cin>>x;
	while((r+1)%MaxSize!=Q.front){
		EnQueue(Q,x);
		r=(r+1)%MaxSize;
		cin>>x;
	}
	cout<<"输出队列为:"<<endl;
	while(DeQueue(Q,f)){
		cout<<f<<"\t";
	}
	cout<<endl; 
	cout<<"留下一个位置存放为指针Q.data[Q.rear]:"<<Q.data[Q.rear];	 
}

1.3

1.队列的链式存储结构

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。不存在内存溢出的问题。如下所示

队列的链式存储类型如下所示

    typedef struct	LinkNode{			//链式队列结点 
	int data;
	struct LinkNode *next;
}LinkNode;
typedef struct{			//链式队列 
	LinkNode *front,*rear;		//队列的队头和队尾指针 
}LinkNode;

当Q.front等于NULL且Q.rear等于NULL时，链式队列为空。

出队时，首先判断队是否为空，若不为空，则取队头元素，将其从链表中删除，并让Q.front指向下一个结点(若该结点为最后一个结点，则置Q.front和Q.rear都为NULL)。入队时，建立一个新的结点,将新结点插入到链表的尾部，并改让Q.rear指向这个新插入的结点(若元队列为空队列，则令Q.front也指向改结点)。

如果设计成一个带头结点的单链表，这样插入和删除就得到了统一，如下所示

2.链式队列的基本操作

(1)初始化

    //初始化
void InitQueue(LinkQueue &Q){
	Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));		//建立头结点
	Q.front->next=NULL; 
}

(2)判队空

    //判断队空
bool IsEmpty(LinkQueue Q){
	if(Q.front==Q.rear)
		return true;
	else 
		return false; 
}

(3)入队操作

    //入队 
void EnQueue(LinkQueue &Q,int x){
	LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));	//创建新结点，插入链尾 
	s->data=x;
	s->next=NULL;
	Q.rear->next=s;
	Q.rear=s;
	
}

(4)出队操作

    //出队
bool DeQueue(LinkQueue &Q,int &x){
	if(Q.front==Q.rear)		//空队 
		return false;
	LinkNode *p=Q.front->next;
	x=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)
		Q.rear=Q.front;		//若原队列中只有一个结点，删除后变空 
	free(p);
	return true;
} 

(5)主函数main()

    int main(){
	LinkQueue Q;
	InitQueue(Q);
	int x;
	cin>>x;
	while(x!=9999){
		EnQueue(Q,x);
		cin>>x;
	}
	cout<<"出队列的数据为:";
	int f;
	while(DeQueue(Q,f)){
		cout<<f<<"\t";
	}
	
}