队列的链式存储结构及实现

亦凉 2022-06-01 22:38 180阅读 0赞

**队列的链式存储结构，其实就是线性表的单链表，只不过它只是尾进头出而已，我们把它简称为链队列**。为了操作上的方便，**我们将队头指针指向链队列的头结点，而队尾指针指向终端节点**。如果

![Center][]

空队列时，front和rear都指向头结点。

![Center 1][]

**入队操作：**

在队尾添加元素,先将队尾元素的next指向添加的元素，然后将队尾指针重新指向新的队尾即可。

![SouthEast][]

**出队操作：**

头结结点指向的结点即为队头结点，出队操作，就是把队头结点干掉，先把头结点指向新的队头结点（也就是旧的队头结点的后继结点），然后释放旧的队头结点。 **如果链表除头结点外只剩一个元素时，则需将rear指向头结点即可**。

![SouthEast 1][]

下面是队列链式存储结构实现的具体代码：

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>
    #define QUEUESIZE 10
    #define ERROR 0 
    #define OK 1 
    #define TRUE 1 
    #define FALSE 0
    #define EleType int 
    #define Status int
    //链队列结点
    typedef struct QueueNode
    {
    	EleType e;//数据域
    	struct QueueNode* next;//指针域
    }QueueNode,*LinkQueuePoi;
    typedef struct LinkQueue
    {
    	LinkQueuePoi front;//指向头结点
    	LinkQueuePoi rear;//指向队尾
    }LinkQueue;
    /*
    初始化链队列
    链队列为空时，链队列队头指针队尾指针均指向头结点
    */
    Status InitLinkQueue(LinkQueue* queue)
    {
    	//空指针
    	if (!queue)
    	{
    		return ERROR;
    	}
    	QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));//头结点
    	node->next = NULL;
    	queue->front = queue->rear = node;
    	return OK;
    }
    /*
    清空链队列
    将所有元素释放
    */
    Status CleaerLinkQueue(LinkQueue* queue)
    {
    	//空指针
    	if (!queue)
    	{
    		return ERROR;
    	}
    	//空链队列
    	if (queue->front == queue->rear)
    	{
    		return ERROR;
    	}
    	QueueNode* node = queue->front->next;//队头元素
    	while (node)
    	{
    
    		queue->front->next = node->next;//指向新的队头结点
    		if (queue->rear == node)//当删除的是队尾元素时，将队尾指针指向头结点
    		{
    			queue->rear = queue->front;
    		}
    		free(node);//释放旧的队头结点
    		node = queue->front->next;
    	}
    	return OK;
    }
    /*
    判断链队列是否为空队列
    */
    Status EmptyLinkQueue(LinkQueue* queue)
    {
    	//空指针
    	if (!queue)
    	{
    		return ERROR;
    	}
    	//空链队列
    	if (queue->front == queue->rear)
    	{
    		return TRUE;
    	}
    	return FALSE;
    }
    /*
    获取链队列长度
    */
    int LengthLinkQueue(LinkQueue* queue)
    {
    	//空指针
    	if (!queue)
    	{
    		return ERROR;
    	}
    	//空链队列
    	if (queue->front == queue->rear)
    	{
    		return 0;
    	}
    	QueueNode* node = queue->front->next;
    	int num = 0;
    	while (node)
    	{
    		node = node->next;
    		num++;
    	}
    	return num;
    }
    /*
    在链队列队尾添加元素
    先将新元素添加到链表尾部，然后将队列尾指针指向这个新元素
    */
    Status AddQueue(LinkQueue* queue,EleType e)
    {
    	//空指针
    	if (!queue)
    	{
    		return ERROR;
    	}
    	QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    	if (!node)
    	{
    		return ERROR;
    	}
    	node->next = NULL;
    	node->e = e;
    	queue->rear->next = node;//将新结点添加到链表表中
    	queue->rear = node;//队尾指针指向新的队尾结点
    	return OK;
    }
    /*
    从链队列中删除队头元素
    先将头结结点指向新的队头结点，然后释放原来的队头结点
    */
    Status DelQueue(LinkQueue* queue, EleType *e)
    {
    	//空指针
    	if (!queue)
    	{
    		return ERROR;
    	}
    	//注意queue->front是头结点，头结点指向的结点才是队头结点
    	QueueNode* node = queue->front->next;//旧队头结点
    	*e = node->e;
    	queue->front->next = node->next;//队头指针指向新的队头结点
    	//当删除的是队尾元素时，将队尾指针指向头结点
    	if (node = queue->rear)
    	{
    		queue->rear = queue->front;
    	}
    	return OK;
    }
    /*
    打印链队列元素
    */
    void PrintfLinkQueue(LinkQueue* queue)
    {
    	if (!queue)
    	{
    		return;
    	}
    	QueueNode* node = queue->front->next;
    	while (node)
    	{
    		printf("%d,", node->e);
    		node = node->next;
    	}
    	printf("\n");
    	return;
    }
    int main(int argc, char *argv[])
    {
    	LinkQueue queue;
    	InitLinkQueue(&queue);
    	AddQueue(&queue, 1);
    	AddQueue(&queue, 2);
    	AddQueue(&queue, 3);
    	AddQueue(&queue, 4);
    	AddQueue(&queue, 5);
    	AddQueue(&queue, 6);
    	AddQueue(&queue, 7);
    	AddQueue(&queue, 8);
    	AddQueue(&queue, 9);
    	printf("链队列元素个数：%d\n",LengthLinkQueue(&queue));
    	printf("展示元素：\n");
    	PrintfLinkQueue(&queue);
    	int e1, e2;
    	DelQueue(&queue, &e1);
    	DelQueue(&queue, &e2);
    	printf("删除元素：%d,%d\n", e1, e2);
    	printf("展示元素：\n");
    	PrintfLinkQueue(&queue);
    	printf("链队列元素个数：%d\n", LengthLinkQueue(&queue));
    	CleaerLinkQueue(&queue);
    	printf("清空元素后，长度为%d，rear = %p，front=%p",LengthLinkQueue(&queue), queue.rear,queue.front);
    	printf("\n");
    	return 0;
    }

验证结果截图：

![SouthEast 2][]

对于循环队列与链队列的比较，可以从时间和空间2方面来考虑，从时间上，他们的基本操作都是常数时间，即都为O(1)，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则2者还是有些细微的差异。对于空间方面来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列就不存在这个问题，尽管它需要一些指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。

[Center]: /images/20220602/c4274dfe711240718801b9a80224d618.png
[Center 1]: /images/20220602/32d4e5ca631c4c2b94140165f7f70fdd.png
[SouthEast]: /images/20220602/a4802fd2eb8a4895b92fe1a89c45b100.png
[SouthEast 1]: /images/20220602/8b387322a50e495798930ded049bb557.png
[SouthEast 2]: /images/20220602/881d577d95a640cea89abdf5c07b3982.png