【数据结构】
队列：
- 一种访问受限的线性表，只能在一端进行插入，另一端删除
- 先进先出（FIFO），队尾插入，队头删除
队列的分类：顺序队列、链表队列
顺序队列：底层的数据结构是内存连续的，基于数组实现队列的先进先出
队头为0，队尾为4的删除数据的时间复杂度为o(n),太高，因此我们一般不用，为了减低时间复杂度，我们一般使用循环队列来处理顺序队列，也就是在逻辑上将数组变成一个环。
循环队列：以数组的形式模拟出环状结构，front是队头指针，队头（第一个）元素的下标；rear是队尾指针，最后一个元素的下一个下标
注意：因为是环形设计，所以往后走不能直接++，容易越界，应该为front=（front+1）%size，rear=（rear+1）%size
插入的操作：头指针front和尾指针rear开始同时指向0下标，每插入一个元素，rear向后移动一个下标；arr[rear]=xx;没有循环，时 间复杂度为o(1);
注意：当rear指向最后一个5下标时，因为不能从5直接指向0，所以不能使用rear++，必须使用 rear=（rear+1）%MAX_SIZE；eg: rear=（rear+1）%6;rear=(5+1)%6=0(rear是数组的下标)；%为取余
删除的操作：每删除一个数据，front向后移动一个下标；front++；只删除元素，不移动数据；时间复杂度为o(1);
判空和判满：因为front==rear既可以判空也可以判满，所以不能用此方法，这时，我们需要牺牲一个内存单元，每次满的时候会 选择牺牲front之前的内存单元;(牺牲的内存单元不固定，每次轮番牺牲)
判空empty：rear==front
判满full：（rear+1）%6==front
代码实现：
结构设计：
typedefn int ElemType;
#define MAX_SIZE 9;typedef struct Queue
{ElemType arr[MAX_SIZE];//数组arr[10]int front;//队头指针int rear;//队尾指针
}Queue,pQueue;初始化：
void init(pQueue pqu)
{if(pqu!=NULL){pqu->frpnt=pqu->rear=0;}
}入队：
(1)判满
int full(pQueue pue)//1 full,0 not full
{return (pqu->rear+1)%MAX_SIZE==pqu->front ?1:0;
} (2)
int enqueue(pQueue pqu,ElemType val)//1 success,0 fail
{if(full(que)){return 0;}pqu->arr[pqu->rear]=val;pqu->rear=(pqu->rear+1)%MAX_SIZE;return 1;
}出队：
(1)判空
int empty(pQueue pue)//1 empty,0 not empty
{return pqu->rear==pqu->front ? 1:0;
}(2)
int dequeue(pQueue pue)//单纯的删除元素，没有存储
{if(empty(pue)){return 0;}pqu->front=(pqu->front+1)%MAX_SIZE;//向前走一个return 1;
}获取队头元素：
int front(pQueue pqu)
{if(empty(pqu)){throw std::exception("queue is empty!")；//一般使用c++处理机制，抛出异常//return -1;//-1有两种情况，数值为-1或者队列为空，因此是异常的，一般不建议这样使用}return pqu->arr[pqu->front];
}获取队尾元素：
int back(pQueue pqu)
{if(empty(pqu)){throw std::exception("queue is empty!")；//#include<iostream>c++头文件// return -1;//-1代表队列为空}return pqu->arr[(pqu->rear+MAX_SIZE-1)%MAX_SIZE];//回退一个，通过rear获取上一个元素为队尾元素
}函数的实现：
int main()
{Queue que;init(&que);for(int i=0;i<8;i++){enqueue(&que,i);}int rtfront=front(&que);int reback=back(&que);printf("front:%d\n",rtfront);printf("back:%d\n",rtback);dequeue(&que);enqueue(&que,100)；rtfront=front(&que);reback=back(&que);return 0;
}考题：
1、为什么设计成环形？
因为其他方法复杂度太高，而环形入队出队时间复杂度都为O(1)，速度快
2、为什么要空一个格子？
判断为空：front==rear
判断为满：设计时最后一个格子不使用，rear再往后走一步front这时就满，浪费一个单元格
因为front==rear既可以判空也可以判满，所以不能用此方法，这时，我们需要牺牲一个内存单元，每次满的时候会选择牺牲front之前的内存单元;(牺牲的内存单元不固定，每次轮番牺牲)
3、因为是环形设计，所以往后走不能直接++，容易越界，应该为front=（front+1）%size，rear=（rear+1）%size