数据结构之队列

队列的定义：

只允许在一端进行插入（入队），在另一端删除（出队）的线性表。

举例：

在队末进行入队，在对头进行出队。

队列的特点：

先进入队列的元素先出队（先进先出）

空队列：

对头和队尾元素：

队列的基本操作：

定义队列：

#define Maxsize 10
typedef struct
{
	ElemType data[Maxsize];//用静态数组存放队列元素
	int front, rear;//队头和队尾指针
}SqQueue;

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

void InitQueue(SqQueue&Q)
{
	Q.rear = Q.front = 0;//初始化时，队头，队尾指针指向0
}

DestoryQueue(&Q):销毁队列，销毁并释放队列Q所占用的内存空间。

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

bool EnQueue(SqQueue& Q, ElemType x)
{
	if (队列已满)//判断队列是否存满
		return false;
	Q.data[Q.rear] = x;//将x插入队尾
	Q.rear = (Q.rear + 1)%Maxsize;//队尾指针加1取模
	return true;
}

那么队列已满的条件是不是rear==Maxsize?

那当然不是！

举例：

如果是上述这种情况，虽然此时rear==Maxsize，但是队列中的前几个元素已经出队列了，此时的队列并没有存满。

正确的判断条件是：

方案一：

(Q.rear + 1)%Maxsize//(9+1)%10=0使rear指向0

相当于将线性存储在逻辑结构上变成了环状：

队列已满的条件：

队尾指针的再下一个位置是对头，即（Q.rear+1）%Maxsize==Q.front

注意：这里无法将所有的空间都使用，因为如果当rear和front指向同一个位置，那么这不就恰好成为了空队列的条件吗？因此我们必须牺牲一个存储单元。

方案二：

方案三：

当rear指向的是队尾元素时的基本操作：

队列元素个数：

（rear+Maxsize-front）%Maxsize

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

bool DeQueue(SqQueue& Q, ElemType& x)
{
	if (Q.rear == Q.front)//空栈则报错
	{
		return false;
	}
	x = Q > data[Q.front];
	Q.front = (Q > front + 1) % Maxsize;//从队头元素开始，使元素依次出队
	return true;
}

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

bool GetHead(SqQueue Q, ElemType& x)
{
	if (Q.rear == Q.front)//队空则报错
		return false;
	x = Q.data[Q.front];
	return true;
}

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

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

队列的链式实现：

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

链队列：链式存储实现的队列

链式队列的初始化：

//带头结点
void InitQueue(LinkQueue& Q)
{
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));//使指针都指向头结点
	Q.front->next = NULL;
}

//不带头结点
void InitQueue(LinkQueue& Q)
{
	Q.front = NULL;
	Q.rear = NULL;
}

链式队列的判空操作：

//带头结点
bool IsEmpty(LinkQueue Q)
{
	if (Q.front == Q > rear)
		return true;
	else
		return false;
}

//不带头结点
bool IsEmpty(LinkQueue Q)
{
	if (Q.front == NULL)
		return true;
	else
		return false;
}

链式队列的入队：

//带头结点
void EnQueue(LinkQueue& Q, ElemType x)
{
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	Q.rear->next=s;//新节点插入rear之后
	Q.rear = s;//修改表尾指针
}

//不带头结点
void EnQueue(LinkQueue& Q, ElemType x)
{
	LInkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	if (Q.front == NULL)//在空队列中插入第一个元素
	{
		//修改队头队尾指针
		Q.front = s;
		Q.rear = s;
	}
	else
	{
		Q.rear->next = s;//新节点插入到rear节点之后
		Q.rear = s;//修改rear指针
	}
}

链式队列的出队操作：

//带头结点
bool DeQueue(LinkQueue& Q, ELemType& x)
{
	if (Q.front == Q.rear)//空队
		return false;
	LinkNode* p = Q.front->next;
	x = p->data;//用变量x返回队头元素
	Q.front->next = p->next;//修改头结点的next指针
	if (Q > rear == p)//最后一个节点出队
	{
		Q.rear = Q.front;//修改rear指针
	}
	free(p);
	return true;
}

//不带头结点
bool DeQueue(LinkQueue& Q, ElemType& x)
{
	if (Q.front == NULL)//空队列
		return false;
	LinkNode* p = Q.front;//p指向此次出队列的节点
	x = p->data;//用变量x返回队头元素
	Q.front = p->next;//修改front指针
	if (Q.rear == p)//最后一个节点出队
	{
		Q.front = NULL;
		Q.rear = NULL;
	}
	free(p);
	return true;
}