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

叁歲伎倆 2023-06-06 10:36 155阅读 0赞

# 队列 #

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

/** * 队列：先入先出，后入后出 * 最多只能入列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;
    
        }
    }

# 测试 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]  
测试代码如下：

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][]

欢迎关注同名公众号：“我就算饿死也不做程序员”。  
交个朋友，一起交流，一起学习，一起进步。![在这里插入图片描述][20200430114340949.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]: /images/20230601/5fe981d373ab41ba96bc67b2dd77de0d.png
[GitHub]: https://github.com/SGyuanshi/DataStructures/tree/master/src/com/hong/queue
[20200430114340949.jpg]: /images/20230601/ef36157b00d14a1f8452a8505681b9bb.png