一 . 什么是队列

           队列，和栈一样，也是一种对数据的"存"和"取"有严格要求的线性存储结构。

           队列的两端都"开口"，要求数据只能从一端进，从另一端出，如图所示：

          队列中数据的进出要遵循 "先进先出" 的原则

二 . 队列的实现方式

        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("退出程序");}}