使用数组模拟队列

╰半夏微凉° 2023-06-30 01:41 10阅读 0赞

package com.zzb.queue;
    
    import java.util.Scanner;
    
    /**
     * @Auther: Administrator
     * @Date: 2020/1/13 13:29
     * @Description: 使用 数组 模拟 队列
     *
     * 队列是一个有序列表，可用 数组 或 链表 来实现
     * 队列遵循 先进先出 的原则，即先存进队列的数据被先取出来，后存进的数据被后取出来
     *
     * 数组模拟队列的思路
     * maxSize 成员变量表示队列的最大容量，即队列中数组的最大容量
     * 队列的输出、输入分别从前后端处理，成员变量front、rear分别记录队列的前后端索引，front随着队列中的数据输出而改变，
     * rear随着数据输入队列而改变
     *
     * 问题及优化（另一篇博文：数组模拟环形队列）
     * （1）数组使用一次就不能用，没有达到复用的效果
     * （2）数组使用算法，改进为一个环形队列（将数组看做是一个环形），取模（%）实现
     */
    public class ArrayQueueTest {
        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("---------------a(add)：添加数据到队列----------------");
                System.out.println("---------------g(get)：从队列中获取数据---------------");
                System.out.println("---------------s(show)：遍历队列---------------------");
                System.out.println("---------------h(head)：查看队列的头部数据-------------");
                System.out.println("---------------e(exit)：退出程序----------------------");
                // 接收一个字符
                key = scanner.next().charAt(0);
                switch(key) {
                    case 'a':
                        System.out.println("输入一个数据");
                        int data = scanner.nextInt();
                        queue.add(data);
                        break;
                    case 'g':
                        int get = queue.get();
                        System.out.println("获取的数据为  " + get);
                        break;
                    case 's':
                        queue.showQueue();
                        break;
                    case 'h':
                        int head = queue.head();
                        System.out.println("队列的头部数据为  " + head);
                        break;
                    case 'e':
                        loop = false;
                        scanner.close();
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序退出");
        }
    }
    
    // 数组模拟队列
    class ArrayQueue {
        // 队列的最大容量，即队列中数组的最大容量
        private int maxSize;
        // 队列头索引，即输出数据时队列中的数组要移动的索引
        // 指向队列头的前一个位置
        private int front;
        // 队列尾索引，即输入数据时队列中的数组要移动的索引
        // 指向队列的最后一个数据
        private int rear;
        // 数组用于模拟队列，存储数据
        private int[] array;
    
        // 构造器初始化队列
        public ArrayQueue(int maxSize) {
            this.maxSize = maxSize;
            this.array = new int[maxSize];
            // 初始化，指向队列头的前一个位置
            this.front = -1;
            // 初始化，指向队列的最后一个数据
            this.rear = -1;
        }
    
        // 判断队列是否为空
        public boolean isEmpty() {
            return this.rear == this.front;
        }
    
        // 判断队列是否满
        public boolean isFull() {
            return this.rear == this.maxSize - 1;
        }
    
        // 添加数据到队列
        public void add(int data) {
            // 判断队列是否满
            if(isFull()) {
                System.out.println("队列已满，不能添加数据！");
                return;
            }
            this.rear++;
            this.array[this.rear] = data;
        }
    
        // 从队列中获取数据
        public int get() {
            // 判断队列是否为空
            if(isEmpty()) {
                throw new RuntimeException("队列为空，不能获取数据！");
            }
            this.front++;
            return this.array[this.front];
        }
    
        // 遍历队列中的数据
        public void showQueue() {
            // 判断队列是否为空
            if(isEmpty()) {
                System.out.println("队列为空");
                return;
            }
            // 已经获取的数据就不能被遍历出来
            for(int i = this.front+1; i <= this.rear; i++) {
                System.out.print(this.array[i] + "\t");
            }
            System.out.println();
        }
    
        // 显示队列的头部数据
        public int head() {
            // 判断队列是否为空
            if(isEmpty()) {
                throw new RuntimeException("队列为空！");
            }
            return this.array[this.front+1];
        }
    }