队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表

进行插入操作的一端称为队尾（入队列），进行删除操作的一端称为队头（出队列）

队列最大的特点就是：先进先出，后进后出

队列可分为顺序队列、循环队列、链式队列

1）顺序队列放在线性表中，有两种情况：

队头不动，出队列时队头后的所有元素向前移动（缺陷：出队搬移数据会比较繁琐）

对头移动，出队时队头向后移动一个位置（缺陷：会出现假溢出的问题）

扩充：假溢出指的是实际上是有空间存放数据的，可根据判断却认为没有空间

2）循环队列解决了假溢出的问题（也就是上面的rear到5了之后还可以回到0的位置）

扩充：可是现在刚解决了一个问题又出现另外一个问题，循环队列如何得知队列的空和满呢？两种情况如何区分？？

有才的人类想到三个办法：少用一个存储单元；设置一个标记位；设置一个计数器

3）链式队列（上面两种空间的大小毕竟是死的，存放数据总有放满的时候，再存就会溢出）

链式队列是一种特殊的单链表，只在单链表上进行头删和尾插操作

 

在此我使用链式队列（操作相对简单^0^）

typedef int qDataType;

//结点中含有数据和指向下一个结点的指针
typedef struct qNode
{
	qDataType data;
	struct qNode *pNext;
}qNode;

//队列中含有指向链表头和尾的两个指针和队列中元素的个数
typedef struct queue
{
	qNode *pFront;
	qNode *pRear;
	int size;
}queue;

在队列中我实现了以下的基本操作

//队列的初始化
void queueInit(queue *pQ);

//队列的销毁
void queueDestroy(queue *pQ);

//队列数据的打印
void queuePrintf(queue pQ);

//入队操作
void queuePush(queue *pQ, qDataType data);

//出队操作
void queuePop(queue *pQ);

//队首元素
qDataType queueFront(queue *pQ);

//是否为空队列
int queueIsEmpty(queue *pQ);

//队列的大小
int queueSize(queue *pQ);

1）初始化

void queueInit(queue *pQ)
{
	assert(pQ != NULL);
	//初始化队列没有数据结点
	pQ->pFront = NULL;
	pQ->pRear = NULL;
	pQ->size = 0;
}

2）销毁

void queueDestroy(queue *pQ)
{
	assert(pQ);
	qNode *node;
	while (pQ->pFront != NULL)
	{
		node = pQ->pFront;
		pQ->pFront = pQ->pFront->pNext;
		free(node);
	}
	pQ->pFront = NULL;
	pQ->pRear = NULL;
	pQ->size = 0;
}

3）打印

void queuePrintf(queue pQ)
{
	while (pQ.pFront != NULL)
	{
		printf("%d->", pQ.pFront->data);
		pQ.pFront = pQ.pFront->pNext;
	}
	printf("NULL\n");
}

#if 0
void queuePrintf(queue *pQ)
{
	assert(pQ != NULL);
	qNode *node = pQ->pFront;
	while (node != NULL)
	{
		printf("%d->", node->data);
		node = node->pNext;
	}
	printf("NULL\n");
}
#endif

4）入队

void queuePush(queue *pQ, qDataType data)
{
	assert(pQ != NULL);
	qNode *newNode = (qNode *)malloc(sizeof(qNode));
	assert(newNode);
	newNode->data = data;
	newNode->pNext = NULL;
	pQ->size++;
	//当前链表中无结点
	if (pQ->pFront == NULL)
	{
		pQ->pFront = newNode;
		pQ->pRear = newNode;
		return;
	}
	pQ->pRear->pNext = newNode;
	pQ->pRear = newNode;
}

5）出队

void queuePop(queue *pQ)
{
	assert(pQ != NULL);
	assert(pQ->size > 0);
	qNode *node = pQ->pFront;
	pQ->size--;
	//当前只有一个结点
	if (pQ->pFront == pQ->pRear)
	{
		free(node);
		pQ->pFront = NULL;
		pQ->pRear = NULL;
		return;
	}
	pQ->pFront = pQ->pFront->pNext;
	free(node);
}

6）队首

qDataType queueFront(queue *pQ)
{
	assert(pQ != NULL);
	assert(pQ->size > 0);
	return pQ->pFront->data;
}

7）判空

int queueIsEmpty(queue *pQ)
{
	assert(pQ != NULL);
	return pQ->size == 0 ? 1 : 0;
}

8）大小

int queueSize(queue *pQ)
{
	assert(pQ != NULL);
	return pQ->size;
}

总结：了解了之间单链表博客的内容后，相信对队列的操作就容易多了。因为我们只能一边出一边入