数据结构第2版 3.4队列

一、队列的定义
对于排队问题，需要有一种能解决共性问题的数据序列的管理组织方式，在这个方式中，多个数据构成一个有序序列，而对这个有序序列的操作（比如插入、删除）有一定要求：只能在一端插入，而在另一端删除。
这样的数据组织方式就是 “队列” 。

队列 也是一个有序线性表，但队列的插入和删除操作是分别在线性表的两个不同端点进行的。

队列简称 “队”，是一种运算受限的线性表。
队列只能选取一个端点进行插入操作，另一个端点进行删除操作。

把进行插入操作的一端称作 队尾（rear）
把进行删除操作的一端称作 队首 或 队头（front）
向队列中插入新元素称为 进队 或 入队，新元素进队后就成为新的队尾元素
从队列中删除元素称为 出队 或 离队，元素出队后，其 后继元素就成为队首元素。

队列的主要特点是 先进先出，所以又把队列称为 先进先出表。

队列的抽象数据类型定义为：
类型名称：队列（Queue）
数据对象集：一个有0个或多个元素的有穷线性表。
操作集：对于一个长度为正整数 MaxSize 的队列Q 属于Queue，记队列中的任意元素X 属于ElementType，队列的基本操作主要有：
（1）Queue CreateQueue(int MaxSize)：生成空队列，其最大长度为 MaxSize；
（2）bool IsFull(Queue Q)：判断队列Q是否已满。是则返回 true，否则返回 false；
（3）bool AddQ(Queue Q, ElementType X)：将元素 X 压入队列Q。若队列已满，返回 false；否则将数据元素 X 插入到队列Q 并返回 true；
（4）bool IsEmpty(Queue Q)：判断队列Q 是否为空，若是则返回 true；否则返回 false；
（5）ElementType Delete(Queue Q)：删除并返回队列头元素。若队列为空，返回错误信息；否则将队列头数据元素从队列中删除并返回。

顺序队的4要素：
（初始的时候 Front = Rear = -1）
队空条件：Front = Rear
队满条件：Rear = MaxSize-1
元素e进队：Rear++； Data[Rear] = e
元素e出队：Front++; e = Data[Front]

把数组的前端和后端连接起来，形成一个环形顺序表，即把存储队列元素的表 从逻辑上看成一个环，称为环形队列或循环队列。

二、队列的实现

队列顺序存储结构的定义

typedef int ElementType;
typedef int Position; 
typedef struct QNode * PtrToQNode;
struct QNode
{
	ElementType *Data;
	Position Front,Rear;
	int MaxSize;
};
typedef PtrToQNode Queue;

创建

Queue CreateQueue(int MaxSize)//创建 
{
	Queue Q = (Queue)malloc(sizeof(Queue)); //分配空间
	Q->Data = (ElementType*)malloc(MaxSize*sizeof(ElementType)); //给Data分配MaxSize个空间
	Q->Front = Q->Rear = 0; //队列的头尾指针
	Q->MaxSize = MaxSize;
	return Q;
}

入队

bool IsFull(Queue Q)
{
	return ((Q->Rear+1) % Q->MaxSize == Q->Front );
}
bool AddQ(Queue Q, ElementType X)//入队 
{
	if(IsFull(Q)) //顺序存储是有一定空间的，所以入队前先做一个判断
	{
		printf("队列满\n");
		return false;
	}
	
	else
	{
		Q->Rear = (Q->Rear+1) % Q->MaxSize ; //循环队列
		Q->Data [Q->Rear ] = X;
		return true;
	}
}

出队

bool IsEmpty(Queue Q)
{
	return (Q->Front == Q->Rear );
}
ElementType DeleteQ(Queue Q)//出队 
{
	if(IsEmpty) //出队前先判断是否为空，空队列没有元素会使删除操作失败
	{
		printf("队列空\n");
		return NULL;
	}
	
	else
	{
		Q->Front = (Q->Front+1) % Q->MaxSize ; //循环队列
		return Q->Data [Q->Front ];
	}
}

队列链式存储结构的定义

typedef int ElementType;
typedef struct Node * PtrToNode;
struct Node
{
	ElementType Data;
	PtrToNode Next;`在这里插入代码片`
};
typedef PtrToNode Position;

typedef struct QNode * PtrToQNode;
struct QNode
{
	Position Front,Rear; //队列头 尾指针 
	int MaxSize; //队列最大容量 
};
typedef PtrToQNode Queue;

链式队列的出队

bool IsEmpty(Queue Q)
{
	return (Q->Front == NULL );
}
ElementType DeleteQ(Queue Q)//出队 
{
	Position FrontCell;
	ElementType FrontElem;
	if(IsEmpty(Q))
	{
		printf("队列空\n");
		return NULL;
	}
	else
	{
		FrontCell = Q->Front ;
		if(Q->Front == Q->Rear ) //队列里只有一个元素 
		  Q->Front = Q->Rear = NULL;
		else
		  Q->Front = Q->Front->Next;
		FrontElem=FrontCell->Data;
		free(FrontCell);
		return FrontElem;
	}
}

我后期应该补一个链式队列的创建和入队的操作。。。