数据结构与算法——队列

队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
与栈相反，队列是一种先进先出（First In First Out，FIFO）的线性表。

与栈相同的是，队列也是一种重要的线性结构，实现一个队列同样需要顺序表和链表作为基础。

队列的链式存储结构

队列一般使用链表来实现，简称链队列

typedef struct QNode  //定义结点的数据结构
{
    ElemType data;
    struct QNode *Next;
}QNode, *QueuePrt;

typedef struct
{
    QueuePrt front, rear; //队列头、尾指针
}LinkQueue;

将队头指针指向链队列的头结点，而队尾指针指向终端结点。（注：头结点不是必须的，但是为了方便操作，我们加上了）

创建一个队列

创建一个队列要完成两个任务：一是在内存中创建一个头结点，二是将队列的头指针和尾指针都指向这个生成的头结点，因为此时是空队列。

void initQueue(LinkQueue *q)
{
    q->front =q->rear(QueuePtr)malloc(sizeof(QNode));
    if(!q->front)
    exit(0);
    q->front->next = null;
}

入队列操作

InsertQueue(LinkQueue *q,ElemType e)
{
	QueuePtr p;
	p = (QueuePtr)malloc(sizeof(QNode)); //生成结点
	if (p == NULL)
	exit(0);
	p->data = e; //赋值
	p->next = NULL; //下一个结点
	q->rear->next = p; //令q rear的下一个指向p
	q->rear = p; //令q的rear等于p
}

出队列操作

若原队列只有一个元素，那么应该对队尾指针进行处理

DeleteQueue(LinkQueue *q,ElemType *e)
{
	QueuePtr p;
	if(q->front == q->rear) //空队列
	return;
	p = q->front->next; //令p结点等于头结点的下一个结点
	if(q->rear == p)  //判断队尾指针是否等于p 即是否只有一个元素
		q->rear = q->front; //将队尾指针向前移动，再释放p
	free(p);
}

销毁一个队列

由于链队列建立在内存的动态区，因此当一个队列不再有用时应将其销毁，以免过多地占用内存空间。

DestroyQueue(LinkQueue *q)
{
	while(q->front)
	{
		q->rear = q->front->next; //队列只有q的头尾结点
		free(q->front); //释放q的头指针
		q->front = q->rear; 
	}
}