一 . 什么是队列
队列，和栈一样，也是一种对数据的"存"和"取"有严格要求的线性存储结构。
队列的两端都"开口"，要求数据只能从一端进，从另一端出，如图所示：
队列中数据的进出要遵循 "先进先出" 的原则
二 . 队列的实现方式
1.实现有两种方式
1.1. 顺序队列 ：存储结构为数组的形式
1.2. 链队列 ：存储结构为链表的形式
2 . 实现思路
2.1 队列的输入输出 是分别从前后端来控制的 ，所以需要两个变量来标记前后端 ，
还需要存储数据的格式 以及容量
前端队列头 front 队列尾 rear （都指向 第一个元素之前）
最大容量 MaxSize
这里出队里后会造成前面的空间浪费 怎么改进呢 ？ 改变变量的含义 下面有详细
3 . 代码实现顺序队列
class ArrayQueue{
//这个类表示模拟的队列
private int maxSize; // 最大容量
private int front; //开始队列头
private int rear; //队列尾
private int [] arr; //数组存放数据
//构造方法表示能够创建出一个队列 ,传入一个容量
public ArrayQueue(int arrMaxSize) {
maxSize=arrMaxSize;
arr=new int[maxSize];
front=-1; //表示头部变量指向 队列头的第一个位置之前；
rear=-1;
}
//判断队列是否为满
public boolean isFull() {
return rear==maxSize-1;
}
//判断队列是否是空的
public boolean isEmpty() {
return rear==front;
}
//给队列添加数据 入队列
public void addQueue(int nums) {
//判断是否满了
if(isFull()) {
System.out.println("队列元素满了，不能添加数据---");
return;
}
rear++;
arr[rear]=nums;
}
//取出数据 ，出队列
public int getQueue() {
//判断是否为空
if(isEmpty()) {
throw new RuntimeErrorException(null, "队列为空，不能取数据");
}
front++;
//取出数据后，重新的复制原来的位置 才是删除去除，但空间不能利用了
int s= arr[front];
arr[front]=0;
return s;
}
//打印队列的所有数据
public void showQueue() {
if(isEmpty()) {
System.out.println("数列为空，不能查看");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d]=%d\n",i,arr[i]);
}
}
}4. 循环队列怎么写呢
改造环形队列 实现空间利用
现在这里的变量 改变了意义
Front :指向队列的第一个元素 (默认初始为0）（原来是第一个元素后一个位置）
Rear : 指向队列的最后一个元素后一个位置默认初始为0）（原来是包含后一个位置）
主要改进 就是对空间能够利用
空出一个空间作为约定位置
空队列为 Front==rear;
此时队列满时条件 (rear+1)%maxSize==Front;
队列中有效的数字 （rear+maxSize-Front)%maxsize
代码实现
class CircleQueue{
//这个类表示模拟的队列
private int maxSize; // 最大容量
private int front; //开始队列头
private int rear; //队列尾
private int [] arr; //数组存放数据
//构造方法表示能够创建出一个队列 ,传入一个容量
public CircleQueue(int arrMaxSize) {
maxSize=arrMaxSize;
arr=new int[maxSize];
front=0; //表示头部变量指向 队列头的第一个位置
rear=0;
}
//判断队列是否为满
public boolean isFull() {
return (rear+1) % maxSize==front;
}
//判断队列是否是空的
public boolean isEmpty() {
return rear==front;
}
//给队列添加数据 入队列
public void addQueue(int nums) {
//判断是否满了
if(isFull()) {
System.out.println("队列元素满了，不能添加数据---");
return;
}
//rear++ 这里的rear意义改变了,不需要后移位置再赋值
arr[rear]=nums;
rear = (rear+1)%maxSize;
}
//取出数据 ，出队列
public int getQueue() {
//判断是否为空
if(isEmpty()) {
throw new RuntimeErrorException(null, "队列为空，不能取数据");
}
//front++ ，front此时存的就是第一个元素
//取出数据后，重新的赋值原来的位置 才是删除去除
int s= arr[front];
arr[front]=0;
front=(front+1)%maxSize;
return s;
}
//打印队列的所有数据
public void showQueue() {
if(isEmpty()) {
System.out.println("数列为空，不能查看");
return;
}
for (int i = front; i < front+Size(); i++) {
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
}
}
//求当前的队列有效数字
public int Size() {
return (rear+maxSize-front)%maxSize;
}
}测试代码 （这里的思想一定要学会）
public class ArryQueueTest {
public static void main(String[] args) {
//创建构造的队列
ArrayQueue queue = new ArrayQueue(3);
//创建出一个菜单，直接能提示给用户；
char key=' '; //接受用户输入数据
Scanner scanner= new Scanner(System.in);
boolean loop=true;
while(loop) {
System.out.println("s(show) :显示队列数据");
System.out.println("e(exit) :退出程序");
System.out.println("a(add) :添加数据");
System.out.println("g(get) :获得队列数据");
System.out.println("i(isFull):显示队列是否满了");
key=scanner.next().charAt(0); //获得接受字符串；
switch(key) {
case 's' : queue.showQueue(); break;
case 'e' :
scanner.close();
loop=false; break;
case 'a' :
System.out.println("输入一个数据");
int nums = scanner.nextInt();
queue.addQueue(nums);
break;
case 'g' :
try {
int res = queue.getQueue();
System.out.printf("取得的数据为%d\n",res);
}catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'i' : queue.isFull(); break;
}
}
System.out.println("退出程序");
}
}