考研篇——数据结构王道3.2.3_队列的链式实现

1.链队列

队列是一种线性结构，线性是指其在逻辑结构，上一节我们顺序存储实现队列，这次链式存储实现队列。与单链表的实现不同的是，只能在表头删除，表尾插入。

2.代码实现

2.1 带头结点

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LinkNode {
	ElemType data;
	struct LinkNode* next;
}LinkNode;
typedef struct {
	LinkNode* front, * rear;
	//int size;//如果频繁使用队列长度的话，考虑增加变量size记录，否则每遍历的时间复杂度是O(n)
}LinkQueue;
//带头结点
void InitQueue(LinkQueue& Q)
{
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	if (Q.front == NULL)
		return;
	Q.front->next = NULL;
}
bool IsEmpty(LinkQueue Q)
{
	if (Q.front == Q.rear)//Q.front->next==NULL
		return true;
	else
		return false;
}
void EnQueue(LinkQueue& Q, ElemType x)
{
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	if (s == NULL)
		return;
	s->next = NULL;
	s->data = x;
	Q.rear->next = s;
	Q.rear = s;
}
bool DeQueue(LinkQueue& Q, ElemType& x) {
	if (Q.front == Q.rear)
		return false;
	LinkNode* s = Q.front->next;
	x = s->data;
	Q.front->next = s->next;
	if (Q.rear == s)
		Q.rear = Q.front;
	free(s);
	return true;
}

2.2 不带头结点

与代码2.1相同的部分省略

//不带头结点
void InitQueue1(LinkQueue &Q)
{
	Q.front = Q.rear = NULL;
}
bool IsEmpty1(LinkQueue Q)
{
	if (Q.front == NULL)//Q.rear==NULL
		return true;
	else
		return false;
}
void EnQueue1(LinkQueue& Q, ElemType x)
{
	LinkNode* s= (LinkNode*)malloc(sizeof(LinkNode));
	if (s == NULL)
		return;
	s->next = NULL;
	s->data = x;
	if (Q.rear == NULL)
		Q.front = Q.rear = s;//不带头结点，第一个元素入队时单独处理，与后续元素入队不同的是，要更改头指针的指向
	else {
		Q.rear->next = s;
		Q.rear = s;
	}
}
bool DeQueue1(LinkQueue& Q, ElemType& x) {
	if (Q.front == Q.rear)
		return false;
	LinkNode* p = Q.front;
	x = p->data;
	Q.front = p->next;
	if (Q.rear == p)
		Q.rear = Q.front=NULL;
	free(p);
	return true;
}

总结

链式存储实现的队列与顺序存储相比，好处在于，顺序存储的空间是预分配的，一旦满了就不能再插入。但链式存储一般不存在队满的情况，除非内存不足。
在书写代码时，思考不带头结点与带头节点在操作上的区别，是否单独处理要分情况。