————————————本栏目旨在讨论计算机知识，欢迎交流—————————————

        上一章，我们讨论了顺序栈和链式栈，这一章，我们将讲解线性结构的最后一个部分——顺序队列和链式队列。相比于栈结构的同端进出，就像原肠生物，而队列则是尾部入队和头部出队，就像后口生物一样。

        如图：

        那么，如何来实现入队和出队呢？答曰：请看VCR：

        但是，使用这种直观地朴素方法我们有个致命的问题——假溢出问题。在顺序栈的实现中我们的队头队尾类似于双指针滑动窗口算法，但是每次划过了之后空间不会清除，导致看起来一共占了（rear-head）个空间，但是其实远远不止这么多。前面的都没删除，很容易产生假溢出的效果并且及其占用空间。

        于是，循环赋值的方法应运而生。它的基本原理是：通过取余操作来覆盖删除的数值，直到队头与队尾相撞结束。那么，现在我们有两种思路：1、通过设定一个bool类型变量flag，每次通过判断来操作。2、虚空一个空间，每次入队的时候探针向前虚指，碰到了头才操作。比起第一种方法，第二种用了空间换时间的方法，效率更高。

如下：

if ((queue->rear + 1) % MaxQueueSize == queue->front) {
		fprintf(stderr, "Queue Full!\n");
		return -1;
	}
//如果相等，则表明队列是满的

queue->rear = (queue->rear + 1) % MaxQueueSize;
	queue->data[queue->rear] = e;
//入队操作

if (queue->rear == queue->front) {
		fprintf(stderr, "Queue Empty!\n");
		return -1;
	}
//如果对撞，表明队列是空了

	queue->front = (queue->front + 1) % MaxQueueSize;
	*e = queue->data[queue->front];
//出队操作

 好了，解决了顺序结构的难点，我们可以附上全部代码了：

1、.h文件的代码：

#ifndef ARRAY_QUEUE_H
#define ARRAY_QUEUE_H

#define MaxQueueSize	5
#define Element int
typedef struct {
	Element data[MaxQueueSize];
	int front;
	int rear;
} ArrayQueue;

void initArrayQueue(ArrayQueue *queue);

int enArrayQueue(ArrayQueue *queue, Element e);
int deArrayQueue(ArrayQueue *queue, Element *e);
#endif //ARRAY_QUEUE_H

2、.c文件的代码：

#include <stdio.h>
#include "arrayQueue.h"

void initArrayQueue(ArrayQueue* queue) {
	queue->front = queue->rear = 0;
}//初始化

int enArrayQueue(ArrayQueue* queue, Element e) {
	if ((queue->rear + 1) % MaxQueueSize == queue->front) {
		fprintf(stderr, "Queue Full!\n");
		return -1;
	}

	queue->rear = (queue->rear + 1) % MaxQueueSize;
	queue->data[queue->rear] = e;

	return 0;
}//入队

int deArrayQueue(ArrayQueue* queue, Element* e) {
	if (queue->rear == queue->front) {
		fprintf(stderr, "Queue Empty!\n");
		return -1;
	}

	queue->front = (queue->front + 1) % MaxQueueSize;
	*e = queue->data[queue->front];

	return 0;
}//出队

        既然我们已经明晰了顺序队列的循环优化方法，那么我们下一步可以继续介绍链式队列的实现方式了：

        链式队列仍是遵循之前我们讲的逻辑结构的原理，但是对于链式队列，我们要重新构建队列结构，考虑到入队是插入的模式，相对自由，于是我们着重构建出队：以单链表的模式，出队的构建即为顺着单链表Next的指向方向来移动权当出队的操作。那么入队则为单向链式结构不停地增加新节点，形成同向出入队的效果。

        有了一个关于模型的思考雏形，那么我们可以试着作出逻辑图如下：

        下面，我们来通过代码实现它： 

1、首先是.h文件功能实现的构建：

#ifndef LINK_QUEUE_H
#define LINK_QUEUE_H

