数据结构顺序队列及链式队列

————————————本栏目旨在讨论计算机知识，欢迎交流————————————— 上一章，我们讨论了顺序栈和链式栈，这一章，我们将讲解线性结构的最后一个部分——顺序队列和链式队列。相比于栈结构的同端进出，就像原肠生物，而队列则是尾部入队和头部出队，就像后口生物一样。如图：那么，如何来实现入队和出队呢？答曰：请看VCR：但是，使用这种直观地朴素方法我们有个致命的问题——假溢出问题。在顺序栈的实现中我们的队头队尾类似于双指针滑动窗口算法，但是每次划过了之后空间不会清除，导致看起来一共占了（rear-head）个空间，但是其实远远不止这么多。前面的都没删除，很容易产生假溢出的效果并且及其占用空间。于是，循环赋值的方法应运而生。它的基本原理是：通过取余操作来覆盖删除的数值，直到队头与队尾相撞结束。那么，现在我们有两种思路：1、通过设定一个bool类型变量flag，每次通过判断来操作。2、虚空一个空间，每次入队的时候探针向前虚指，碰到了头才操作。比起第一种方法，第二种用了空间换时间的方法，效率更高。如下：

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

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

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

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

好了，解决了顺序结构的难点，我们可以附上全部代码了： 1、.h文件的代码：

1
#ifndef ARRAY_QUEUE_H
2
#define ARRAY_QUEUE_H
3

4
#define MaxQueueSize 5
5
#define Element int
6
typedef struct {
7
Element data[MaxQueueSize];
8
int front;
9
int rear;
10
} ArrayQueue;
11

12
void initArrayQueue(ArrayQueue *queue);
13

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

2、.c文件的代码：

1
#include
2
#include "arrayQueue.h"
3

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

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

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

17
return 0;
18
}//入队
19

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

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

29
return 0;
30
}//出队

既然我们已经明晰了顺序队列的循环优化方法，那么我们下一步可以继续介绍链式队列的实现方式了：链式队列仍是遵循之前我们讲的逻辑结构的原理，但是对于链式队列，我们要重新构建队列结构，考虑到入队是插入的模式，相对自由，于是我们着重构建出队：以单链表的模式，出队的构建即为顺着单链表Next的指向方向来移动权当出队的操作。那么入队则为单向链式结构不停地增加新节点，形成同向出入队的效果。有了一个关于模型的思考雏形，那么我们可以试着作出逻辑图如下：下面，我们来通过代码实现它： 1、首先是.h文件功能实现的构建：

1
#ifndef LINK_QUEUE_H
2
#define LINK_QUEUE_H
3

4
#define Element int
5

6
// 链表的节点
7
typedef struct _node {
8
Element data;
9
struct _node *next;
10
} QueNode;
11

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

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

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

27
#endif //LINK_QUEUE_H

2、建立队列的函数：

1
LinkQueue* createLinkQueue(const char *name) {
2
LinkQueue* queue = malloc(sizeof(LinkQueue));
3
if (queue == NULL) {
4
fprintf(stderr, "createLinkQueue malloc failed!\n");
5
return NULL;
6
}
7
queue->name = name;
8
queue->front =queue->rear = NULL;
9
queue->cnt = 0;
10

11
return queue;
12
}

3、销毁队列函数：

1
void releaseLinkQueue(LinkQueue* queue) {
2
//如果队列存在
3
if (queue) {
4
//新建辅助节点
5
QueNode *node;
6
while (queue->front) {
7
node = queue->front;
8
queue->front = node->next;
9
//释放辅助节点
10
free(node);
11
queue->cnt--;
12
}
13
printf("queue have %d node!\n", queue->cnt);
14
//释放链式头结点
15
free(queue);
16
}
17
}

4、出队与入队：

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

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

测试函数：

1
#include
2
#include "arrayQueue.h"
3
#include "linkQueue.h"
4

5
void test01() {
6
ArrayQueue stu1;
7

8
initArrayQueue(&stu1);
9

10
for (int i = 0; i name, queue->cnt);
11
while (deLinkQueue(queue, &x1) != -1) {
12
printf("\t%d", x1);
13
}
14
printf("\n");
15
releaseLinkQueue(queue);
16
}
17

18
int main() {
19
test02();
20

21
return 0;
22
}

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

音乐

音乐

支持与分享

音乐

文章目录