这是使用数组实现的循环队列,同样也可以用链表实现,但原理都是一样的,就不重新写一份了,简单实现了数据的取出插入

结构体定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//
// Created by Tianyi on 2021/11/3.
//

#ifndef DATA_STRUCT_CIRCULAR_QUEUE_STRUCT_H
#define DATA_STRUCT_CIRCULAR_QUEUE_STRUCT_H

#endif //DATA_STRUCT_CIRCULAR_QUEUE_STRUCT_H

struct CircularQueue {
int * data;
int capacity;
int count;
int head;
int tail;
};

循环队列相关操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//
// Created by 陈天翼 on 2021/11/3.
//
#include <stdlib.h>
#include <string.h>

#ifndef DATA_STRUCT_CIRCULAR_QUEUE_UTILS_H
#define DATA_STRUCT_CIRCULAR_QUEUE_UTILS_H

#endif //DATA_STRUCT_CIRCULAR_QUEUE_UTILS_H

typedef struct CircularQueue CircularQueue;

/**
* 创建循环队列
* @param capacity
* @return
*/
struct CircularQueue *newQueue(int capacity) {

int *data = calloc(capacity + 1, sizeof(int));

struct CircularQueue *queue = malloc(sizeof(CircularQueue));

if (data == NULL || queue == NULL) {
printf("Apple memory for queue failure!!!");
return NULL;
}

// 清空申请的内存
memset(queue, 0, sizeof(CircularQueue));

queue->data = data;
queue->capacity = capacity + 1;
queue->count = 0;
queue->head = 0;
queue->tail = queue->head + 1;

return queue;
}

/**
* 队列添加元素
* @param queue
* @param value
*/
void push(struct CircularQueue *queue, int value) {
if ((queue->tail + 1) % queue->capacity == queue->head) {
printf("The queue is full!!!\n");
return;
}

// 第一次添加元素比较特殊
if (queue->count == 0) {
queue->data[queue->head] = value;
} else {
queue->data[queue->tail] = value;
queue->tail = (queue->tail + 1) % queue->capacity;
}
queue->count++;
}

/**
* 取出头部元素,并不删除
* @param queue
* @return
*/
int peek(struct CircularQueue *queue) {
return queue->data[queue->head];
}

int pool(struct CircularQueue *queue) {
if ((queue->head + 1) % queue->capacity == queue->tail) {
if (queue->count == 1) {
queue->count = 0;
} else {
printf("The queue is empty!!!\n");
return -65535;
}
}

int pool = queue->data[queue->head];
queue->head = (queue->head + 1) % queue->capacity;
queue->count--;

return pool;
}

/**
* 打印队列中的数据
* @param queue
*/
void show(struct CircularQueue *queue) {
int index = 1;
for (int i = queue->head; i != queue->tail; i = (i + 1) % queue->capacity) {
printf("index %d -- value %d\n", index, queue->data[i]);
index++;
}
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>

#include "lib/struct.h"
#include "lib/utils.h"

int main() {
struct CircularQueue * queue = newQueue(5);
for (int i = 0; i < 5; ++i) {
push(queue, i);
}
show(queue);
printf("=========================\n");
printf("The head value is %d\n", peek(queue));
printf("=========================\n");
pool(queue);
show(queue);
printf("=========================\n");
printf("The head value is %d\n", peek(queue));
printf("=========================\n");
pool(queue);
show(queue);
printf("=========================\n");
for (int i = 0; i < 2; ++i) {
push(queue, i + 5);
}
show(queue);

return 0;
}