简介
- 队列也是一种数据结构，队列也可以用来存放数字
- 每次只能向队列里将入一个数字，每次只能从队列里获得一个数字
- 在队列中，允许插入的一段称为入队口，允许删除的一段称为出队口
- 它的原则是先进先出(FIFO: first in first out)，先进入队列的数据先出去，后进入的后出去。
- 队列的插入操作称为入队
- 队列的删除操作称为出队
以下是队列中进行入队和出队的演示操作，数据1先进，也是数据1先出
代码实现
- 初始化队列
typedef struct queue{int* elements; // 存储区int cap; // 队列的容量int rear; // 入队口int front; // 出队口int size; // 队列当前大小
}queue_t;
- 初始化队列
void queue_init(queue_t* pqueue, int cap){// 分配存储区空间pqueue->elements = malloc(sizeof(int) * cap);if(pqueue->elements == NULL){printf("内存分配失败\n");return;}// 赋值容量pqueue->cap = cap;// 此时因为没有收数据，出队口和入队口都是0，队列当前大小也是0pqueue->rear = 0;pqueue->front = 0;pqueue->size = 0;
}
- 销毁队列
void queue_deinit(queue_t* pqueue){free(pqueue->elements);pqueue->elements = NULL;pqueue->cap = 0;pqueue->rear = 0;pqueue->front = 0;pqueue->size = 0;
}
- 判断队列是否已满
int queue_full(queue_t* pqueue){// 当size==cap的时候，说明已满，反之则没满return pqueue->size == pqueue->cap;
}
- 判断队列是否为空
int queue_empty(queue_t* pqueue){// 当size==0的时候，说明为空，反之则不为空return pqueue->size == 0;
}
以下是一组入队出队的操作
- 入队
void queue_push(queue_t* pqueue, int data){// 参考上面的视频，当此时还存在入队操作时，说明队列还没满，// 但是此时rear已经超过索引值了(也就是与cap值相等)，需要将rear重置为0;if(pqueue->rear == pqueue=>cap)pqueue->rear = 0;pqueue->elements[pqueue->rear++] = data;pqueue->size++;
}
- 出队
int queue_pop(queue_t* pqueue){// 与入队函数类似，当此时还存在出队操作时，说明队列不为空，// 但是此时front已经超过索引值了（也就是与cap值相等），需要将front重置为0if(pqueue->front == pqueue->cap)pqueue->front = 0;pqueue->size--;return pqueue->elements[pqueue->front++];
}
实例代码
创建三个文件: queue.c、queue.h、main.c，实现上面动图中的操作
queue.c定义队列具体的函数
#include "queue.h"// 初始化队列
void queue_init(queue_t* pqueue, int cap){pqueue->elements = malloc(sizeof(int) * cap);if(pqueue->elements == NULL){ printf("分配队列存储区失败!\n");return;}pqueue->cap = cap;pqueue->rear = 0;pqueue->front = 0;pqueue->size = 0;
}// 销毁队列
void queue_deinit(queue_t* pqueue){free(pqueue->elements);pqueue->elements = NULL;pqueue->cap = 0;pqueue->rear = 0;pqueue->front = 0;pqueue->size = 0;
}// 入队
void queue_push(queue_t* pqueue, int data){if(pqueue->rear == pqueue->cap)pqueue->rear = 0;pqueue->elements[pqueue->rear++] = data;pqueue->size++;
}// 出队
int queue_pop(queue_t* pqueue){if(pqueue->front == pqueue->cap)pqueue->front = 0;pqueue->size--;return pqueue->elements[pqueue->front++];
}//判断队列是否已满
int queue_full(queue_t* pqueue){return pqueue->size == pqueue->cap;
}// 判断队列是否为空
int queue_empty(queue_t* pqueue){return pqueue->size == 0;
}
queue.h声明队列的相关函数和定义队列
#ifndef __QUEUE_H
#define __QUEUE_H#include <stdio.h>
#include <stdlib.h>// 定义队列
typedef struct queue{int* elements;int cap;int rear;int front;int size;}queue_t;extern void queue_init(queue_t* pqueue, int cap);
extern void queue_deinit(queue_t* pqueue);
extern void queue_push(queue_t* pqueue, int data);
extern int queue_pop(queue_t* pqueue);
extern int queue_full(queue_t* pqueue);
extern int queue_empty(queue_t* pqueue);#endif
main.c主函数使用队列
#include "queue.h"int main(void){// 1. 创建一个队列queue_t queue;// 2. 初始化队列queue_init(&queue, 4);// 3. 入队4个数据printf("开始第一次入队（4个数据）: ");int data = 10;for(int i = 0; i < 4; i++){if(!queue_full(&queue)){printf("%d ", data);queue_push(&queue, data);data += 10;}}printf("\n此时还剩%d个数据\n\n", queue.size);// 4. 出队2个数据printf("开始第一次出队（2个数据）: ");for(int i = 0; i < 2; i++){if(!queue_empty(&queue)){data = queue_pop(&queue);printf("%d ", data);}}printf("\n此时还剩%d个数据\n\n", queue.size);// 5. 入队2个数据printf("开始第二次入队（2个数据）: ");data = 10;for(int i = 0; i < 2; i++){if(!queue_full(&queue)){printf("%d ", data);queue_push(&queue, data);data += 10;}}printf("\n此时还剩%d个数据\n\n", queue.size);// 6. 将所有数据全部取出printf("将全部数据取出: ");while(!queue_empty(&queue)){data = queue_pop(&queue);printf("%d ", data);}printf("\n此时还剩%d个数据\n\n", queue.size);// 销毁队列queue_deinit(&queue);return 0;
}
