队列的实现（完整代码+详细注释版）【数据结构】_数据结构顺序队列完整代码

注释详细完整且健壮的两种方式实现队列的代码：

顺序队列

//
//  main.c
//  SequenceQueue
//
//  Created by Eason on 2020/8/2.
//  Copyright © 2020 Eason. All rights reserved.
//

#include <stdio.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 21  //采用循环队列的方式，充分利用空间，但是会有一个单元的浪费，实际容量为最大容量-1，因为要区分空与满
typedef int ElemType;
typedef int Status;
typedef struct{   //顺序队列的存储结构
    ElemType data[MAXSIZE];   //队列元素的数据
    int front, rear;   //头指针与尾指针
}SqQueue;

//初始化顺序队列
Status initQueue(SqQueue *Q){
    Q->front=0;   //初始时头指针与为指针均指向0
    Q->rear=0;
    return OK;
}

//判断顺序队列是否为空
Status isEmpty(SqQueue Q){
    if(Q.front==Q.rear){   //当头指针与尾指针指向相同的单元时表示队列为空
        return TRUE;
    }else{
        return FALSE;
    }
}

//判断顺序队列是否已满
Status isFull(SqQueue Q){
    if((Q.rear+1)%MAXSIZE==Q.front){   //循环队列头指针可能在前也可能在后，头指针在前尾指针在最后差1时为满，头指针在后尾指针与头指针差1时为满，则用差值取余的方式可判断当前是否已满
        return TRUE;
    }else{
        return FALSE;
    }
}
//获取顺序队列的长度
Status getLength(SqQueue Q){
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;   //根据循环队列的特点，即长度为差值加最大容量与最大容量的取模运算
}

//清空顺序队列
Status clearQueue(SqQueue *Q){
    Q->front = Q->rear;   //根据队列为空的判断条件，即将头指针指向尾指针时两指针指向同一单元时队列为空。不能颠倒，因为尾指针指向的是空单元
    return OK;
}

//入队
Status enter(SqQueue *Q, ElemType *e){
    if(isFull(*Q)){   //判断队列是否还可以再入队元素
        printf("队列已满，无法入队\n");
        return ERROR;
    }
    Q->data[Q->rear]=e;   //将当前尾指针指向的空白单元入值
    Q->rear = (Q->rear+1)%MAXSIZE;   //将尾指针向后走一格，因为有可能是从队尾到队头，所以使用取模的方式判断尾指针接下来的位置
    return OK;
}

//出队
Status leave(SqQueue *Q, ElemType *e){
    if(isEmpty(*Q)){   //判断队列是否有元素可以出队
        printf("队列为空，不可出队\n");
        return ERROR;
    }
    *e = Q->data[Q->front];   //将当前队首元素出队给e供返回与查看
    Q->front = (Q->front+1)%MAXSIZE;   //将头指针向后走一格，因为有可能是从队尾到队头，所以使用取模的方式判断头指针接下来的位置
    return OK;
}

//获取队首元素
Status getHead(SqQueue Q, ElemType *e){
    if(isEmpty(Q)){   //判断队列是否有元素可供查看
        printf("队列为空，无队首元素\n");
        return ERROR;
    }
    *e = Q.data[Q.front];   //将当前队头元素返回给e供返回并查看
    return OK;
}

//打印队列
Status printQueue(SqQueue Q){
    if(isEmpty(Q)){   //判断队列当前是否有元素可供打印
        printf("队列为空，无队元素可供打印\n");
        return ERROR;
    }
    int i=0;   //当前元素数量计数器
    while(!isEmpty(Q)){
        i++;   //不为空说明当前有元素可供打印，则计数器+1
        printf("从队首至队尾的第%d个元素为：%d\n", i, Q.data[Q.front]);   //打印当前队首元素
        Q.front = (Q.front+1)%MAXSIZE;   //将头指针向后走一格，因为有可能是从队尾到队头，所以使用取模的方式判断头指针接下来的位置
    }
    return OK;
}

