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

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

0

1

2

3

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

 

2.环形数组

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

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

3.添加数据

4.取出数据 

5.查看所有数据 

完整代码

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]);
    }
}