数据结构(3.6)——队列的链式实现

队列的链式表示为链队列，它实际上是一个同时有队头指针和队尾指针的单链表

队列的链式实现

typedef struct LinkNode {//链式队列结点
	int data;
	struct LinkNode* next;
}LinkNode;

typedef struct {//链式队列
	LinkNode* front, * rear;//队列的队头和队尾指针
}LinkQueue;

  初始化(带头结点)

//初始化队列(带头结点)
void InitQueue(LinkQueue* Q) {
	//初始化时 front、rear 都指向头结点
	Q->front = Q->rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q->front->next = NULL;
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q{
	if (Q.front == Q.rear) {
		return true;
	}
	else {
		return false;
	}
}

  初始化(不带头结点)

//初始化队列(不带头结点)
void InitQueue(LinkQueue* Q) {
	//初始化时 front、rear 都指向NULL
	Q->front = NULL;
	Q->rear = NULL;
}
//判断队列是否为空(不带头结点)
bool IsEmpty(LinkQueue Q{
	if (Q.front==NULL) {
		return true;
	}
	else {
		return false;
	}
}

入队(带头结点)

//新元素入队(带头结点)
void EnQueue(LinkQueue* Q, int x) {
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	Q->rear->next = s;//新结点插入到rear之后
	Q->rear = s;//修改表尾指针
}

入队(不带头结点)

//新元素入队(不带头结点)
void EnQueue(LinkQueue* Q, int x) {
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	if (Q->front == NULL) {//在空队列插入第一个元素
		Q->front = s;
		Q->rear = s;
	}
	else {
		Q->rear->next = s;//新结点插入到rear之后
		Q->rear = s;//修改表尾指针
	}
}

出队(带头结点)

//队头元素出队(带头结点)
bool DeQueue(LinkQueue* Q, int* x) {
	if (Q->front == Q.rear) {
		return false//空队
	}else {
		LinkNode* p = Q->front->next;//让p指针指向要删除的结点(头结点的后一个结点)
		x = p->data;//用变量x返回队头元素
		Q->front->next = p->next;//修改头结点的next指针
		if (Q->rear == p) {//此次是最后一个结点出队
			Q.rear = Q->front;//修改rear指针
		}
		free(p);//释放结点空间
		return true;
	}
}

出队(不带头结点)

//队头元素出队(不带头结点)
bool DeQueue(LinkQueue* Q, int* x) {
	if (Q->front == NULL) {
		return false//空队
	}
	else {
		LinkNode* p = Q->front;//p指向此次出队的结点
		x = p->data;//用变量x返回队头元素
		Q.front = p->next;//修改front指针
		if (Q.rear == p) {//此次是最后一个结点出队
			Q.front = NULL;
			Q.rear = NULL;
		}
		free(p);//释放结点空间
		return true;
	}
}

总结