数据结构与算法（C语言）代码实现-队列的相关操作代码实现（链队列）_使用c语言编写完整代码,完成链队列的实现

队列的概念

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

我们可以把队列理解成生活中排队做核酸的场景，站在第一个位置的人叫队头，站在最后一个位置的人叫队尾。出队就是做完核酸，入队就是来新的要做核酸的人，出队只能在队头出，即每次做核酸的只能是站在最前面的人做，入队要在队尾入，即后来者只能排在后面，不能进行插队。

链队列

使用链表实现的队列。

头指针：指向链表的头节点
尾指针：指向链表的最后一个节点
队空情况：头指针和尾指针指向同一位置

实现的操作概览

• 初始化队列
  InitLinkQueue(LinkQueue &queue);
• 销毁队列
  DestroyLinkQueue(LinkQueue &queue);
• 判断队列是否为空
  LinkQueueEmpty(LinkQueue queue);
• 获取队列的长度
  LinkQueueLength(LinkQueue queue);
• 获取队头元素
  GetHead(LinkQueue queue, ElemType &e);
• 清空队列
  ClearLinkQueue(LinkQueue &queue);
• 入队操作
  EnLinkQueue(LinkQueue &queue, ElemType e);
• 出队操作
  DeLinkQueue(LinkQueue &queue, ElemType &e);

C代码实现

#include <stdio.h>
#include <cstdlib>

//###一些常量
//函数结果状态码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//队列的最大容量
#define MAXSIZE 5


//函数类型
typedef int Status;
//队列的元素类型
typedef char ElemType;


//定义链队结点结构体
typedef struct LinkQueueNode{
    //节点数据域的类型
    ElemType data;
    //next指针域
    struct LinkQueueNode *next;
}LinkQueueNode, *QueuePointer;
typedef struct{
    //头指针，指向的是头结点，下一个才是队列的首元节点
    QueuePointer front;
    //尾指针
    QueuePointer rear;
    //记录队列的长度
    int length;
}LinkQueue;

//----------------------------------------------
//初始化队列
Status InitLinkQueue(LinkQueue &queue);
//销毁队列
Status DestroyLinkQueue(LinkQueue &queue);
//判断队列是否为空
Status LinkQueueEmpty(LinkQueue queue);
//获取队列的长度
int LinkQueueLength(LinkQueue queue);
//获取队头元素
void GetHead(LinkQueue queue, ElemType &e);
//清空队列
Status ClearLinkQueue(LinkQueue &queue);
//入队操作
Status EnLinkQueue(LinkQueue &queue, ElemType e);
//出队操作
Status DeLinkQueue(LinkQueue &queue, ElemType &e);
//----------------------------------------------

int main(){
    //初始化队列
    LinkQueue *queue = new LinkQueue;
    InitLinkQueue(*queue);
    //准备元素
    ElemType e1 = 'a', e2 = 'b', e3 = 'c', e4 = 'd', e5 = 'e', e6 = 'f';
    //入队
    EnLinkQueue(*queue, e1);
    EnLinkQueue(*queue, e2);
    EnLinkQueue(*queue, e3);
    EnLinkQueue(*queue, e4);
    EnLinkQueue(*queue, e5);
    EnLinkQueue(*queue, e6);
    //判断队列是否为空
    Status isEmpty = LinkQueueEmpty(*queue);
    printf("队列是否为空：%d\n", isEmpty);//0
    //出队
    DeLinkQueue(*queue, e1);
    printf("出队元素：%c\n", e1);//a
    //出队
    DeLinkQueue(*queue, e1);
    printf("出队元素：%c\n", e1);//b
    //队列的长度
    int length = LinkQueueLength(*queue);
    printf("队列的长度：%d\n", length);//4
    //获取队头元素
    GetHead(*queue, e1);
    printf("队列头元素：%c\n", e1);//c
    //清空队列
    ClearLinkQueue(*queue);
    //出队列
    DeLinkQueue(*queue, e1);//队列为空，出队失败！
    //销毁队列
    DestroyLinkQueue(*queue);
}

/**
 * 初始化队列，构造一个空队列
 * @param queue 队列
 * @return
 */
Status InitLinkQueue(LinkQueue &queue){
    //创建链表头结点
    LinkQueueNode *node = new LinkQueueNode;
    node->next = NULL;
    //头指针和尾指针都指向头结点，形成空队
    queue.front = queue.rear = node;
    //初始化队列长度为0
    queue.length = 0;
    return OK;
}

/**
 * 判断队列是否为空，是空队列返回TRUE
 * @param queue 队列
 * @return
 */
Status LinkQueueEmpty(LinkQueue queue){
    //根据队列长度判断
    return queue.length? FALSE: TRUE;
}

/**
 * 获取队列的长度
 * @param queue 队列
 * @return
 */
int LinkQueueLength(LinkQueue queue){
    //返回length属性
    return queue.length;
}

/**
 * 清空队列
 * @param queue
 */
Status ClearLinkQueue(LinkQueue &queue){
    //将队尾指向头结点，重置队列length属性
    queue.rear = queue.front;
    queue.length = 0;
    return OK;
}

/**
 * 销毁队列
 * @param queue
 */
Status DestroyLinkQueue(LinkQueue &queue){
    //定义一个队列指针，指向队头
    QueuePointer queuePointer = queue.front->next;
    for(QueuePointer p = queuePointer; p; p=queuePointer){
        //指针后移
        queuePointer = queuePointer->next;
        //销毁p指向的节点
        delete p;
    }
    //重置队列length属性
    queue.length = 0;
    return OK;
}

/**
 * 获取队头元素
 * @param queue
 * @param e ：用来存放队头的元素
 */
void GetHead(LinkQueue queue, ElemType &e){
    //队头指针的next才是头元素所在的节点
    e = queue.front->next->data;
}

/**
 * 入队操作
 * @param queue 队列
 * @param e 要入队的元素
 */
Status EnLinkQueue(LinkQueue &queue, ElemType e){
    //创建新节点
    LinkQueueNode *node =  new LinkQueueNode;
    node->data = e;
    node->next = NULL;
    //插入节点
    queue.rear->next = node;
    //尾指针后移
    queue.rear = node;
    //更新长度
    queue.length++;
    return OK;
}

/**
 * 出队操作
 * @param queue 队列
 * @param e 用来接收出队的元素
 */
Status DeLinkQueue(LinkQueue &queue, ElemType &e){
    //判断是否是空队列
    if(queue.front == queue.rear){
        printf("队列为空，出队失败！\n");
        return ERROR;
    }
    //记录出队的元素节点
    LinkQueueNode *node = queue.front->next;
    //将出队的元素给e
    e = node->data;
    //移动头指针的next指针域
    queue.front->next = node->next;
    //销毁出队的节点
    delete node;
    //更新长度
    queue.length--;
    return OK;
}


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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211