黑马程序员技术交流社区

标题: 【上海校区】java手写队列 [打印本页]

---

作者: 不二晨    时间: 2019-3-22 09:08
标题: 【上海校区】java手写队列
队列也可以用数组来实现，不过这里有个问题，当数组下标满了后就不能再添加了，但是数组前面由于已经删除队列头的数据了，导致空。所以队列我们可以用循环数组来实现，见下面的代码：

package com.cn.test.queue;



public class RoundQueue {
        private long a[];
        private int size; //数组大小
        private int nItems;//实际存储数量
        private int front;//头
        private int rear;//尾
       
        public RoundQueue(int maxSize){
                this.size=maxSize;
                a=new long[size];
                nItems=0;
                front=0;
                rear=-1;
        }
       
        //判断队列是否为空
        public boolean isEmpty(){
                return (nItems==0);
        }
               
        //判断队列是否已满
        public boolean isFull(){
                return (nItems==size);
        }
       
        //队列实际存储数量大小
        public int size(){
                return nItems;
        }
       
        //往队列添加数据
        public void insert(long value){
                if(isFull()){
                        System.out.println("队列已满！");
                        return;
                }
                rear= ++nItems%size;
                a[rear]=value;//尾指针满了就循环到0处,这句相当于下面注释内容   
                nItems++;
                /*if(rear == size-1){
                        rear = -1;
                }
                a[++rear] = value;*/
        }
       
        public long remove(){
                if(isEmpty()){
                        System.out.println("队列为空！");
                        return 0;
                }
                nItems--;
                front =front % size;
                return a[front++];
        }
       
        public long peek(){
                if(isEmpty()){
                        System.out.println("队列为空！");
                        return 0;
                }
                return a[front++];
        }
       
        //打印 队列
        public void display(){
                if(isEmpty()){
                        System.out.println("队列为空！");
                        return;
                }
                int item=front;
                for(int i=0;i<nItems;i++){
                        System.out.println(a[item++ % size]+" ");
                }
                System.out.println(" ");
        }
       
        //测试
    public static void main(String[] args) throws Exception
    {
            RoundQueue roundQueue=new RoundQueue(30);
            roundQueue.insert(3);
            roundQueue.insert(6);
            roundQueue.insert(9);

        System.out.println("打印输出： ");
        roundQueue.display();

        int elem=(int)roundQueue.remove();
        System.out.println("移除队列===： "+elem);
        System.out.println(" ");
        System.out.println("移除队列后打印输出===： ");
        roundQueue.display();

        int elem1=(int)roundQueue.peek();
        System.out.println("移除队列---： "+elem1);
        System.out.println(" ");
        System.out.println("移除队列后打印输出---： ");
        roundQueue.display();
    }
       
       
}

输出结果：




和栈一样，队列中插入数据项和删除数据项的时间复杂度均为O(1)。
---------------------
作者：小志的博客
来源：CSDN
原文：https://blog.csdn.net/li1325169021/article/details/87085693
版权声明：本文为博主原创文章，转载请附上博文链接！

---

作者: 不二晨    时间: 2019-3-25 17:14
奈斯，感谢分享

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2