队列

1、 队列 就是允许在一端进行插入，在另一端进行删除的线性表。
允许插入的一端称为队尾, 通常用一个队尾指针r指向队尾元素，即r总是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针f指向排头元素的前面。
初始时f=r=0。

2、队列的基本操作：
(1)   新建队列
(2)   入队
(3)   出队
(4)   判断队列是否为空
(5)   判断队列是否为满
(6)   显示队列元素

3、数组模拟队列：

#include <iostream>
#define MAXN 5
using namespace std;
int queue[MAXN] = {0};  //队列 
int front = 0;  //头指针 
int rear = 0;   //尾指针
void addqueue(int value){  //入队
	if(rear >= MAXN){
		cout<<"队满!"<<endl; 
	}else{
		queue[rear] = value;
		rear++;
	}
} 
int delqueue(){   //出队
	int r;
	if(front == rear){
		cout<<"队空"<<endl; 
		r = -1;
	}else{
		r = queue[front];
		front++;
	}	
	return r;
} 
void display(){   //显示队
	int i;
	for(i = front;i < rear;i++){
		cout<<queue[i]<<" ";
	} 
	cout<<endl;	
} 
int main(){
	int order;//口令
	int value,t;
	cout<<"输入指令"<<endl;
	while(1 == 1){
		cout<<"1入队,2出队,3显示！"<<endl;
		cin>>order;
		if(order == 1){
			cin>>value;
			addqueue(value);
			display();
		}else if(order == 2){
			t = delqueue();
			if(t != -1){
				cout<<t<<"已经出队"<<endl;	
				display();
			}else{
				cout<<"队列已空"<<endl;
			}
		}else if(order == 3){
			display();
		}else{
			cout<<"口令错误！"<<endl; 
		}
	}
	return 0;
}

4、循环队列的使用
上述通过数组来实现队列的方法，如果进行插入一次，删除一次的操作，只要数组使用 过一遍数组就会被用光。数组仿真队列的元素全部出队以后，队的首部就会出现需多空位无法使用，导致空间浪费。
解决方法: 将线型数组模拟成环形数组。但无论在线型数组中还是环形数组中，都有一个问题：无法判断队空还是队满。
因为队空的条件是：front==rear;
队满的条件也是: front==rear。
为了解决这个问题，我们在入队时少用一个数据元素空间。
这样，判断队满的方式为：(rear + 1) % MAXN==front。

#include <iostream>
#define MAXN 5
using namespace std;
int queue[MAXN] = {0};  //队列 
int front = 0;          //头指针 
int rear = 0;           //尾指针
void addqueue(int value){ //入队
    if((rear + 1) % MAXN == front){
  //队满 
        cout<<"队满"<<endl;
    }else{
        queue[rear] = value;
        rear = (rear + 1) % MAXN;
    }
} 
int delqueue(){ //出队
    int r;
    if(front == rear){
        cout<<"队空"<<endl;
        r = -1;
    }else{
        r = queue[front];
        queue[front] = -1;   //出队标记 
        front = (front + 1) % MAXN; 
    }   
    return r;
} 
void display(){   //显示队
    if(front == rear){
        cout<<"队空"<<endl; 
    }else{
        int i = front;
        do{
            cout<<queue[i]<<" ";
            i = (i + 1) % MAXN;
        }while(i != rear);
    }
    cout<<endl;   
}
int main(){
    int order;  //口令
    int value,t;
    cout<<"输入指令"<<endl;
    while(1 == 1){
        cout<<"1入队,2出队,3显示！"<<endl;
        cin>>order;
        if(order == 1){
            cin>>value;
            addqueue(value);
            display();
        }else if(order == 2){
            t = delqueue();
            if(t != -1){
                cout<<t<<"已经出队"<<endl;    
                display();
            }else{
                cout<<"队列已空"<<endl;
            }
        }else if(order == 3){
            display();
        }else{
            cout<<"口令错误！"<<endl; 
        }
    }
}