数据结构学习系列之循环队列

• 队列的基本概念：
• 队列（Queue）：一种先进先出（FIFO）的线性表；
• 队尾（rear）：允许插入的一端；
• 队头（front）：允许删除的一端；
• 入队列：队列的插入元素的操作；
• 出队列：队列的删除元素的操作；
• 循环队列：
• 即：队列的头尾相接的顺序存储结构；
• 入队列：rear = (rear + 1) % Queue_size；
• 出队列：front = (front + 1) % Queue_size；
• 队空：rear == front；
• 队满：(rear + 1) % Queue_size == front；
• 队列的长度：(rear - front + Queue_size) % Queue_size；
• 入队列：

int push_loop_queue(queue_t *loop_queue,int data)
{

    if(NULL == loop_queue)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    if(queue_is_full(loop_queue))
    {
        printf("此时队列已满，入队失败\n");
        return -1;
    }

    loop_queue->a[loop_queue->rear] = data;
    loop_queue->rear = (loop_queue->rear + 1) % N;
    return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 出队列：

int pop_loop_queue(queue_t *loop_queue,int *data)
{
    if(NULL == loop_queue || NULL == data)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    if(queue_is_empty(loop_queue))
    {
        printf("此时队列为空，出队失败\n");
        return -1;
    }

    *data = loop_queue->a[loop_queue->front];
    loop_queue->front = (loop_queue->front + 1) % N;
    return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 示例代码：
• loop_queue.h:

#ifndef __LOOP_QUEUE_H__
#define __LOOP_QUEUE_H__

#include 
#include 
#include 

#define N 6

typedef struct Loop_Queue{

    int a[N];
    int front;
    int rear;
   
}queue_t;

int create_loop_queue(queue_t **p);
int queue_is_full(queue_t *loop_queue);
int push_loop_queue(queue_t *loop_queue,int data);
int queue_is_empty(queue_t *loop_queue);
int pop_loop_queue(queue_t *loop_queue,int *data);
int clean_loop_queue(queue_t *loop_queue);
int destroy_loop_queue(queue_t **loop_queue);
int print_loop_queue(queue_t *loop_queue);


#endif
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

• loop_queue.c:

#include "loop_queue.h"

//创建队列
int create_loop_queue(queue_t **p)
{

    if(NULL == p)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    *p = (queue_t *)malloc(sizeof(queue_t));

    if(NULL == *p)
    {
        printf("内存分配失败\n");
        return -1;
    }

    memset(*p,0,sizeof(queue_t));

    return 0;

    
}

//判断队列是否为满
int queue_is_full(queue_t *loop_queue)
{
    if(NULL == loop_queue)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    return (loop_queue->rear + 1) % N == loop_queue->front ? 1 : 0;

}

//入队列
int push_loop_queue(queue_t *loop_queue,int data)
{

    if(NULL == loop_queue)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    if(queue_is_full(loop_queue))
    {
        printf("此时队列已满，入队失败\n");
        return -1;
    }

    loop_queue->a[loop_queue->rear] = data;
    loop_queue->rear = (loop_queue->rear + 1) % N;
    return 0;

}

//判断队列是否为空
int queue_is_empty(queue_t *loop_queue)
{
    if(NULL == loop_queue)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    return loop_queue->rear == loop_queue->front ? 1 : 0;

}

//出队列
int pop_loop_queue(queue_t *loop_queue,int *data)
{
    if(NULL == loop_queue || NULL == data)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    if(queue_is_empty(loop_queue))
    {
        printf("此时队列为空，出队失败\n");
        return -1;
    }

    *data = loop_queue->a[loop_queue->front];
    loop_queue->front = (loop_queue->front + 1) % N;
    return 0;

}

//清空队列
int clean_loop_queue(queue_t *loop_queue)
{
    if(NULL == loop_queue)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    loop_queue->front = 0;
    loop_queue->rear = 0;
    return 0;

}

//销毁队列
int destroy_loop_queue(queue_t **loop_queue)
{
    if(NULL == loop_queue || NULL == *loop_queue)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    free(*loop_queue);
    *loop_queue = NULL;
    return 0;

}

//遍历队列的元素
int print_loop_queue(queue_t *loop_queue)
{
    if(NULL == loop_queue)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    int i = loop_queue->front;
    while(i != loop_queue->rear)
    {

        printf("%d ",loop_queue->a[i]);

        i = (i + 1) % N;
    }
    puts("");
    return 0;

}
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

• main.c:

#include "loop_queue.h"

int main(int argc, char const *argv[])
{
    queue_t *loop_queue = NULL;
    create_loop_queue(&loop_queue);
    printf("loop_queue = %p\n",loop_queue);


    //入队
    push_loop_queue(loop_queue,11);
    push_loop_queue(loop_queue,33);
    push_loop_queue(loop_queue,11);
    push_loop_queue(loop_queue,66);
    push_loop_queue(loop_queue,11);
    push_loop_queue(loop_queue,99);
    


    print_loop_queue(loop_queue);

    //出队
    int data;
    pop_loop_queue(loop_queue,&data);
    printf("%d ", data);
    pop_loop_queue(loop_queue,&data);
    printf("%d ", data);
    pop_loop_queue(loop_queue,&data);
    printf("%d ", data);
    pop_loop_queue(loop_queue,&data);
    printf("%d ", data);
    pop_loop_queue(loop_queue,&data);
    printf("%d ", data);
    puts("");
    pop_loop_queue(loop_queue,&data);
   


    clean_loop_queue(loop_queue);
    print_loop_queue(loop_queue);

    destroy_loop_queue(&loop_queue);
    printf("loop_queue = %p\n",loop_queue);

    return 0;
}

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

• 运行结果：

loop_queue = 0x562e9a67b260
此时队列已满，入队失败
11 33 11 66 11 
11 33 11 66 11 
此时队列为空，出队失败

loop_queue = (nil)
1
2
3
4
5
6
7

• 注意：
• 本示例代码的存储空间预设可以存储6个元素，但是实际上只能存储5个元素；
• 虽然浪费了1个存储空间，却给判断队列是否为满提供了便利；
• 本示例代码，仅供参考；