欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

JAVA数据结构- 环形数组模拟队列

程序员文章站 2022-06-06 20:56:29
...

1.使用普通数组时,定一个m长度的数组

0 1 2 3

     把数据存入数组满时, 再取出时, 就不能再向这个数组添加数据 ,   因为该数组最后一个位置

 

2.环形数组

 定义第一个数据也就是第一个先添加的数据的位置   first 初始值为0

 定义最后一个添加进来的数据  的后一个位置为     last    初始值为0    所以实际最大容量为 max-1

JAVA数据结构- 环形数组模拟队列

3.添加数据

JAVA数据结构- 环形数组模拟队列

4.取出数据 

JAVA数据结构- 环形数组模拟队列

5.查看所有数据 

JAVA数据结构- 环形数组模拟队列

完整代码

package dataStructure.环形队列;

import java.util.Scanner;

public class CircleArrayQueue {

    public static void main(String[] args) {
        //测试一把
        System.out.println("测试数组模拟环形队列的案例~~~");
        //  创建一个环形队列
        CircleArray queue = new CircleArray(4); //说明设置 4,  其队列的有效数据最大是 3
        char key = ' '; //  接收用户输入
        Scanner scanner = new Scanner(System.in);//
        boolean loop = true;
        //  输出一个菜单
        while (loop) {
            System.out.println("s(show):  显示队列");
            System.out.println("e(exit):  退出程序");
            System.out.println("a(add):  添加数据到队列");
            System.out.println("g(get):  从队列取出数据");
            System.out.println("h(head):  查看队列头的数据");
            key = scanner.next().charAt(0);//  接收一个字符
            switch (key) {
                case 's':
                    queue.show();
                    break;
                case 'a':
                    System.out.println("输出一个数");
                    int value = scanner.nextInt();
                    queue.add(value);
                    break;
                case 'g': //  取出数据
                    try {
                        int res = queue.getOne();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //  查看队列头的数据
                    try {
                        queue.showHead();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e': //  退出
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出~~");
    }


}

class CircleArray {
    private int maxSize;  //定义数组的最大容量,实际最大容量为maxSize-1 因为 last指向最后一个数据的后一个
    private int last;      //定义数组最后一个数据的 后一个数据的位置  初始值为0
    private int first;     //定义数组的第一个数据的位置  初始值为0
    private int arr[];     //存放数据的数组

    public CircleArray(int maxSize) {
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
    }

    /**
     * 判断数组是否为空
     *
     * @return
     */
    public Boolean isEmpty() {
        return last == first;
    }

    /**
     * 判断数组是否满,(last+1)%maxSize就是将指针移到开头,因为是环形的所以取模
     *
     * @return
     */
    public Boolean isFull() {
        return (last + 1) % maxSize == first;
    }

    /**
     * 添加数据,添加的数据在队未
     * @param num
     */
    public void add(int num) {
        if (isFull()) {
            System.out.println("队列满,不能添加~~");
            return;
        }
        arr[last] = num;         //因为last就指向最后一个数据的后一个,所以直接是
        last = (last + 1) % maxSize;   //后移一位,考虑环形
    }

    /**
     * 获得一个数据,获得的数据是队首
     *
     * @return
     */
    public int getOne() {
        if (isEmpty()) {
            throw new RuntimeException("队列空,不能取~~");
        }
        int value = arr[first];
        first = (first + 1) % maxSize;   //后移一位,考虑环形
        return value;
    }

    /**
     * 查看所有数据
     */
    public void show() {
        int length = (last - first + maxSize) % maxSize; //先得到当前数据个数
        //从第一个数开始遍历就是first
        for (int i = first; i < first + length; i++) {
            System.out.printf("array[%d]=%d\n", i, arr[i]);
        }
    }

    public void showHead() {
        if (isEmpty()) {
            throw new RuntimeException("队列空,不能查看~~");
        }
        System.out.printf("队列头的数据是:%d\n", arr[first]);
    }
}