队列的基本操作（顺序队列，循环队列，链队列）_队列的删除操作称为

一. 定义：

1. 和栈相反，队列是一种“先进先出”的线性表。即它只能在表的一端进行插入，在表的另一端删除元素。
2. 在队列中，允许插入的一段叫做队尾，允许删除的一端则称为队头。
3. 队列的插入操作称为进队，删除操作称为出队。
4. 新插入的元素只能添加到队尾，被删除的元素只能是排在队头的元素。
   

二. 队列的顺序表示和实现：

(一) . 顺序队列：

1. 队列的顺序存储结构简称为“顺序队列”，它是由一个一维数组（用于存储队列中的元素）及两个分别指示队头和队尾的变量组成。这两个变量分别称为“队头指针”和“队尾指针”。
2. 通常约定，初始化建空队列时，令front=rear=0。在非空队列中，头指针始终指向队列头元素，而尾指针始终指向rear队列尾元素的下一个位置。
3. 顺序队列的类型声明：

#define MaxSize 20  //指定队列的容量
typedef struct
{
	ElemType data[MaxSize];  //保存队中元素
	int front,rear;          //定义队头和队尾指针 
}SqQueue
1
2
3
4
5
6

(二). 循环队列：

1. 当队列处于上图（d）状态时不可再继续插入新的队尾元素，否则会导致数组越界，但此时又浪费了一些空间。这种因为队满条件设置不合理而导致的“溢出”称为“假溢出”。为了能够充分地使用数组中的存储空间，可以把数组的前端和后端假想地连接起来，形成一个环形的表，即把存储队列元素的表从逻辑上看成一个环。这个环形的表叫做循环队列或环形队列。
2. 经过这样的操作以后，rear和front的值并不是简单的加1或减1的操作。
   队头指针进1： front = (front+1) % MaxSize
队尾指针进1： rear =（rear+1) % MaxSize

从上图，队空为（a）图，队满为（c）图。会发现不论使队满还是队空，rear=front。
此时为了区分队满还是队空：
队空条件设为： front==rear
队满条件设为： （rear+1）% MaxSize == front
也就是说，当rear指到front的前一位置时就认为队列满了。也就是说，队满成立时队中还有一个空闲单元，这样的队中最多只能进队MaxSize-1个元素。
4. 总结起来，上述设置的循环队列Q的4个要素如下：

·Q.front == Q.rear   //队空条件 
·(Q.rear+1) % MaxSize == Q.front  // 队满条件 
·Q.data[Q.rear] = x;    //进队操作 
 Q.rear = (Q.rear+1) % MaxSize;
·x = Q.data[Q.front];   //出队操作 
 Q.front = (Q,front+1) % MaxSize 
1
2
3
4
5
6

5. 循环队列的类型声明：

#define MAXQSIZE 100   //最大队列长度+1
typedef struct
{
	ElemType *base;    //初始化的动态分配存储空间 
	int front;         //头指针，若队列不空，指向队列头元素 
	int rear;          //尾指针，若队列不空，指向队列元素的下一个位置 
}SqQueue;
1
2
3
4
5
6
7

(三). 循环队列的基本算法：

1. 初始化队列：
主要操作：指定sq.front = sq.rear = 0
代码如下：

void InitQueue(SqQueue &Q)
{
	Q.base = (QQlemType *)malloc(MAXQSIZE * sizeof(QElemType));
	if(!Q.base)  //存储分配失败
	   exit(OVERFLOW);
	Q.front = Q.rear = 0; 
}
1
2
3
4
5
6
7

2. 销毁队列运算：
代码如下：

void Destroy(SqQueue &Q)
{
	if(Q.base)  
	   free(Q.base);
	Q.base = NULL;
	Q.front = Q.rear = 0; 
}
1
2
3
4
5
6
7

3. 入队列操作：
主要操作：先判断队列是否已满，若不满，在队列尾指针位置存放x，然后循环加1。
代码如下：

Status EnQueue(SqQueue &Q , QElemType e)
{
	if((Q.rear+1) % MAXQSIZE == Q.front)  //队列满  
	   return ERROR;
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear + 1) % MAXQSIZE;
	return OK; 
}
1
2
3
4
5
6
7
8

4. 出队列操作：
主要操作：先判断队列是否已空，若不空，将队头指针位置的元素赋值给x，然后对头指针循环加1。
代码如下：

