「队列-顺序结构（循环队列）」C语言实现

文章目录
  1. 循环队列示意图
  2. 结构定义
  3. 重点
  4. 源码

循环队列示意图

结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
/*-------------------- 循环队列结构定义 ----------------------*/

#define MAXSIZE 10  // 队列长度

typedef int ElemType;

typedef struct queue {
    ElemType * pBase;  // 数组（用指针表示）
    int front;
    int rear;
} Queue, *pQueue;

/*-------------------- 循环队列结构定义 ----------------------*/

重点

  1. 为什么要使用循环队列？

    如果用链表实现队列的话，很简单，只要确定一个头指针和一个尾指针即可。

    但这里我们选择用数组来实现，数组占用一块连续的内存地址，那么就要考虑内存的问题了，入队：尾指针递增，出队：头指针递增。

    可以看出不管是增加元素还是删除元素，指针所指的内存地址都在递增，那么前面的地址就浪费了，内存空间一直在变小。

    为了解决这个问题，循环队列应运而生。

  2. 实现循环队列的关键点：

    • 头指针 front: 指向第一个有效节点，尾指针 rear: 指向最后一个有效节点的后面一个节点
    • 队列长度：len, 有效节点数：len-1
    • 入队：rear = (rear + 1) % len;
    • 出队：front = (fromt + 1) % len;
    • 队空：front == rear
    • 队满：(rear + 1) % len == front

  3. 队列的应用：所有与时间有关的操作都会用到队列。

源码

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
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


/*-------------------- 循环队列结构定义 ----------------------*/

#define MAXSIZE 10  // 队列长度

typedef int ElemType;

typedef struct queue {
    ElemType * pBase;  // 数组（用指针表示）
    int front;
    int rear;
} Queue, *pQueue;

// 示意图：https://img.arctee.cn/one/202208271516620.png

/*-------------------- 循环队列结构定义 ----------------------*/


// 函数前置声明
void InitQueue(pQueue pQ);
bool IsFull(pQueue pQ);
bool EnQueue(pQueue pQ, ElemType e);
bool IsEmpty(pQueue pQ);
bool TraverQe(pQueue pQ);
bool DeQueue(pQueue pQ, ElemType * pE);


// 主函数
int main(void)
{
    Queue Q;

    InitQueue(&Q);

    printf("入队：");
    EnQueue(&Q, 1);
    EnQueue(&Q, 2);
    EnQueue(&Q, 3);
    EnQueue(&Q, 4);
    EnQueue(&Q, 5);
    EnQueue(&Q, 6);
    // EnQueue(&Q, 7);

    TraverQe(&Q);

    ElemType e;
    DeQueue(&Q, &e);
    printf("出队：%d\n", e);
    DeQueue(&Q, &e);
    printf("出队：%d\n", e);
    DeQueue(&Q, &e);
    printf("出队：%d\n", e);

    TraverQe(&Q);

    return 0;

}

// 初始化
void InitQueue(pQueue pQ)
{
    // 创建动态数组
    pQ->pBase = (ElemType*)malloc( MAXSIZE * sizeof(ElemType) );
    pQ->front = 0;
    pQ->rear = 0;
}

// 是否已满
bool IsFull(pQueue pQ)
{
    return ( (pQ->rear+1) % MAXSIZE ==  pQ->front );
}

// 入队
bool EnQueue(pQueue pQ, ElemType e)
{
    if ( IsFull(pQ) ) {
        printf("队列已满！无法入队！");
        return false;
    }

    pQ->pBase[pQ->rear] = e;
    pQ->rear = (pQ->rear + 1) % MAXSIZE;

    return true;
}

// 是否空
bool IsEmpty(pQueue pQ)
{
    return ( pQ->front == pQ->rear );
}

// 遍历队列
bool TraverQe(pQueue pQ)
{
    if ( IsEmpty(pQ) ) {
        printf("队列为空！");
        return false;
    }

    int i = pQ->front;
    while ( i != pQ->rear ) {
        printf("%d ", pQ->pBase[i]);
        i = (i + 1) % MAXSIZE;
    }
    printf("\n");

    return true;
}

// 出队
bool DeQueue(pQueue pQ, ElemType * pE)
{
    if ( IsEmpty(pQ) ) {
        printf("队列为空！");
        return false;
    }

    *pE = pQ->pBase[pQ->front];
    pQ->front = (pQ->front + 1) % MAXSIZE;

    return true;
}

// 清空

// 销毁