普通数组模拟队列

思路：
定义数组容量maxSize；队列头 front; 队列尾：rear； 以及数组 arr[];
初始化front和rear都为-1；
以rear==maxSize-1来判断队列是否已满
以front==rear来判断队列是否为空
具体代码：

  1. package 算法.Queue;
  3. import java.util.Scanner;
  4. //用数组模拟队列
  5. public class ArrayQueueDemo {
  6.     public static void main(String[] args) {
  7.         ArrayQueue arrqueue=new ArrayQueue(3);
  8.         Scanner input=new Scanner(System.in);
  9.         String n;
  10.         boolean loop=true;
  11.         while (loop){
  12.             System.out.println("s(show)：显示所有数据");
  13.             System.out.println("a(add)：向队列中添加一个数据");
  14.             System.out.println("g(get)：取出队列头");
  15.             System.out.println("h(head)：查看队列头");
  16.             System.out.println("e(exit)：退出");
  17.             n=input.next();
  18.             switch (n){
  19.                 case "s":
  20.                     arrqueue.showQueue();
  21.                     break;
  22.                 case "a":
  23.                     System.out.println("请输入一个数");
  24.                     int value=input.nextInt();
  25.                     arrqueue.addQueue(value);
  26.                     break;
  27.                 case "g":
  28.                     try {
  29.                         int res=arrqueue.getQueue();
  30.                         System.out.println("取出的数据是:"+res);
  31.                     }catch (Exception e){
  32.                         System.out.println(e.getMessage());
  33.                     }
  34.                     break;
  35.                 case "h":
  36.                     try {
  37.                         int res=arrqueue.headQueue();
  38.                         System.out.println("队列的头数据为:"+res);
  39.                     }catch (Exception e){
  40.                         System.out.println(e.getMessage());
  41.                     }
  42.                     break;
  43.                 case "e":
  44.                     input.close();
  45.                     loop=false;
  46.                     break;
  47.                 default:
  48.                     break;
  49.             }
  50.         }
  52.         System.out.println("程序退出");
  53.     }
  54. }
  56. //用数组模拟队列
  57. class ArrayQueue{
  58.     private int maxSize;//表示数组最大容量
  59.     private int front;//队列头
  60.     private int rear;//队列尾
  61.     private int[] arr;//该数组用于存储数据，模拟队列
  63.     public ArrayQueue(int maxSize) {
  64.         this.maxSize = maxSize;
  65.         this.arr=new int[maxSize];
  66.         this.front = -1;
  67.         this.rear = -1;
  68.     }
  70.     public boolean isEmpty(){//判断队列是否为空
  71.         return front==rear;
  72.     }
  74.     public  boolean isFull(){//判断队列是否已满
  75.         return rear==maxSize-1;
  76.     }
  78.     public void addQueue(int value){//向队列中添加一个数据
  79.         if(isFull()){
  80.             System.out.println("队列已满");
  81.             return;
  82.         }
  83.         arr[++rear]=value;
  84.     }
  86.     public int getQueue(){//取出队列头
  87.         if(isEmpty()){
  88.             throw new RuntimeException("队列为空，不能取数据");
  89.         }
  90.         return arr[++front];
  91.     }
  93.     public void showQueue(){//显示所有数据
  94.         if(isEmpty()){
  95.             System.out.println("队列为空，没有数据");
  96.             return;
  97.         }
  98.         for (int i=0;i<arr.length;i++){
  99.             System.out.println("arr["+i+"]="+arr[i]);
  100.         }
  101.     }
  103.     public int headQueue(){//查看队列头
  104.         if(isEmpty()){
  105.             throw new RuntimeException("队列为空，不能无头数据");
  106.         }
  107.         return arr[front+1];
  108.     }
  109. }

缺点：
此种方法有很多问题，数组只能利用一次
所以我们一般用循环数组来模拟队列

循环数组模拟队列

思路：
定义数组容量maxSize；队列头 front; 队列尾：rear； 以及数组 arr[];
初始化front和rear都为0；
以front==rear来判断队列是否为空

注意！以(rear+1)%maxSize==front来判断队列是否已满，因为是循环数组
且其数组存储数据的长度为 (rear+maxSize-front)%maxSize

因为需要用maxSize去做一个判断，且我的构造器是这个逻辑，
public CircleArrayQueue(int maxSize) {
this.maxSize = maxSize;
this.arr=new int[this.maxSize];
this.front = 0;
this.rear = 0;
}
所以，我的循环数组只能储存maxSize-1个数据

package 算法.Queue;

import java.util.Scanner;

public class CircleArrayQueueDemo {//用循环数组模拟队列

    public static void main(String[] args) {
        CircleArrayQueue circlequeue=new CircleArrayQueue(4);
        Scanner input=new Scanner(System.in);
        String n;
        boolean loop=true;
        while (loop){
            System.out.println("s(show)：显示所有数据");
            System.out.println("a(add)：向队列中添加一个数据");
            System.out.println("g(get)：取出队列头");
            System.out.println("h(head)：查看队列头");
            System.out.println("e(exit)：退出");
            n=input.next();
            switch (n){
                case "s":
                    circlequeue.showQueue();
                    break;
                case "a":
                    System.out.println("请输入一个数");
                    int value=input.nextInt();
                    circlequeue.addQueue(value);
                    break;
                case "g":
                    try {
                        int res=circlequeue.getQueue();
                        System.out.println("取出的数据是:"+res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case "h":
                    try {
                        int res=circlequeue.headQueue();
                        System.out.println("队列的头数据为:"+res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case "e":
                    input.close();
                    loop=false;
                    break;
                default:
                    break;
            }
        }

        System.out.println("程序退出");
    }
}

class CircleArrayQueue{//用数组模拟队列
    private int maxSize;//表示数组最大容量
    private int front;//队列头
    private int rear;//队列尾
    private int[] arr;//该数组用于存储数据，模拟队列

    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        this.arr=new int[this.maxSize];
        this.front = 0;
        this.rear = 0;
    }

    public boolean isEmpty(){//判断队列是否为空
        return front==rear;
    }

    public  boolean isFull(){//判断队列是否已满
        return (rear+1)%maxSize==front;
    }

    public void addQueue(int value){//向队列中添加一个数据
        if(isFull()){
            System.out.println("队列已满");
            return;
        }
        arr[rear]=value;
        rear=(rear+1)%maxSize;
    }

    public int getQueue(){//取出队列头
        if(isEmpty()){
            throw new RuntimeException("队列为空，不能取数据");
        }
        int value=arr[front];
        front=(front+1)%maxSize;
        return value;
    }

    public void showQueue(){//显示所有数据
        if(isEmpty()){
            System.out.println("队列为空，没有数据");
            return;
        }
        for (int i=front;i<front+queueSize();i++){
            System.out.println("arr["+i%maxSize+"]="+arr[i%maxSize]);
        }
    }

    public int headQueue(){//查看队列头
        if(isEmpty()){
            throw new RuntimeException("队列为空，不能无头数据");
        }
        return arr[front];
    }

    public int queueSize(){
        return (rear+maxSize-front)%maxSize;
    }
}