Status DeQueue(SqQueue &Q , QElemType &e)
{
	if(Q.front == Q.rear)  //队列空  
	   return ERROR;
	e = Q.base[Q.front] ;
	Q.front = (Q.front + 1) % MAXQSIZE;
	return OK; 
}
1
2
3
4
5
6
7
8

5. 取队头元素：
主要操作： 先判断队列是否已空，若不空，将队头指针前一个位置的元素赋值给x。
代码如下：

Status GetHead(SqQueue Q , QElemType &e)
{
	if(Q.front == Q.rear)  //队列空  
	   return ERROR;
	e = Q.base[Q.front] ;
	return OK; 
}
1
2
3
4
5
6
7

6. 判断队空算法：
主要操作： 若队列为空，则返回1；否则返回0.
代码如下：

Status QueueEmpty(SqQueue Q)
{
	if(Q.front == Q.rear)  //队列空的标志  
	   return TRUE;
	else
	   return FALSE; 
}
1
2
3
4
5
6
7

三. 队列的链式表示和实现：

(一). 链队列：

1. 队列的链式存储结构简称为链队列。
2. 这里采用的链队列是一个同时带有队头指针front和队尾指针rear的单链表。
3. 队头指针指向头结点，队尾指针指向队尾结点即单链表的尾结点，并将队头和队尾指针结合起来构成链队结点。
   
   
4. 数据结点：

typedef struct QNode
{
	ElemType data;          //存放队中元素 
	struct QNode *Next;     //指向下一个结点 
}QNode *QueuePtr;          //数据结点类型 
1
2
3
4
5

链队结点：

typedef struct 
{
	QNode *front;  //队头指针 
	QNode *rear;   //队尾指针 
}LinkQueue;        //链队结点类型 
1
2
3
4
5

5. 总结起来，链队列的4个要素如下：
   ·队空条件：Q.front->next == NULL;
·队满条件：不考虑（因为每个结点是动态分配的）;
·进队操作：创建结点p，将其插入到队尾，并由Q.rear指向它;
·出队操作：删除队头的结点;

(二). 在链队列上实现队列的基本运算：

1. 初始化队列：
主要操作：创建链队列头结点，并置rear和front指向头结点，且指针域为NULL。
代码如下：

void InitQueue(LinkQueue &Q)
{
	if(!(Q.front=Q.rear=(Queueptr)malloc(sizeof(QNode))))  //存储分配失败
	   exit(OVERFLOW);
	Q.front->next = Null; 
}
1
2
3
4
5
6

2. 销毁队列：
依次释放单链表的结点即可
代码如下：

void Destroy(LinkQueue &Q)
{
	while(Q.front)
	{
		Q.rear = Q,front->next;
		free(Q.front);
		Q.front = Q.rear;
	}
}
1
2
3
4
5
6
7
8
9

3. 入队列：
主要操作：创建一个新结点，并将其链接到链队的末尾，并由rear指向它。
代码如下：

void EnQueue(LinkQueue &Q , QElemType e)
{
	QueuePtr p;
	if(!(p=(QueuePtr)malloc(sizeof(QNode))))  //存储分配失败
	   exit(OVERFLOW);
	p->next = Null ;
	Q.rear->next = p ;
	Q.rear = p ;
}
1
2
3
4
5
6
7
8
9

4. 出队列：
主要操作：将front->next 结点的data域值赋给e，并删除该结点。
代码如下：

Status DeQueue(LinkQueue &e , QElemType &e)
{
	QueuePtr p;
	if(Q.front == Q,rear)
	   return ERROR;
	p = Q.front->next;
	e = p->next;
	Q.front->next = p->next;
	if(Q.rear == p)
	   Q.rear = Q.front;
	free(p);
	return OK; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5. 取队头元素：
主要操作：将队头结点的data域值赋给e。
代码如下：

Status GetHead(LinkQueue Q , QElemType &e)
{
	QueuePtr p;
	if(Q.front == Q.rear)  //队列空  
	   return ERROR;
	p = Q.front->next;
	e = p->data ;
	return OK; 
}
1
2
3
4
5
6
7
8
9

6.判断队空：
主要操作： 若链队为空，则返回1；否则返回0.
代码如下：

Status QueueEmpty(LinkQueue Q)
{
	if(Q.front->next == NULL)  //队列空的标志  
	   return TRUE;
	else
	   return FALSE; 
}
1
2
3
4
5
6
7