Queue队列的实现

队列的基本概念及讨论

队列只能在表的一端进行插入，这一端叫作队尾，而在另一端进行删除，这一端叫队头。这样的结构有先进先出FIFO(first in first off)的特点，也可以是后进后出。链表可以用来实现队列或者循环队列，数组一般用来实现循环队列，因为数组在前端的插入或删除操作花费O(N)时间。队列的应用有很多，比如打印机是按照作业到达的顺序排列起来的，生活中的排队是先到的先处理。

队列的基本实现

1.不循环队列

基本思想

如果用单链表实现，则除了链表结构外还需要多声明一个队列结构来指示在链表中的队头位置和队尾位置，这样就可以使队列的入队出队只花费O(1)时间。若用带头双向循环链表则可以选择不用声明队列结构，因为入队出队也只花费O(1)时间。这里我们用单链表实现

结构声明和函数声明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;

typedef struct ListNode* PtrToNode;
typedef PtrToNode Position;

typedef struct Queue* Queue;
struct ListNode
{
	DataType data;
	PtrToNode next;
};
struct Queue
{
	Position front;
	Position rear;
};

Queue QueueCreate();
void DeQueue(Queue q);
void EnQueue(Queue q, DataType x);
DataType QueueFront(Queue q);
DataType QueueRear(Queue q);
int IsEmpty(Queue q);
int QueueSize(Queue q);
void QueueDestroy(Queue q);
void QueuePrint(Queue q);
void QueueDestroy(Queue q);

队列创建：

Queue QueueCreate()
{
	Queue q = (Queue)malloc(sizeof(struct Queue));
	if (q == NULL)
	{
		printf("out of spaces!\n");
		exit(-1);
	}
	q->front = NULL;
	q->rear = NULL;
	return q;
}

入队和出队：

void EnQueue(Queue q, DataType x)
{
	assert(q);
	PtrToNode newNode = (PtrToNode)malloc(sizeof(struct ListNode));
	if (newNode == NULL)
	{
		printf("out of spaces!\n");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	if (IsEmpty(q))
	{
		q->front = q->rear = newNode;
	}
	else
	{
		q->rear->next = newNode;
		q->rear = newNode;;
	}
}
void DeQueue(Queue q)
{
	assert(q);
	if (IsEmpty(q))
		return;

	Position head = q->front;
	q->front = q->front->next;
    if (q->front == NULL)
		q->rear = NULL;

	free(head);
}

出队的函数编写需要非常仔细，稍不注意可能就会漏掉对q->rear的更新，最后需要判断队头是否走到了空，如果队头走到了空，那么队尾也应该置为空 否则就会变成非法指针。

返回队头和队尾：

DataType QueueFront(Queue q)
{
	assert(q);
	assert(!IsEmpty(q));
	return q->front->data;
}
DataType QueueRear(Queue q)
{
	assert(q);
	assert(!IsEmpty(q));
	return q->rear->data;
}

判空和返回大小

判断空可以有几种方法，可以只判断队头为空、只判断队尾为空或者判断队头队尾都为空。如果是后面两种写法，那么出队函数若忘记了对q->rear的更新，程序的错误就会在判空函数上得以找到，如果是第一种问题就会较严重，程序的错误很隐蔽，即使忘了更新q->rear，程序也能正常运行。

int IsEmpty(Queue q)
{
	return q->front == NULL;
}
int QueueSize(Queue q)
{
	assert(q);
	Position cur = q->front;
	int count = 0;
	while (cur)
	{
		cur = cur->next;
		count++;
	}
	return count;
}

打印和销毁：

void QueuePrint(Queue q)
{
	assert(q);
	while (!IsEmpty(q))
	{
		printf("%d ", QueueFront(q));
		DeQueue(q);
	}
	printf("\n");
}
void QueueDestroy(Queue q)
{
	assert(q);
	while (!IsEmpty(q))
	{
		DeQueue(q);
	}
	free(q);
}

2.循环队列

基本思想

由于链表实现循环队列较为简单，我们来讨论数组的循环队列实现。循环队列是在一定的空间内，循环利用空间，比如一个给定的数组大小为10，front为数组头，rear为数组尾，当入队十次时，队列似乎是满了，下一次入队rear就会到达一个数组外的位置，然而队列中也许只有不到十个元素，因为若干个元素可能已经出队了，所以出队的那些空间又可以利用起来。解决方法是让rear回到数组开头的位置。还有一些问题需要注意，一开始时基准情形rear给定为0，front给定为1。此时表示为空队列，当经过9次入队时，rear=9，再一次入队，rear回到开头rear=0。此时表示满队列。我们发现rear=0，front=1既可以表示空队列也可以表示满队列。出现这种分歧有两种解决方法，第一种是在队列结构中加上size字段，当size为0时表示空队列，size为10时表示满队列。第二种是不让这种情况出现，少存储一个数据，也就是说当队列大小为N时，有N-1个数据时队列就满了。因为如果要让这种情况出现，需要rear绕一圈回到原位置，只要少存一个让rear回不到原位置即可。我们采用第一种方法，第二种在编程中需要格外注意，需要存储k个元素就需要申请k+1的空间。且队列为空时，front是rear的下一个位置，队列为满时，front是rear的下两个位置。

结构声明与函数声明：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define MINSIZE (5)
typedef int DataType;
typedef int Position;
typedef struct QueueRecord* Queue;
struct QueueRecord
{
	DataType* data;
	int front;
	int rear;
	int capacity;
	int size;
};

Queue QueueCreate(size_t size);
void EnQueue(Queue q, DataType x);
void DeQueue(Queue q);
DataType QueueFront(Queue q);
DataType QueueRear(Queue q);
Position NextPosition(Queue q, Position p);
int IsEmpty(Queue q);
int IsFull(Queue q);
void PrintQueue(Queue q);
void QueueDestroy(Queue q);

队列创建：

Queue QueueCreate(size_t size)
{
	Queue q = (Queue)malloc(sizeof(struct QueueRecord));
	if (q == NULL)
	{
		printf("out of spaces!\n");
		exit(-1);
	}
	q->capacity = size > MINSIZE ? size : MINSIZE;
	q->data = (DataType*)malloc(sizeof(DataType) * q->capacity);
	if (q->data == NULL)
	{
		printf("out of spaces!\n");
		exit(-1);
	}
	q->rear = 0;
	q->front = 1;
	q->size = 0;
	return q;
}

入队和出队：

void EnQueue(Queue q, DataType x)
{
	assert(q);
	if (IsFull(q))
	{
		printf("EnQueue failed! Queue is already full\n");
		return;
	}
	q->rear = NextPosition(q, q->rear);
	q->data[q->rear] = x;
	q->size++;
}
void DeQueue(Queue q)
{
	if (!IsEmpty(q))
	{
		q->front = NextPosition(q, q->front);
		q->size--;
	}
}

判断空和满：

int IsEmpty(Queue q)
{
	return q->size == 0;
}
int IsFull(Queue q)
{
	return q->size == q->capacity;
}

寻找下一个位置：

Position NextPosition(Queue q, Position p)
{
	if (++p == q->capacity)
		return 0;
	return p;
}

返回队头和队尾：

DataType QueueFront(Queue q)
{
	assert(q);
	return q->data[q->front];
}
DataType QueueRear(Queue q)
{
	assert(q);
	return q->data[q->rear];
}

打印和销毁：

void PrintQueue(Queue q)
{
	while (!IsEmpty(q))
	{
		printf("%d ", QueueFront(q));
		DeQueue(q);
	}
}
void QueueDestroy(Queue q)
{
	assert(q);
	free(q->data);
	free(q);
}