队列结构
queue.h
#ifndef ZDPC_ALGORITHM_DEV_QUEUE_H
#define ZDPC_ALGORITHM_DEV_QUEUE_H
// 队列
typedef struct queue {
int *arr; // 容器
int cap; // 容量
int size; // 元素个数
int front; // 队首,用于出队
int tail // 队尾,用于入队
} Queue;
#endif //ZDPC_ALGORITHM_DEV_QUEUE_H
新建队列
核心代码:
Queue *newQueue(int cap) {
// 申请队列内存
Queue *queue = malloc(sizeof(Queue) * cap);
// 申请容器内存
queue->arr = malloc(sizeof(int) * cap);
// 其他属性
queue->cap = cap;
queue->size = 0;
queue->front = 0;
queue->tail = 0;
// 返回
return queue;
}
queue.h
#ifndef ZDPC_ALGORITHM_DEV_QUEUE_H
#define ZDPC_ALGORITHM_DEV_QUEUE_H
// 公共头文件
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
// 队列
typedef struct queue {
int *arr; // 容器
int cap; // 容量
int size; // 元素个数
int front; // 队首,用于出队
int tail; // 队尾,用于入队
} Queue;
extern Queue *newQueue(int cap); // 创建队列
#endif //ZDPC_ALGORITHM_DEV_QUEUE_H
queue.c
#include "queue.h"
// 新建队列
Queue *newQueue(int cap) {
// 申请队列内存
Queue *queue = malloc(sizeof(Queue) * cap);
// 申请容器内存
queue->arr = malloc(sizeof(int) * cap);
// 其他属性
queue->cap = cap;
queue->size = 0;
queue->front = 0;
queue->tail = 0;
// 返回
return queue;
}
释放队列
核心代码:
void freeQueue(Queue *queue) {
if (queue == NULL) {
return;
}
free(queue->arr);
free(queue);
}
queue.h
#ifndef ZDPC_ALGORITHM_DEV_QUEUE_H
#define ZDPC_ALGORITHM_DEV_QUEUE_H
// 公共头文件
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
// 队列
typedef struct queue {
int *arr; // 容器
int cap; // 容量
int size; // 元素个数
int front; // 队首,用于出队
int tail; // 队尾,用于入队
} Queue;
extern Queue *newQueue(int cap); // 创建队列
extern void freeQueue(Queue *queue); // 释放队列
#endif //ZDPC_ALGORITHM_DEV_QUEUE_H
queue.c
#include "queue.h"
// 新建队列
Queue *newQueue(int cap) {
// 申请队列内存
Queue *queue = malloc(sizeof(Queue) * cap);
// 申请容器内存
queue->arr = malloc(sizeof(int) * cap);
// 其他属性
queue->cap = cap;
queue->size = 0;
queue->front = 0;
queue->tail = 0;
// 返回
return queue;
}
// 释放队列
void freeQueue(Queue *queue) {
if (queue == NULL) {
return;
}
free(queue->arr);
free(queue);
}
判断队列是否已满
核心代码:
int isFullQueue(Queue *queue) {
if (queue == NULL) {
return 0;
}
return queue->size >= queue->cap;
}
queue.h
#ifndef ZDPC_ALGORITHM_DEV_QUEUE_H
#define ZDPC_ALGORITHM_DEV_QUEUE_H
// 公共头文件
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
// 队列
typedef struct queue {
int *arr; // 容器
int cap; // 容量
int size; // 元素个数
int front; // 队首,用于出队
int tail; // 队尾,用于入队
} Queue;
extern Queue *newQueue(int cap); // 创建队列
extern void freeQueue(Queue *queue); // 释放队列
extern int isFullQueue(Queue *queue); // 判断队列是否已满
#endif //ZDPC_ALGORITHM_DEV_QUEUE_H
queue.c
#include "queue.h"
// 新建队列
Queue *newQueue(int cap) {
// 申请队列内存
Queue *queue = malloc(sizeof(Queue) * cap);
// 申请容器内存
queue->arr = malloc(sizeof(int) * cap);
// 其他属性
queue->cap = cap;
queue->size = 0;
queue->front = 0;
queue->tail = 0;
// 返回
return queue;
}
// 释放队列
void freeQueue(Queue *queue) {
if (queue == NULL) {
return;
}
free(queue->arr);
free(queue);
}
// 判断队列是否已满
int isFullQueue(Queue *queue) {
if (queue == NULL) {
return 0;
}
return queue->size >= queue->cap;
}
判断队列是否为空
核心代码:
int isEmptyQueue(Queue *queue) {
if (queue == NULL) {
return 0;
}
return queue->size <= 0;
}
queue.h
#ifndef ZDPC_ALGORITHM_DEV_QUEUE_H
#define ZDPC_ALGORITHM_DEV_QUEUE_H
// 公共头文件
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
// 队列
typedef struct queue {
int *arr; // 容器
int cap; // 容量
int size; // 元素个数
int front; // 队首,用于出队
int tail; // 队尾,用于入队
} Queue;
extern Queue *newQueue(int cap); // 创建队列
extern void freeQueue(Queue *queue); // 释放队列
extern int isFullQueue(Queue *queue); // 判断队列是否已满
extern int isEmptyQueue(Queue *queue); // 判断队列是否为空
#endif //ZDPC_ALGORITHM_DEV_QUEUE_H
queue.c
#include "queue.h"
// 新建队列
Queue *newQueue(int cap) {
// 申请队列内存
Queue *queue = malloc(sizeof(Queue) * cap);
// 申请容器内存
queue->arr = malloc(sizeof(int) * cap);
// 其他属性
queue->cap = cap;
queue->size = 0;
queue->front = 0;
queue->tail = 0;
// 返回
return queue;
}
// 释放队列
void freeQueue(Queue *queue) {
if (queue == NULL) {
return;
}
free(queue->arr);
free(queue);
}
// 判断队列是否已满
int isFullQueue(Queue *queue) {
if (queue == NULL) {
return 0;
}
return queue->size >= queue->cap;
}
// 判断队列是否为空
int isEmptyQueue(Queue *queue) {
if (queue == NULL) {
return 0;
}
return queue->size <= 0;
}
入队
核心代码:
void enQueue(Queue *queue, int value) {
if (isFullQueue(queue)) {
printf("queue is full\n");
return;
}
if (queue->tail >= queue->cap) {
queue->tail = 0;// 循环队列
}
queue->arr[queue->tail] = value;
queue->tail++;
queue->size++;
}
queue.h
#ifndef ZDPC_ALGORITHM_DEV_QUEUE_H
#define ZDPC_ALGORITHM_DEV_QUEUE_H
// 公共头文件
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
// 队列
typedef struct queue {
int *arr; // 容器
int cap; // 容量
int size; // 元素个数
int front; // 队首,用于出队
int tail; // 队尾,用于入队
} Queue;
extern Queue *newQueue(int cap); // 创建队列
extern void freeQueue(Queue *queue); // 释放队列
extern int isFullQueue(Queue *queue); // 判断队列是否已满
extern int isEmptyQueue(Queue *queue); // 判断队列是否为空
extern void enQueue(Queue *queue, int value); // 入队
extern void deQueue(Queue *queue); // 出队
#endif //ZDPC_ALGORITHM_DEV_QUEUE_H
queue.c
#include "queue.h"
// 新建队列
Queue *newQueue(int cap) {
// 申请队列内存
Queue *queue = malloc(sizeof(Queue) * cap);
// 申请容器内存
queue->arr = malloc(sizeof(int) * cap);
// 其他属性
queue->cap = cap;
queue->size = 0;
queue->front = 0;
queue->tail = 0;
// 返回
return queue;
}
// 释放队列
void freeQueue(Queue *queue) {
if (queue == NULL) {
return;
}
free(queue->arr);
free(queue);
}
// 判断队列是否已满
int isFullQueue(Queue *queue) {
if (queue == NULL) {
return 0;
}
return queue->size >= queue->cap;
}
// 判断队列是否为空
int isEmptyQueue(Queue *queue) {
if (queue == NULL) {
return 0;
}
return queue->size <= 0;
}
// 入队
void enQueue(Queue *queue, int value) {
if (isFullQueue(queue)) {
printf("queue is full\n");
return;
}
if (queue->tail >= queue->cap) {
queue->tail = 0;// 循环队列
}
queue->arr[queue->tail] = value;
queue->tail++;
queue->size++;
}
出队
核心代码:
int deQueue(Queue *queue) {
if (isEmptyQueue(queue)) {
printf("queue is empty\n");
return -1;
}
if (queue->front >= queue->cap) {
queue->front = 0;// 循环队列
}
// 取值
int value = queue->arr[queue->front];
queue->front++;
queue->size--;
// 返回
return value;
}
queue.h
#ifndef ZDPC_ALGORITHM_DEV_QUEUE_H
#define ZDPC_ALGORITHM_DEV_QUEUE_H
// 公共头文件
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
// 队列
typedef struct queue {
int *arr; // 容器
int cap; // 容量
int size; // 元素个数
int front; // 队首,用于出队
int tail; // 队尾,用于入队
} Queue;
extern Queue *newQueue(int cap); // 创建队列
extern void freeQueue(Queue *queue); // 释放队列
extern int isFullQueue(Queue *queue); // 判断队列是否已满
extern int isEmptyQueue(Queue *queue); // 判断队列是否为空
extern void enQueue(Queue *queue, int value); // 入队
extern int deQueue(Queue *queue); // 出队
#endif //ZDPC_ALGORITHM_DEV_QUEUE_H
queue.c
#include "queue.h"
// 新建队列
Queue *newQueue(int cap) {
// 申请队列内存
Queue *queue = malloc(sizeof(Queue) * cap);
// 申请容器内存
queue->arr = malloc(sizeof(int) * cap);
// 其他属性
queue->cap = cap;
queue->size = 0;
queue->front = 0;
queue->tail = 0;
// 返回
return queue;
}
// 释放队列
void freeQueue(Queue *queue) {
if (queue == NULL) {
return;
}
free(queue->arr);
free(queue);
}
// 判断队列是否已满
int isFullQueue(Queue *queue) {
if (queue == NULL) {
return 0;
}
return queue->size >= queue->cap;
}
// 判断队列是否为空
int isEmptyQueue(Queue *queue) {
if (queue == NULL) {
return 0;
}
return queue->size <= 0;
}
// 入队
void enQueue(Queue *queue, int value) {
if (isFullQueue(queue)) {
printf("queue is full\n");
return;
}
if (queue->tail >= queue->cap) {
queue->tail = 0;// 循环队列
}
queue->arr[queue->tail] = value;
queue->tail++;
queue->size++;
}
// 出队
int deQueue(Queue *queue) {
if (isEmptyQueue(queue)) {
printf("queue is empty\n");
return -1;
}
if (queue->front >= queue->cap) {
queue->front = 0;// 循环队列
}
// 取值
int value = queue->arr[queue->front];
queue->front++;
queue->size--;
// 返回
return value;
}
队列的基本使用
main.c
#include <stdio.h>
#include "queue.h"
int main(void) {
// 创建队列
Queue *queue = newQueue(2);
// 入队
enQueue(queue, 11);
enQueue(queue, 22);
enQueue(queue, 33); // 队列满了
// 出队
printf("%d\n", deQueue(queue));
printf("%d\n", deQueue(queue));
printf("%d\n", deQueue(queue)); // 队列空了
return 0;
}
输出:
queue is full
11
22
queue is empty
-1
队列交替入队和出队
main.c
#include <stdio.h>
#include "queue.h"
int main(void) {
// 创建队列
Queue *queue = newQueue(2);
// 入队
enQueue(queue, 11);
enQueue(queue, 22);
printf("%d\n", deQueue(queue));
enQueue(queue, 33); // 循环队列
printf("%d\n", deQueue(queue));
printf("%d\n", deQueue(queue));
// 入队
enQueue(queue, 11);
enQueue(queue, 22);
printf("%d\n", deQueue(queue));
enQueue(queue, 33); // 循环队列
printf("%d\n", deQueue(queue));
printf("%d\n", deQueue(queue));
return 0;
}
输出:
11
22
33
11
22
33
遍历队列
main.c
#include <stdio.h>
#include "queue.h"
int main(void) {
// 创建队列
Queue *queue = newQueue(2);
// 入队
enQueue(queue, 11);
enQueue(queue, 22);
printf("cap=%d size=%d\n", queue->cap, queue->size);
// 遍历队列
while (!isEmptyQueue(queue)) {
printf("%d\n", deQueue(queue));
}
printf("cap=%d size=%d\n", queue->cap, queue->size);
return 0;
}
输出:
cap=2 size=2
11
22
cap=2 size=0
重要:别忘了释放内存!!!
main.c
#include <stdio.h>
#include "queue.h"
int main(void) {
// 创建队列
Queue *queue = newQueue(2);
// 入队
enQueue(queue, 11);
enQueue(queue, 22);
printf("cap=%d size=%d\n", queue->cap, queue->size);
// 遍历队列
while (!isEmptyQueue(queue)) {
printf("%d\n", deQueue(queue));
}
printf("cap=%d size=%d\n", queue->cap, queue->size);
// 别忘了释放内存
freeQueue(queue);
return 0;
}
输出:
cap=2 size=2
11
22
cap=2 size=0