//测试
int main(int argc, const char * argv[]) {
    SqQueue Q;
    initQueue(&Q);
    printf("初始化队列Q后队列的长度为：%d,是否为空？（是1否0）：%d\n", getLength(Q), isEmpty(Q));
    printf("将1-18顺序的入队后队列变为：\n");
    for(int i=1;i<=18;i++){
        enter(&Q, i);
    }
    printQueue(Q);
    printf("此时队列的长度为：%d\n", getLength(Q));
    printf("队列的最大长度为20，检验再依次入队3个元素后得：\n");
    enter(&Q, 19);
    enter(&Q, 20);
    enter(&Q, 21);
    printQueue(Q);
    printf("-----验证循环队列-----\n");
    int e;
    leave(&Q, &e);
    printf("出队列：%d\n", e);
    enter(&Q, 21);
    printf("入队列：21\n");
    printf("此时的队列内容为：\n");
    printQueue(Q);
    printf("此时队列的长度为：%d，是否已满？（1是0否）：%d\n", getLength(Q), isFull(Q));
    printf("清空队列后队列为：\n");
    clearQueue(&Q);
    printQueue(Q);
    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

链队

//
//  main.c
//  LinkedQueue
//
//  Created by Eason on 2020/8/2.
//  Copyright © 2020 Eason. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status;   //注意：头指针始终指向头结点（不存放数据）头结点的下一结点才是链队的队头
typedef struct QueueNode{   //链队结点的存储结构
    ElemType data;   //数据域
    struct QueueNode *next;   //指针域
}QueueNode, *QueueNodePtr;

typedef struct{   //链队头结点的存储结构
    QueueNodePtr front, rear;   //头指针与尾指针
}LinkQueue;

//初始化链队
Status initQueue(LinkQueue *Q){
    Q->front = (QueueNodePtr)malloc(sizeof(QueueNode));   //初始化为首位指针分配内存
    Q->rear = (QueueNodePtr)malloc(sizeof(QueueNode));
    if(!Q->front || !Q->rear){   //若不存在则说明内存分配失败无法初始化
        printf("初始化内存分配失败");
        return ERROR;
    }
    Q->front = Q->rear;   //空队的条件 队头指针=队尾指针 均指向头结点
    Q->front->next = NULL;   //头结点的下一结点，即首个结点为空
    return OK;   //这里要注意，初始的时候首位指针均指向头结点，是不存放数据的，链队此时为空
}

//判断链队是否为空
Status isEmpty(LinkQueue Q){
    if(Q.front==Q.rear){   //链队为空的条件为头指针=尾指针，即都指向头结点
        return TRUE;
    }else{
        return FALSE;
    }
}

//获取链队的长度
int getLength(LinkQueue Q){
    QueueNodePtr p;   //定义临时结点指针
    p = Q.front->next;   //将临时结点置为链队的首个结点
    int i=0;   //链队长度计数器
    while(p){   //如果此时链队结点存在的话就继续向下进行
        i++;   //计数器+1
        p = p->next;   //链队指针继续向下移动
    }
    return i;   //返回链队计数器i即长度
}

//入队
Status enter(LinkQueue *Q, ElemType *e){
    QueueNodePtr p = (QueueNodePtr)malloc(sizeof(QueueNode));   //为新入队的结点分配内存空间
    if(!p){   //验证是否为新结点内存分配成功
        printf("新结点内存分配失败，无法入队");
        return ERROR;
    }
    p->data = e;   //将新结点的数据域置为指定值
    Q->rear->next = p;   //还未入队的此时队尾的下一结点指向p
    Q->rear = p;   //这时队尾指针指向p，即p成为了新的队尾结点
    p->next = NULL;   //队尾结点的指针域为空
    return OK;
}

//出队
Status leave(LinkQueue *Q, ElemType *e){
    if(isEmpty(*Q)){   //判断链队是否为空，若为空则无链队元素可供出队
        printf("链队为空，无队元素可出列\n");
        return ERROR;
    }
    QueueNodePtr p;   //定义临时结点指针p
    p = Q->front->next;   //将p置为链队的首个结点
    *e = p->data;   //将首个结点p的数据域赋给e以供返回与查看
    Q->front->next = p->next;   //将老首个结点的下一结点设置为首个结点
    if(Q->rear == p){   //若此时p也为尾结点，说明队列为空了
        Q->rear = Q->front;   //如果队列为空则将队尾指针重新指向头结点表示链队为空了
    }
    free(p);   //将出队的p结点释放掉
    return OK;
}

//获取链队的队头元素
Status getHead(LinkQueue Q, ElemType *e){
    if(isEmpty(Q)){   //判断链队是否为空，若为空则无链队的队头元素可供查看
        printf("链队为空，无队头元素\n");
        return ERROR;
    }
    *e = Q.front->next->data;   //若链队不为空，则将链队的首个结点的数据域赋给e供返回与查看
    return OK;   //仅查看队头元素，指针不发生移动
}

//清空链队
Status clearQueue(LinkQueue *Q){
    QueueNodePtr p, q;   //定义临时结点pq
    p = Q->front->next;   //将p结点置为链队的首个结点
    Q->rear = Q->front;   //将队尾指针指向头结点与头指针相同，这样则表示此时链队为空
    Q->front->next = NULL;   //将头结点的指针域置空，即无首个结点
    while(p){   //若p存在则继续执行循环体
        q = p;   //将p赋给q
        p = p->next;   //p继续向下进行
        free(q);   //释放q，一直循环直到p结点不再存在，即此时链队的结点都被释放掉了
    }
    return OK;
}

//打印链队
Status printQueue(LinkQueue Q){
    if(isEmpty(Q)){   //判断链队是否为空，若为空则无链队元素可供打印
        printf("当前链队无元素可供打印\n");
        return ERROR;
    }
    QueueNodePtr p;   //定义临时结点p
    p = Q.front->next;   //将p赋为链队的首个结点
    int i=0;   //此时链队元素位置计数器
    while(p){   //如果此时p存在的话则继续执行循环体
        i++;   //p存在则计数器+1
        printf("从队首至队尾的第%d个元素为：%d\n", i, p->data);   //打印当前p结点的数据域
        p = p->next;   //p指针继续向下移动，直到p为空，即链队的所有结点都打印完毕
    }
    return OK;
}

//测试
int main(int argc, const char * argv[]) {
    LinkQueue Q;
    initQueue(&Q);
    printf("初始化队列Q后队列的长度为：%d\n此时的链队是否为空？（1是0否）：%d\n", getLength(Q), isEmpty(Q));
    printf("将1-6按顺序入队后可得链队：\n");
    for(int i=1;i<=6;i++){
        enter(&Q, i);
    }
    printQueue(Q);
    printf("此时队列的长度为：%d\n", getLength(Q));
    int e;
    getHead(Q, &e);
    printf("此时队列的队头为：%d\n", e);
    printf("队列出队两个元素：\n");
    leave(&Q, &e);
    printf("出队：%d\n", e);
    leave(&Q, &e);
    printf("出队：%d\n", e);
    printf("现在的链队为：\n");
    printQueue(Q);
    printf("现在的链队长度为：%d\n", getLength(Q));
    getHead(Q, &e);
    printf("现在链队的队头为：%d\n", e);
    printf("清空链队后得链队为：\n");
    clearQueue(&Q);
    printQueue(Q);
    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
148
149
150
151
152
153
154
155
156
157
158
159
160