#define Element int

// 链表的节点
typedef struct _node {
	Element data;
	struct _node *next;
} QueNode;

// 链式队列的头节点,记录队头和队尾的位置
//const char name 是队列的名字,cnt 记录元素个数
typedef struct {
	QueNode *rear;
	QueNode *front;
	int cnt;
	const char *name;
} LinkQueue;

LinkQueue *createLinkQueue(const char *name);
void releaseLinkQueue(LinkQueue *queue);

int enLinkQueue(LinkQueue *queue, Element e);
int deLinkQueue(LinkQueue *queue, Element *e);

#endif //LINK_QUEUE_H

2、建立队列的函数：

LinkQueue* createLinkQueue(const char *name) {
	LinkQueue* queue = malloc(sizeof(LinkQueue));
	if (queue == NULL) {
		fprintf(stderr, "createLinkQueue malloc failed!\n");
		return NULL;
	}
	queue->name = name;
	queue->front =queue->rear = NULL;
	queue->cnt = 0;

	return queue;
}

3、 销毁队列函数：

void releaseLinkQueue(LinkQueue* queue) {
    //如果队列存在
	if (queue) {
    //新建辅助节点
		QueNode *node;
		while (queue->front) {
			node = queue->front;
			queue->front = node->next;
            //释放辅助节点
			free(node);
			queue->cnt--;
		}
		printf("queue have %d node!\n", queue->cnt);
    //释放链式头结点
		free(queue);
	}
}

 4、出队与入队：

// 先有新节点，新节点应该rear的next方向插入，便于front的删除
int enLinkQueue(LinkQueue* queue, Element e) {
	QueNode *node = malloc(sizeof(QueNode));
	if (node == NULL) {
		fprintf(stderr, "enLinkQueue new_node malloc failed!\n");
		return -1;
	}//如果空间申请未成功
	node->data = e;//赋值
	node->next = NULL;//入队后队尾指向NULL;
	if (queue->rear) {//队尾存在
		queue->rear->next = node;//入队操作，和上一个过程的队尾链接
		queue->rear = node;
	} else {
		queue->rear = queue->front = node;//初始的时候队尾队头指向同一点
	}
	queue->cnt++;
	return 0;
}

int deLinkQueue(LinkQueue* queue, Element* e) {
	if (queue->front == NULL) {
		fprintf(stderr, "queue empty!\n");
		return -1;
	}//空间申请未成功
	*e = queue->front->data;//备份队头待删除元素
	QueNode *tmp = queue->front;//辅助节点
	queue->front = tmp->next;//更新队头为下一个
	free(tmp);//释放空间
	queue->cnt--;
	if (queue->front == NULL) {		// 队列中已经没有元素
		queue->rear = NULL;
	}
	return 0;
}

 测试函数：

#include <stdio.h>
#include "arrayQueue.h"
#include "linkQueue.h"

void test01() {
	ArrayQueue stu1;

	initArrayQueue(&stu1);

	for (int i = 0; i < 4; ++i) {
		enArrayQueue(&stu1, i + 100);
	}
	enArrayQueue(&stu1, 500);

	printf("Que1 show: ");
	Element x1;
	while (deArrayQueue(&stu1, &x1) != -1) {
		printf("%d\t", x1);
	}
	printf("\n");
}

void test02() {
	LinkQueue *queue = createLinkQueue("stu1");
	if (queue == NULL) {
		return;
	}
	for (int i = 0; i < 5; ++i) {
		enLinkQueue(queue, i + 100);
	}
	Element x1;
	printf("%s Que %d show: ", queue->name, queue->cnt);
	while (deLinkQueue(queue, &x1) != -1) {
		printf("\t%d", x1);
	}
	printf("\n");
	releaseLinkQueue(queue);
}

int main() {
	test02();

	return 0;
}

好了，关于队列的数据结构结构实现讲解到此完结~撒花✿✿ヽ(°▽°)ノ✿，希望能对你有所帮助！