[C++知识库]队列的链式存储C语言实现

参考资料为《大话数据结构》

typedef int ElemType;
typedef struct {       //结点
	ElemType data;
	struct QNode* next;
}QNode, * QueuePtr;

typedef struct {      //队列链表结构
	QueuePtr front, rear;
}LinkQueue;

1、初始化

//初始化
void InitQueue(LinkQueue* Q) {
	Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
	if (!Q->front) {
		printf("初始化失败\n");
	}
	Q->front->next = NULL;  //带头结点（front指向头结点）
}

2、清除队列

//清除队列
void DestoryQueue(LinkQueue* Q) {
	while (Q->front) {
		Q->rear = Q->front->next;
		free(Q->front);
		Q->front = Q->rear;
	}
}

3、清空队列

//清空队列
void ClearQueue(LinkQueue* Q) {
	QueuePtr p, q;
	Q->rear = Q->front;
	p = Q->front->next;
	Q->front->next = NULL;
	while (p) {
		q = p;
		p = p->next;
		free(q);
	}
}

4、判断是否为空

//判断是否为空队列
bool QueueEmpty(LinkQueue Q) {
	if (Q.rear == Q.front) {
		return true;
	}
	else {
		return false;
	}
}

5、求队列长度

//求队列长度
int QueueLength(LinkQueue Q) {
	QueuePtr p;
	p = Q.front;
	int i = 0;
	while (Q.rear != p) {
		i++;
		p = p->next;
	}
	return i;
}

6、获取队头元素

//获取队头元素
bool GetHead(LinkQueue Q, ElemType* e) {
	if (Q.rear == Q.front) {   //队列为空
		return false;
	}
	else {
		QueuePtr p;
		p = Q.front->next;
		*e = p->data;
		return true;
	}
}

7、插入元素

//插入元素
bool EnQueue(LinkQueue* Q, ElemType e) {
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
	if (!s) {
		//printf("插入失败\n");
		return false;
	}
	else {
		s->data = e;
		Q->rear->next = s;
		s->next = NULL;
		Q->rear = s;
		return true;
	}
}

8、删除元素

//删除元素
bool DeQueue(LinkQueue* Q, ElemType* e) {
	QueuePtr p;
	if (Q->front == Q->rear) {
		return false;
	}
	else {
		p = Q->front->next;
		*e = p->data;
		Q->front->next = p->next;
		if (Q->rear == p) {   //若队头已经是队尾，则让队尾指针指向头结点，队列变空
			Q->rear = Q->front;
		}
		free(p);
	}
}

9、输出

//输出
void ShowQueue(LinkQueue Q) {
	QueuePtr p;
	p = Q.front->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

10、完整+测试程序

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdbool.h>
#include <stdio.h>
typedef int ElemType;
typedef struct {       //结点
	ElemType data;
	struct QNode* next;
}QNode, * QueuePtr;

typedef struct {      //队列链表结构
	QueuePtr front, rear;
}LinkQueue;

//初始化
void InitQueue(LinkQueue* Q) {
	Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
	if (!Q->front) {
		printf("初始化失败\n");
	}
	Q->front->next = NULL;  //带头结点（front指向头结点）
}

//清除队列
void DestoryQueue(LinkQueue* Q) {
	while (Q->front) {
		Q->rear = Q->front->next;
		free(Q->front);
		Q->front = Q->rear;
	}
}

//清空队列
void ClearQueue(LinkQueue* Q) {
	QueuePtr p, q;
	Q->rear = Q->front;
	p = Q->front->next;
	Q->front->next = NULL;
	while (p) {
		q = p;
		p = p->next;
		free(q);
	}
}

//判断是否为空队列
bool QueueEmpty(LinkQueue Q) {
	if (Q.rear == Q.front) {
		return true;
	}
	else {
		return false;
	}
}

//求队列长度
int QueueLength(LinkQueue Q) {
	QueuePtr p;
	p = Q.front;
	int i = 0;
	while (Q.rear != p) {
		i++;
		p = p->next;
	}
	return i;
}

//获取队头元素
bool GetHead(LinkQueue Q, ElemType* e) {
	if (Q.rear == Q.front) {   //队列为空
		return false;
	}
	else {
		QueuePtr p;
		p = Q.front->next;
		*e = p->data;
		return true;
	}
}

//插入元素
bool EnQueue(LinkQueue* Q, ElemType e) {
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
	if (!s) {
		//printf("插入失败\n");
		return false;
	}
	else {
		s->data = e;
		Q->rear->next = s;
		s->next = NULL;
		Q->rear = s;
		return true;
	}
}

//删除元素
bool DeQueue(LinkQueue* Q, ElemType* e) {
	QueuePtr p;
	if (Q->front == Q->rear) {
		return false;
	}
	else {
		p = Q->front->next;
		*e = p->data;
		Q->front->next = p->next;
		if (Q->rear == p) {   //若队头已经是队尾，则让队尾指针指向头结点，队列变空
			Q->rear = Q->front;
		}
		free(p);
	}
}

//输出
void ShowQueue(LinkQueue Q) {
	QueuePtr p;
	p = Q.front->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

//TEST
int main(void) {
	LinkQueue Q;
	InitQueue(&Q);
	ElemType n, d;
	int i;
	printf("是否空队列？%d(1:空 0:否)  ", QueueEmpty(Q));
	printf("队列的长度为%d\n", QueueLength(Q));
	printf("请输入整数（-1表示结束输入）：\n");
	int flag = 1;
	while (flag) {
		scanf("%d", &n);
		if (n == -1) {
			flag = 0;
			break;
		}
		EnQueue(&Q, n);
	}
	printf("插入元素后,队列的长度为%d\n", QueueLength(Q));
	printf("是否空队列？%d(1:空 0:否)  \n", QueueEmpty(Q));
	printf("队列的元素依次为：");
	ShowQueue(Q);
	i = GetHead(Q, &d);
	if (i) {
		printf("队头元素是：%d\n", d);
	}
	DeQueue(&Q, &d);
	printf("删除了队头元素%d\n", d);
	i = GetHead(Q, &d);
	if (i) {
		printf("新的队头元素是：%d\n", d);
	}
	return 0;
}