（二）Java数据结构之基于数组实现的环形队列

- 日理万妓 2022-12-12 15:20 120阅读 0赞

package top.baikunlong.queue;
    
    import java.util.Scanner;
    
    /**
     * @author baikunlong
     * @date 2020/10/7 11:53
     */
    public class ArrayQueue {
    
        private int maxSize;//最大容量，实际存储只有maxSize-1，有一个空间为预留空间。
        private int front;//队头
        private int rear;//队尾
        private int[] arr;
    
        public ArrayQueue(int maxSize) {
            this.maxSize = maxSize;
            arr = new int[maxSize];
        }
    
        public boolean isFull() {
            //这里要预留一个空间，也就是有一个空间永远是利用不了的，不然rear==front了，区别不了是空队列还是满队列。。。
            return (rear + 1) % maxSize == front;
        }
    
        public boolean isEmpty() {
            return rear == front;
        }
    
        /**
         * 入队
         *
         * @param n
         */
        public void add(int n) {
            if (isFull()) {
                System.out.println("队列已满");
            } else {
                arr[rear] = n;
                rear = (rear + 1) % maxSize;
            }
        }
    
        /**
         * 出队，会移除数据
         *
         * @return
         */
        public int poll() {
            if (isEmpty()) {
                throw new RuntimeException("队列为空");
            } else {
                int n = arr[front];
                front = (front + 1) % maxSize;
                return n;
            }
        }
    
        /**
         * 打印队列
         */
        public void show() {
            //从front开始遍历，遍历到front+size
            for (int i = front; i < front+size(); i++) {
                System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
            }
        }
    
        /**
         * 当前队列有效个数
         *
         * @return
         */
        public int size() {
            return (rear + maxSize - front) % maxSize;
        }
    
        public static void main(String[] args) {
            ArrayQueue queue = new ArrayQueue(4);
            Scanner scanner = new Scanner(System.in);
            while (true) {
                System.out.println("a(add): 添加数据到队列");
                System.out.println("p(poll): 从队列取出数据");
                System.out.println("s(show): 显示队列");
                System.out.println("e(exit): 退出程序");
                String s = scanner.nextLine();
                switch (s) {
                    case "a":
                        queue.add(scanner.nextInt());
                        break;
                    case "p":
                        try {
                            System.out.println("出队得到："+queue.poll());
                        } catch (Exception e) {
                            System.out.println(e.getMessage());
                        }
                        break;
                    case "s":
                        queue.show();
                        break;
                    case "e":
                        System.exit(0);
                        break;
                }
            }
    
        }
    }