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

数据结构:队列的java实现以及优化

程序员文章站 2022-03-31 10:08:13
...

队列

队列是一种先进先出,后进后出的数据结构。
如果用数组的基本数据结构实现的话,普通的队列只能入列的元素数量为数组的大小,不管是否已经出列。

/**
 * 队列:先入先出,后入后出
 * 最多只能入列maxSize个元素,不管是否已经出列
 */
public class Queue {

    private int maxSize; // 队列的最大容量
    private int first = -1; // 第一个成员的index
    private int last = 0; // 最后一个成员的index +1
    private String[] arr;

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

    public String take(){
        if (first+1 == last){
            System.out.println("队列为空,无法出列");
            return null;
        }

        first ++;
        String e = arr[first];
        return e;
    }

    public void add(String e){
        if (last == maxSize){
            System.out.println("队列已满,无法添加");
            return;
        }

        arr[last] = e;
        last ++;
    }
}

环形队列

基于上面说到的普通队列的缺点,我们可以进行优化——环形队列,让队列可以同时存在数组大小的元素数量,不管之前是否已经出列。

/**
 * 环形队列:在队列可以同时存在maxSize个元素,不管之前已经出列了多少元素
 */
public class CycleQueue {

    private int maxSize; // 队列的最大容量
    private int first = -1; // 第一个成员的index
    private int last = 0; // 最后一个成员的index +1
    private String[] arr;

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

    public void add(String e){
        if (last-first == maxSize+1){
            System.out.println("队列已满,无法添加");
            return;
        }

        arr[last%maxSize] = e;
        last ++;
    }

    public String take(){
        if (first == last-1){
            System.out.println("队列为空,无法出列");
            return null;
        }

        first ++;
        String e = arr[first%maxSize];
        return e;

    }
}

测试

数据结构:队列的java实现以及优化
测试代码如下:

public class Test {
    public static void main(String[] args) {
        System.out.println("====普通队列测试");
        queueTest();
        System.out.println("====环形队列测试");
        cycleQueueTest();
    }

    public static void queueTest(){
        Queue queue = new Queue(10);

        queue.add("a");
        queue.add("b");
        queue.add("c");
        System.out.println(queue.take());
        System.out.println(queue.take());
        queue.add("d");
        System.out.println(queue.take());
        System.out.println(queue.take());
    }

    public static void cycleQueueTest(){
        CycleQueue cycleQueue = new CycleQueue(2);
        cycleQueue.add("a");
        cycleQueue.add("b");
        System.out.println(cycleQueue.take());
        System.out.println(cycleQueue.take());
        cycleQueue.add("c");
        cycleQueue.add("d");
        cycleQueue.add("e");
        System.out.println(cycleQueue.take());
        System.out.println(cycleQueue.take());
    }
}

完整代码的已上传至GitHub