小胡博客

环形队列

package com.xiaohu.suanfa.queue;

/**
 * 实现说明:
 * 1.通过尾索引的下一个为头索引时表示队满，，即将队列容量空出
 * 一个作为约定 （tail+1）%maxSize = head;
 * 2.tail = head 代表队列为空
 */

import java.util.Scanner;

/**
 * @author 小胡哥哥
 * NO BB show your code
 * 队列plus 实现环形队列，进行可复用
 */
public class CircularQueue {
    class ArrayQueue {
        //表示最大数组容量
        private int maxSize;
        //队头
        private int head;
        //队尾
        private int tail;
        //数组
        private int[] arr;

        //构造初始化
        public ArrayQueue(int maxsize) {
            //预留一个位置
            this.maxSize = maxsize + 1;
            arr = new int[maxsize];
            //刚开始队头队尾都为0
            head = 0;
            tail = 0;
        }

        private boolean isEmpty() {
            //如果队头指向的元素等于队尾指向的元素，则为空
            return head == tail;
        }

        private boolean isFull() {
            // 环形队列 假定预留一个位置作为约定,假设maxSize = 3
            //tail+1把空间沾满，而% maxSize  2%3 = 2没满 3%3 = 0=head满了，防止越界
            return (tail + 1) % maxSize == head;
        }

        /**
         * 添加
         */
        private void add(int num) {
            if (isFull()) {
                throw new RuntimeException("队列已满,无法添加元素");
            }
            //因为tail代表最后一个元素,所以他位置就等于添加元素的位置
            arr[tail] = num;
            //防止越界 原本是直接tail++, 但会越界，必须取模 ，加完之后 tail后移一位
            tail = (tail + 1) % maxSize;
            System.out.println("添加成功");
        }

        /**
         * 获得元素
         */
        private int get() {
            if (isEmpty()) {
                throw new RuntimeException("队列为空,无法获得元素");
            }
            //因为head指向第一个元素，但不能直接返回(队列先进先出) 因为需要head后移一位，直接返回无法后移
            //定义一个临时变量存储head 然后 head取模后移一位 返回临时变量
            int temp = arr[head];
            head = (head + 1) % maxSize;
            return temp;
        }

        /**
         * 遍历a
         */
        public void showElem() {
            if (isEmpty()) {
                System.out.println("队列为空~~");
            }
            //取出来的元素不需要遍历出来 tail = 0,head = 1 maxSize=4
            for (int i = head; i < ((tail + maxSize - head) % maxSize)+ head; i++) {

                System.out.printf("%d\t", arr[i % maxSize]);
                System.out.println("");
            }
        }

        private int getHead() {
            if (isEmpty()) {
                System.out.println("队列为空~~");
            }
            return arr[head];
        }
    }
    //测试

    public static void main(String[] args) {
        ArrayQueue q = new CircularQueue().new ArrayQueue(4);
        char c;
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        while (loop) {
            System.out.println("s: 显示队列");
            System.out.println("e: 退出应用");
            System.out.println("a: 元素入队尾");
            System.out.println("g: 从队头取出元素");
            System.out.println("h: 查看队头元素");
            System.out.println("请输入你的操作");
            c = scanner.next().charAt(0);
            switch (c) {
                case 's':
                    q.showElem();

                    break;
                case 'a':
                    try {
                        System.out.println("请输入一个数");
                        int v = scanner.nextInt();

                        q.add(v);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'g':
                    try {
                        int res = q.get();
                        System.out.println("取出了 " + res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res = q.getHead();
                        System.out.println("队头元素 " + res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    loop = false;
                    System.out.println("程序退出~");
                    break;
                default:
                    System.out.println("指令非法,请重新输入正确的指令~");
            }
        }
    }

}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