import java.util.Scanner;

/**
 * @Auther: Arsenal
 * @Date: 2020-03-07 20:43
 * @Description: 队列
 */
public class Queue {
    public static void main(String[] args) {

        // 测试数组模拟环形队列
        System.out.println("测试数组模拟环形队列");
        CircleArrayQueue queue = new CircleArrayQueue(4);
        char c;
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        while (loop) {
            System.out.println("a(add) : 队列添加数据");
            System.out.println("g(get) : 从队列取数据");
            System.out.println("h(head) : 获取队列头部数据");
            System.out.println("s(show) : 显示队列所有数据");
            System.out.println("e(exit) : 退出程序");
            // 接收字符
            c = scanner.next().charAt(0);
            switch (c) {
                case 'a':
                    System.out.println("请输入一个数：");
                    int val = scanner.nextInt();
                    queue.addQueue(val);
                    System.out.printf("当前队列的头部指针：%d，尾部指针：%d\n", queue.getFront(), queue.getRear());
                    break;
                case 'g':
                    try {
                        int n = queue.getQueue();
                        System.out.println("从队列取出数据：" + n);
                        System.out.printf("当前队列的头部指针：%d，尾部指针：%d\n", queue.getFront(), queue.getRear());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int n = queue.headQueue();
                        System.out.println("队列的头部数据：" + n);
                        System.out.printf("当前队列的头部指针：%d，尾部指针：%d\n", queue.getFront(), queue.getRear());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 's':
                    queue.showQueue();
                    System.out.printf("当前队列的头部指针：%d，尾部指针：%d\n", queue.getFront(), queue.getRear());
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("退出程序");
    }
}

/**
 * 环形队列
 * 思路如下:
 * 1.  front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素。front 的初始值 = 0;
 * 2.  rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定。rear 的初始值 = 0；
 * 3. 当队列满时，条件是  (rear  + 1) % maxSize == front 【满】;
 * 4. 对队列为空的条件， rear == front 【空】;
 * 5. 当我们这样分析， 队列中有效的数据的个数   (rear + maxSize - front) % maxSize ;
 * 6. 我们就可以在原来的队列上修改得到，一个环形队列。
 */
class CircleArrayQueue {

    private int maxSize; //队列长度
    private int front; //队列头
    private int rear; //队列尾
    private int[] arr; //数组队列

    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        this.front = 0; // 就指向队列的第一个元素
        this.rear = 0; // 指向队列的最后一个元素的后一个位置
        this.arr = new int[maxSize];
    }

    /**
     * 判断队列是否满了
     * @return
     */
    private boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

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

    /**
     * 入队
     * @param number 入队值
     */
    public void addQueue(int number) {
        if (isFull()) {
            throw new RuntimeException("队列已满");
        }

        arr[rear] = number; //赋值
        rear = (rear + 1) % maxSize; // 环形队列，取模
    }

    /**
     * 出队
     * @return 出队值
     */
    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        int value = arr[front]; //临时变量，要返回
        front = (front + 1) % maxSize;// 环形队列，取模
        return value;
    }

    /**
     * 展示队列
     */
    public void showQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }

        // 遍历数组
        // 不能单一的对角标递增处理，会出现角标越界异常
        // 应对环形队列内部的有效数据，从头部数据开始遍历依次取出
        // 有效数据的下标：i % maxSize
        for (int i = front; i < front + size(); i++) {
            System.out.println("arr[" + i % maxSize + "]=" + arr[i % maxSize]);
        }
        System.out.println("front=" + front);
        System.out.println("rear=" + rear);
    }

    /**
     * 展示队列第一个元素
     * @return 第一个元素
     */
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return arr[front];
    }

    /**
     * 返回头指针
     * @return 头指针
     */
    public int getFront() {
        return front;
    }

    /**
     * 返回尾指针
     * @return 尾指针
     */
    public int getRear() {
        return rear;
    }

    /**
     * 获取队列有效数据的个数
     * @return 队列有效数据的个数
     */
    private int size() {
        return (rear + maxSize - front) % maxSize;
    }
}