前言
-
《数据结构系列首页》是数据结构系列文章的首页,其中会逐步更新各种数据结构的实现,有兴趣的选手可以一看。
- 首页中不仅有各种数据结构的实现,还有学习数据结构必备的基础知识,如果有选手觉得自己的基础不太牢固,可以先将搞定基础知识,之后再攻克数据结构这一部分的内容。
- 由于我也是刚开始学习数据结构这门课程,所以如果发现文章中存在错误,希望大家可以直接指出,我将第一时间修改。
- 更多数据结构的实现请见《数据结构系列文章》,我会在学习完新的数据结构后不断更新其中的内容。
开场白
队列(queue)是只允许在一端进行插入操作,在另一端进行删除操作的线性表,是一种先进先出(First In First Out)的线性表,简称FIFO结构。允许插入的一端成为队尾,允许删除的一端为队头。需要注意的是,循环队列的队头下标始终为队头元素的下标,但队尾下标始终为队尾元素的下一个元素的下标;其次,长度为n的循环队列可以存放的元素个数始终为n-1,空余一个位置不放元素是为了区别队列空和队列满。本篇采用动态一维数组实现了队列的循环存储,同时实现了循环队列的一些操作。
具体实现
头文件
#include <stdio.h> // printf、scanf函数所在的头文件
#include <stdlib.h> // exit函数所在的头文件
#include <malloc.h> // calloc、free函数所在的头文件
#include <math.h> // 宏OVERFLOW所在的头文件,OVERFLOW的值为3
// 按照严蔚敏老师书中的编程习惯,定义如下4个宏
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
typedef int Status; // Status是函数返回值的类型,其返回的是函数执行结果的状态
typedef int ElemType; // ElemType是元素的数据类型,想要整体改变元素的数据类型只需改变ElemType前的数据类型即可
// 定义循环队列结构
#define QUEUE_MAX_SIZE 5 // 定义队列的长度(实际长度为4,规定长度为n的循环队列的可用长度为n-1)
typedef struct CyclicQueue
{
ElemType* base; // 动态一位数组的基地址
int front; // 队头元素的下标
int rear; // 队尾元素下一个元素的下标
}QUEUE; // QUEUE 等同于 struct CyclicQueue
函数声明
void init_queue(QUEUE&);
void destroy_queue(QUEUE&);
void clear_queue(QUEUE&);
Status is_empty(QUEUE&);
Status is_full(QUEUE&);
Status get_head_element(QUEUE&, ElemType&);
Status