原理
队列（Queue），是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。其操作特性为先进先出（First In First Out，FIFO），并且只允许在队尾进，队头出。
常见实现方法
通过数组实现
通过数组实现，用head和tail分别表示指向的位置
优点：实现简单
缺点：
- 需要在创建前确定最大容量
- 当pop出元素的时候，该空间不可再继续使用，空间利用率较低，而且是一次性的
判满标志：rear=MAXSize-1
判空标志：rear=head
代码实现
struct Queue{
int data[100];
int head;
int tail;
Queue(){
head=0;
tail=0;
}
bool isEmpty(){
if(this->tail==this->head){
return true;
}
return false;
}
void push(int x){
if(this->tail==100-1){
cout<<"FULL";
return;
}
data[this->tail]=x;
tail++;
}
int pop(){
if(this->isEmpty()){
cout<<"EMPTY";
return -1;
}
int temp=this->data[this->head];
head++;
return temp;
}
int front(){
if(this->isEmpty()){
cout<<"EMPTY";
return -1;
}
return this->data[this->head];
}
};通过链表实现
原理和数组实现的队列相类似
优点：
- 不需要在创建时确定容量，容量可变
- 更加灵活
缺点：
- 实现复杂
- 非连续存储
判满标志：NULL
判空标志：head->next == nullptr;(带有空头节点的)
代码实现(带有空头节点的)
struct Node{
int data;
Node *next;
Node(){
data=-1;
next=nullptr;
}
};
struct LinkedQueue{
Node *head;//队头删除 队尾增加
Node *tail;
int length;
LinkedQueue(){
this->head=new Node;
this->tail=this->head;
}
bool isEmpty(){
/*
if(this->head->next==this->tail){
return true;
}
return false;
*/
return this->head->next == nullptr;
}
void push(int x){
this->length++;
Node *temp=new Node;
temp->data=x;
temp->next=nullptr;
this->tail->next=temp;
this->tail=temp;
}
int pop(){
if(this->isEmpty()){
cout<<"EMPTY";
return -1;
}
this->length--;
Node *p;
int temp;
p=this->head->next;
temp=p->data;
this->head->next=p->next;
delete p;
return temp;
}
int top(){
if(this->isEmpty()){
cout<<"EMPTY";
return -1;
}
return this->head->next->data;
}
void println(){
while(!this->isEmpty()){
cout<<this->pop()<<" ";
}
}
};循环队列
为了解决数组实现的队列存在的假溢出和空间利用率低下的问题，可以通过循环队列解决。循环队列可以理解为将队列的头和尾相链接起来，通过模运算等操作，当队头有空位而队尾满了的时候将tail接着指向队头前方的空位，实现空间的最大化利用。
优点：
- 数组实现队列，实现起来较为简单
- 实现空间的高效利用
- 解决假溢出问题
坑点：
- 求模运算的时候有时候会搞错
- 可用空间是数组长度-1，预留的一个是为了判断队列满的状态。
- 在插入数据的时候必须先检查队列是否已满！！！
判空标志：rear=head;
判满
如果数组的空间全部占满，则rear=head是无法判断队列空和满的状态，因此需要预留一个空位来实现判满的操作，当循环队列是满的时候，则(tail+1)MOD(MAXSize)=head
代码实现
struct ArrayQueue{
int *data;
int maxSize;
int head;
int tail;
ArrayQueue(int SIZE){
this->data=new int[SIZE];
this->maxSize=SIZE;
this->head=0;
this->tail=0;
}
bool isEmpty(){
if(this->head==this->tail){
return true;
}
return false;
}
bool isFull(){
if((this->tail+1)%this->maxSize==this->head){
return true;
}
return false;
}
void push(int x){
if(this->isFull()){
cout<<"FULL"<<endl;
return;
}else{
this->data[this->tail]=x;
if(this->tail==this->maxSize){
this->tail=0;
}else{
this->tail++;
}
}
//this->tail=(this->tail+1)%this->maxSize;
}
int pop(){
if(this->isEmpty()){
cout<<"EMPTY";
return -1;
}
int temp=this->head;
if(this->head==this->maxSize){
this->head=0;
}else{
this->head++;
}
//this->head=(this->head+1)%this->maxSize;
return this->data[temp];
}
int top(){
if(this->isEmpty()){
cout<<"EMPTY";
return -1;
}
return this->data[this->head];
}
void println(){
while(!this->isEmpty()){
cout<<this->pop()<<" ";
}
cout<<endl;
}
};