线性结构之队列

上一篇我们讨论了线性结构中的栈：https://blog.csdn.net/black_carbon/article/details/81105514

 

下面我们来看看线性结构的另外一种类型——队列

与栈相反，队列是一种先进先出（first in first out）的线性表，简称FIFO结构。

它只允许在表的一端进行插入，而在另一端删除元素，类似于我们生活中的排队。在队列中，允许插入的一端叫做队尾，允许删除的一端则称为队头。

与线性表类似，在物理结构上，队列也有两种存储表示——链式存储和顺序存储

由于队列“先进先出”的特点，我们常用链表来表示队列（后面会讲到顺序队列的缺点），下面我们先来讲一下队列的链式存储表示

 

队列的链式存储表示：用链表表示的队列简称为链队列

一个链队列显然需要两个分别指示队头和队尾的指针（头指针和尾指针，头指针用于删除操作，尾指针用于插入操作）才能唯一确定。为了方便起见，我们也给链队列添加一个头结点，并令头指针指向头结点。

空的链队列的判定条件为头指针和尾指针均指向头结点

 

队列的链式存储结构：

/*
	单链队列——队列的链式存储结构
*/
typedef struct QNode{//队列结点类型
	QElemType data;
	struct QNode * next;
}QNode, *QueuePtr;

typedef struct {//队列类型
	QueuePtr front;//队头指针
	QueuePtr rear;//队尾指针
}LinkQueue;

链队列的一些基本操作算法：

构造一个空队列（头指针和尾指针均指向头结点）：

/*
	构造一个空队列
*/
Status InitQueue(LinkQueue &Q)
{
	//带头结点
	Q.front = (QueuePtr)malloc(sizeof(QNode));//分配头结点
	if(!Q.front)
		exit(OVERFLOW);
	Q.rear = Q.front;//空队列标志
	Q.front->next = NULL;
	return OK;
}//InitQueue

 

销毁队列（从头结点开始销毁，直到尾结点）：

/*
	销毁队列
*/
Status DestroyQueue(LinkQueue &Q)
{
	//从头结点开始销毁，利用队尾元素的指针域为NULL来作为结束条件
	while(Q.front)//到Q.front==NULL时结束
	{
		Q.rear = Q.front->next;
		free(Q.front);
		Q.front = Q.rear;
	}//此时Q.front = Q.rear = NULL，不会成为野指针
	return OK;
}//DestroyQueue

 

 

插入新的队尾元素：

/*
	插入新队尾元素
*/
Status EnQueue(LinkQueue &Q, QElemType e)
{
	//插入e作为新的队尾元素
	Q.rear->next = (QueuePtr)malloc(sizeof(QNode));//为新队尾元素分配存储空间
	if(!Q.rear->next)
		exit(OVERFLOW);
	Q.rear = Q.rear->next;//队尾后移
	Q.rear->data = e;//新队尾赋值
	Q.rear->next = NULL;
	return OK;
}//EnQueue

 

 

删除队头元素（这里要注意删除的元素是否同时也是队尾元素，要单独讨论）：

/*
	删除队头元素
*/
Status DeQueue(LinkQueue &Q, QElemType &e)
{
	//取元素前需检查队列是否为空
	if(Q.front == Q.rear)
		return ERROR;
	QueuePtr p = Q.front->next;//队头元素
	Q.front->next = p->next;
	//这里还需注意一点，当取出的元素是队尾元素时，需要对队尾元素重新赋值，否则尾指针将丢失
	if(Q.rear == p)
		Q.rear = Q.front;
	free(p);
	p = NULL;
	return OK;
}//DeQueue

 

队列的顺序存储结构：

与顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。

 

在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。

 

但是这样的顺序队列有一个致命的问题，当分配了一串连续的地址空间给队列后，由于队列“先进先出”的特点，在执行多次插入删除操作后，会出现前面的地址空间没被占用，而后面的地址空间被占满的情况，这时再执行插入操作，会因为数组越界而导致程序代码被破坏，然而此时又不宜如顺序栈那样，进行存储再分配扩大数组空间，因为队列的实际可用空间并未占满。

 

为了解决顺序队列的这个问题，循环队列的概念出现了

循环队列也是队列的顺序表示，不同的是，将顺序队列臆造为一个环状的空间，当分配的地址空间尾端占满而头端未被占用的情况下，可继续循环占用头端地址的空间。

循环队列队空的条件是front==rear，此时不一定为0

循环队列队满的条件是队头指针在队尾指针的下一个位置上

 

下面是循环队列的存储结构：

/*
	循环队列——队列的顺序存储结构
*/
# define MAXQSIZE 100
typedef struct {
	QElemType *base;
	int front;//头指针，若队列不空，指向队列头元素
	int rear;//尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;

 

 

循环队列构造空队列：

/*
	构造一个空循环队列
*/
Status InitQueue(SqQueue &Q)
{
	Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
	if(!Q.base)
		exit(OVERFLOW);
	Q.front = 0;
	Q.rear = Q.front;//空队列标志，并不一定为0
	return OK;
}//InitQueue

 

 

循环队列获取队列长度：

/*
	返回循环队列长度，即元素个数
*/
int QueueLength(SqQueue Q)
{
	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}//QueueLength

 

 

循环队列插入队尾元素：

/*
	循环队列插入新队尾元素
*/
Status EnQueue(SqQueue &Q, QElemType e)
{
	//插入前应先判断队列是否已满
	if((Q.rear+1) % MAXQSIZE == Q.front)//队列满标志(Q.rear+1) % MAXQSIZE == Q.front
		return ERROR;
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear+1)%MAXQSIZE;
	return OK;
}//EnQueue

 

 

循环队列删除队头元素：

/*
	循环队列删除队头元素
*/
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;
}//DeQueue