队列的原理与应用

        队列和栈类似，都是线性结构，区别在于，栈遵循的是“先进后出”的原则，而队列遵循的是“先进先出”的原则，也就是FIFO（first input first output）。队列的两端都可以操作，只不过要求数据只能从其中一端写入，另一端删除。允许数据插入的一端通常称为队尾（Tail或Rear），允许删除的一端被称为队头队首（Head或Front）。

        允许数据插入的一端称为队尾，将数据插入到队列中的操作称为入队（enqueue）

        上图为入队（enqueue）的示意图，相似的，允许数据删除的一端称为队首/队头（Front/Head），将数据从队列中删除的操作称为出队，英文dequeue。

        队列也属于线性结构，在实现的时候，可以以数组或者链表为基础来实现队列的操作。如果以数组为基础来实现队列，由于C的特性需要预先为数组分配空间，通常采用循环访问数组的方式来访问，因为如果不采用循环，在删除数据时，其需要将尾部的数据删除，并且将后续的数据全部向前移动一位，其时间复杂度为O(n)，否则将会出现数组访问错误，故通常采用环形缓冲区的方式来实现队列。

        循环队列也被称作环形缓冲区，在插入数据时，只需将队尾指针+1，在删除数据时，只需将队首指针向后移动一位，当指针移动到最后时，自动将指针移动到数组的最开始元素。

        本文以环形缓冲区为例，设计队列文件。定义结构体Queue用于队列操作。

#define QUEUE_TYPE int   //队列数据类型 
#define QUEUE_MAX  100    //队列最大存储数据数量 
//队列结构体
typedef struct _Queue{
    QUEUE_TYPE _data[QUEUE_MAX];
    int front_cnt;
    int rear_cnt;
    int data_cnt;
    int _max_datacnt;
} Queue;

        利用结构体可以实现队列的管理，其中front_cnt和rear_cnt分别表示队首和队尾指针相对于数组的开始地址的偏移量，QUEUE_TYPE宏为数据类型，QUEUE_MAX表示队列的上限，定义结构体后，定义管理函数，通常一个队列包括入队、出队、数据读取、队列生成与销毁功能，设计五大功能接口。

//创建队列
Queue* create_que(){
    Queue* new = calloc(1, sizeof(Queue));
    if(!new){
        printf("未能正确在堆上申请空间\n");
        return NULL;
    }
    new->_max_datacnt = QUEUE_MAX - 1;
    new->data_cnt = 0;
    new->front_cnt = 0;
    new->rear_cnt = 0;
    return new;
};
//读取队列中的数据，返回从队首开始的第n个,如果超出最大长度，会自动截断为循环表最大储存的余数，输入0读取队首的数据
QUEUE_TYPE read_que(Queue *que, int n, bool force){
    if((!que) || (n < 0)){
        if(!que){
            printf("传入的队列为空");
        }else if (n < 0) {
            printf("欲读取队首前的数据，操作未定义");
        }
        if(force){
            return 0;
        } else {
            exit(-1);
        }
    }
    int read_n = (n + que->front_cnt) % QUEUE_MAX;
    return que->_data[read_n];
};
//向队列中插入数据
bool insert_que(Queue *que, QUEUE_TYPE data){
    if(que->data_cnt == que->_max_datacnt){
        printf("队列已满，无法继续插入数据!\n");
        return false;
    }
    if(!que){
        printf("输入的队列不存在!\n");
        return false;
    }
    //判断指针是否到了数组最末端，同时自动偏移计数
    if((++que->rear_cnt) == QUEUE_MAX) que->rear_cnt = 0;
    que->_data[que->rear_cnt] = data;
    que->data_cnt++;
    return true;
};
//从队列中移除数据
bool remove_que(Queue *que){
    if(que->data_cnt == 0){
        printf("队列为空，无法移除数据!\n");
        return false;
    }
    if(!que){
        printf("输入的队列不存在!\n");
        return false;
    }
    //判断指针是否到了数组最末端，同时自动偏移计数
    if(++que->front_cnt == QUEUE_MAX) que->front_cnt = 0;
    que->_data[que->front_cnt] = 0;
    que->data_cnt --;
    return true;
};
//摧毁队列
bool destory_que(Queue **que){
    free(*que);
    return true;
};

        读者若需要源文件，可以点击立即下载获得队列的头文件和源代码，不过如果需要将其应用到项目，请注意保留版权注释哦，搬砖不易，还望谅解。