精华内容
下载资源
问答
  • Java 队列Queue循环队列

    千次阅读 2019-04-04 17:45:14
    队列是一种线性结构。 相比数组,队列对应的操作是数组的子集。 只能从一段(队尾)添加元素,只能从另一端(队首取出元素)。 队列的操作: 队列的实现: 添加元素(入队) : void enqueue(E) 删除...

    队列是一种线性结构。

    相比数组,队列对应的操作是数组的子集。

    只能从一段(队尾)添加元素,只能从另一端(队首取出元素)

     

    队列的操作:

                            

     

    队列的实现:

    添加元素(入队)      : void enqueue(E)
    删除、取出元素(出队)      :  E dequeue()。
    取得队首元素             :E getFront()
    查看队列有多少元素  :int getSize()
    判断队列是否为空      :boolean isEmpty()

    Queue接口:

    public interface Queue<E> {
    
        int getSize();
        boolean isEmpty();
        void enqueue(E e);
        E dequeue();
        E getFront();
    }

    这里我们将复用之前我的一篇文章中讲到的数组类Array,这里就不进行展示了。有兴趣可以了解动态数组的操作:

     

    ArrayQueue:基于Array类实现的队列

    public class ArrayQueue<E> implements Queue<E> {
    
        //创建私有Array对象
        private Array<E> array;
    
        //基于动态数组的实现,传入容量变量
        public ArrayQueue(int capacity){
            //知道要容量为多少,在这里由用户设置
            array = new Array<>(capacity);
        }
    
        public ArrayQueue(){
            //不知道容量为多少
            array = new Array<>();
        }
    
        @Override
        public int getSize(){
            return array.getSize();
        }
    
        @Override
        public boolean isEmpty(){
            return array.isEmpty();
        }
    
        public int getCapacity(){
            return array.getCapacity();
        }
    
        @Override
        public void enqueue(E e){
            //基于动态数组实现的队列,如果容量不足,则会触发动态数组方法进行扩容
            array.addLast(e);
        }
    
        @Override
        public E dequeue(){
            //相应的此操作也会触发减容的操作
            return array.removeFirst();
        }
    
        @Override
        public E getFront(){
            return array.getFirst();
        }
    
        @Override
        public String toString(){
            StringBuilder res = new StringBuilder();
            res.append("Queue: ");
            res.append("front [");
            //遍历array元素,逐次加入队列中
            for(int i = 0 ; i < array.getSize() ; i ++) {
                res.append(array.get(i));
                if(i != array.getSize() - 1) {
                    res.append(", ");
                }
            }
            res.append("] tail");
            return res.toString();
        }
    
        public static void main(String[] args) {
    
            ArrayQueue<Integer> queue = new ArrayQueue<>();
            for(int i = 0 ; i < 10 ; i ++) {
                queue.enqueue(i);
                System.out.println(queue);
                if(i % 3 == 2) {
                    queue.dequeue();
                    System.out.println(queue);
                }
            }
        }
    }
    

    打印结果:

    下面对数组队列的操作,进行复杂度分析:

    取出队列元素时间复杂度为O(n),每取出一个元素,后面的元素都要做相应的位置调整。怎么优化它呢?

    没错,可以利用循环队列的实现。

    当队列为空时,front和tail指向同一个地方。

    当插入一个元素时:只需要维护tail这个位置

    当出队一个元素时:只需要改变front的位置即可

    当tail加满了怎么办?

    此时可以把此数组队列看成一个环行结构。7位置紧接着0这个位置,两个位置是相连的,也就是环形结构。

    那么当tail插入满了的时候,就可以重新利用前面取出的空间进行下面的操作了。

    tail的计算公式:tail =(当前的索引+1)% (整个数组的长度)

    当再入队一个元素时:

    tail则继续 +1即可。

    此时有一个空出来的位置,那么此位置下还能入队一个元素吗?

    答案是不能,队列满的设计是:   

    前面已经给出了队列空的设计:

    如果再加入一个元素,则会与我们前面的设计产生矛盾。其实整个设计操作,就和时钟一样。

     

    循环队列的实现:LoopQueue

    此时不再复用之前实现的动态数组,这里将重新进行逻辑设计:

    public class LoopQueue<E> implements Queue<E> {
    
        //定义一个数组
        private E[] data;
        //定义用于描述队首,队尾的变量
        private int front, tail;
        //定义成员变量,描述队列有多少个元素
        private int size;   
    
        //用户希望数组队列要传入多少元素
        public LoopQueue(int capacity){
            //capacity + 1:队列需要空出一个位置
            data = (E[])new Object[capacity + 1];
            //空队列初始化成员变量
            front = 0;
            tail = 0;
            size = 0;
        }
    
        //用户不知道要设置队列容量为多少时,新建队列默认容量为10
        public LoopQueue(){
            this(10);
        }
    
        //获取队列有多少个元素的个数
        public int getCapacity(){
            return data.length - 1;
        }
    
        @Override
        public boolean isEmpty(){
            return front == tail;
        }
    
        @Override
        public int getSize(){
            return size;
        }
    
        //入队
        @Override
        public void enqueue(E e){
            //根据设计要求,判断队列是否满了
            if((tail + 1) % data.length == front) {
                //扩容
                resize(getCapacity() * 2);
            }
            //存放元素
            data[tail] = e;
            //当存放元素后,需要设置循环队列tail
            tail = (tail + 1) % data.length;
            size ++;
        }
    
        //出队
        @Override
        public E dequeue(){
    
            if(isEmpty()) {
                throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
            }
            // 出队元素为当前队首元素
            E ret = data[front];
            data[front] = null;
            front = (front + 1) % data.length;
            size --;
            if(size == getCapacity() / 4 && getCapacity() / 2 != 0) {
                //缩容
                resize(getCapacity() / 2);
            }    
            return ret;
        }
    
        //取得队首元素
        @Override
        public E getFront(){
            if(isEmpty()) {
                throw new IllegalArgumentException("Queue is empty.");
            }     
            return data[front];
        }
    
        //扩容
        private void resize(int newCapacity){
            //创建新数组队列
            E[] newData = (E[])new Object[newCapacity + 1];
            for(int i = 0 ; i < size ; i ++) {
                //把旧队列元素放入新队列空间
                //偏移位置量:front
                newData[i] = data[(i + front) % data.length];
            }
            data = newData;
            front = 0;
            //扩容不影响原队列的队首、队尾的位置
            tail = size;
        }
    
        //打印队列
        @Override
        public String toString(){
            
            StringBuilder res = new StringBuilder();
            res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
            res.append("front [");
            //由于是循环操作,所以tail值可能比front小
            for(int i = front ; i != tail ; i = (i + 1) % data.length){
                res.append(data[i]);
                //判断是否为队列最后一个元素
                if((i + 1) % data.length != tail) {
                    res.append(", ");
                }
            }
            res.append("] tail");
            return res.toString();
        }
    
        public static void main(String[] args){
    
            LoopQueue<Integer> queue = new LoopQueue<>();
            for(int i = 0 ; i < 10 ; i ++) {
                queue.enqueue(i);
                System.out.println(queue);
    
                if(i % 3 == 2) {
                    queue.dequeue();
                    System.out.println(queue);
                }
            }
        }
    }

    打印结果:

    Queue: size = 1 , capacity = 10
    front [0] tail
    Queue: size = 2 , capacity = 10
    front [0, 1] tail
    Queue: size = 3 , capacity = 10
    front [0, 1, 2] tail
    Queue: size = 2 , capacity = 5
    front [1, 2] tail
    Queue: size = 3 , capacity = 5
    front [1, 2, 3] tail
    Queue: size = 4 , capacity = 5
    front [1, 2, 3, 4] tail
    Queue: size = 5 , capacity = 5
    front [1, 2, 3, 4, 5] tail
    Queue: size = 4 , capacity = 5
    front [2, 3, 4, 5] tail
    Queue: size = 5 , capacity = 5
    front [2, 3, 4, 5, 6] tail
    Queue: size = 6 , capacity = 10
    front [2, 3, 4, 5, 6, 7] tail
    Queue: size = 7 , capacity = 10
    front [2, 3, 4, 5, 6, 7, 8] tail
    Queue: size = 6 , capacity = 10
    front [3, 4, 5, 6, 7, 8] tail
    Queue: size = 7 , capacity = 10
    front [3, 4, 5, 6, 7, 8, 9] tail

    下面对循环队列做时间复杂度分析:

    虽然循环队列的实现比较复杂,不过相比性能考虑,是值得这么做的。

     

    下面对数组队列及循环队列的性能进行对比:

    import java.util.Random;
    
    public class Main {
    
        // 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间,单位:秒
        private static double testQueue(Queue<Integer> q, int opCount){
    
            long startTime = System.nanoTime();
          
            Random random = new Random();
            //入队
            for(int i = 0 ; i < opCount ; i ++) {
                q.enqueue(random.nextInt(Integer.MAX_VALUE));
    		}	
            //出队
            for(int i = 0 ; i < opCount ; i ++) {
                q.dequeue();
            }
            long endTime = System.nanoTime();
    
            return (endTime - startTime) / 1000000000.0;
        }
    
        public static void main(String[] args) {
    
            int opCount = 100000;
            //数组队列
            ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
            double time1 = testQueue(arrayQueue, opCount);
            System.out.println("ArrayQueue, time: " + time1 + " s");
            //循环队列
            LoopQueue<Integer> loopQueue = new LoopQueue<>();
            double time2 = testQueue(loopQueue, opCount);
            System.out.println("LoopQueue, time: " + time2 + " s");
        }
    }
    

     

    结果:

    忽略硬件与JVM版本的影响。知道了队列的具体实现,之后,我需要知道队列其实对于队首可以多种定义,根据队列的应用场景的不同而定义。队列还分广义的队列,我实现的只是普通的队列,不过对于这种普通队列的实现,在应用算法的时候,有它重要的用处,例如广度优先遍历的应用,后续将会对广度优先遍历做进一步探究。

    展开全文
  • JAVA循环队列

    千次阅读 2017-09-15 15:25:44
    一、JAVA 中已经自带了 Queue、DQueue、ArrayList、LinkedList 等常用的数据结构,为什么还要单独实现循环队列? 之所以使用自定义循环队列,出发点还是基于我们在实际应用中对于数据处理各种各样的需求。使用...

    关于自定义循环队列的实现原理和要点可以参见之前的博文系列:循环队列及C语言实现。这里主要对JAVA下的具体实现方式与原理进行说明。

    一、JAVA 中已经自带了 Queue、DQueue、ArrayList、LinkedList 等常用的数据结构,为什么还要单独实现循环队列?

    之所以使用自定义循环队列,出发点还是基于我们在实际应用中对于数据处理各种各样的需求。使用自定义数据结构的好处就在于可以更加灵活的处理各种数据,增加自己需要的接口。然而弊端就是你的 code 可能会引入各种未知的 Bug。所以,在满足我们使用前提的场景下,使用上述已有数据结构等是比较推荐的,如果满足不了实际项目需求,再通过自定义的方式等实现是我们理想的一种选择。

    二、什么场景需要使用自定义循环队列?

    对于数据的处理要求比较灵活,比如:我们需要开发一个安卓服务器程序,需要不断处理每个客户端的请求以及完成与客户端的交互。发送来的数据需要及时处理,但同时数据以自定义格式进行传输:包头+长度+数据+包尾+校验。如上格式,服务器端需要不断将接收的数据进行缓存与解析,如果未满一帧那么需要缓存到下次数据接收过来再进行解析。这时,我们需要批量从队列读取数据以及如果一帧数据不完全,将读取的数据复原到队列中(更改队列当前读位置)的功能。此时,就可以考虑自己实现队列满足这些特殊的需求。

    三、循环队列的特点与要素

    1、先进先出(FIFO);

    2、队列首尾元素位置;

    3、常用队列操作:初始化、销毁、遍历、读写等;

    四、源码实现

    为便于使用,这里将该循环队列以类的方式实现:

    /*
     * Copyright (c) 2017, SoldierJazz. All rights reserved.
     * Use is subject to license terms.
     *
     */
    
    package com.exmple.java.text;
    
    /**
     * DataQueue 类实现为FIFO循环队列
     *
     * <p> 使用前需要根据实际需求为队列分配合理的队列空间大小
     *
     * 创建一个4K空间的队列如下所示:
     *
     * DataQueue mdataqueue= new DataQueue(4096);
     *
     * <p> 更多使用信息可以参考引用该类的例程,有关问题,可发送到
     * SoldierJazz@163.com 寻求支持。
     *
     * @author      SoldierJazz
     * @version	 1.0.0
     */
    
    public class DataQueue {
    	
    	Queue q = null;
    	
    	public class Queue {
    		byte[] data = null;
    		int read;
    		int write;
    		int size;
    		int space;
    	}
    	
    	Object mSemaphore = new Object();
    	
    	DataQueue(int size) {
    		q = new Queue();
    		Queue_Init(q, size);
    	}
    	
        /**
         * 返回当前队列可用数据量
         *
         * @param    q    目标队列
         *
         */
    	int Avail(Queue q) {
    		return q.size - q.space;
    	}
    	
        /**
         * 初始化队列
         *
         * @param    q    目标队列
         * 
         * @param    size    队列分配内存大小
         *
         */
    	void Queue_Init(Queue q, int size) {
    		synchronized (mSemaphore) {
    			q.data = new byte[size];
    			q.read = 0;
    			q.write = 0;
    			q.size = size;
    			q.space = size;
    		}
    	}
    	
        /**
         * 销毁队列
         *
         * @param    q    目标队列
         *
         */
    	void Queue_Destroy(Queue q) {
    		synchronized (mSemaphore) {
    		    q.read = q.write = 0;
    		    q.space = q.size;
    		}
    	}
    
        /**
         * 判断当前队列是否为空
         *
         * @param    q    目标队列
         *
         * @return    true表示队列为空<br>false表示队列不为空
         *
         */
    	boolean Queue_Empty(Queue q) {
    	    return (q.space == q.size);
    	}
    	
        /**
         * 判断当前队列是否已满
         *
         * @param    q    目标队列
         *
         * @return    true表示队列已满<br>false表示队列未满
         *
         */
    	boolean Queue_Full(Queue q) {
    	    return (q.space == 0);
    	}
    	
        /**
         * 写一个byte到目标队列
         *
         * @param    q    目标队列
         * 
         * @param    val    写入的byte值
         *
         * @return    true表示写入成功<br>false表示写入失败
         *
         */
    	boolean AddQueue(Queue q, byte val) {
    	    if (!Queue_Full(q)) {
    	        q.data[q.write] = val;
    	        q.write = (q.write + 1) % q.size;
    	        q.space--;
    	        return true;
    	    } 
    	    return false;
    	}
    	
        /**
         * 从队列中读取一个字节
         *
         * @param    q    目标队列
         * 
         * @param    data    读取的字节
         *
         * @return    true表示读取成功<br>false表示读取失败
         *
         */
    	boolean DelQueue(Queue q, Byte data) {
    	    if (!Queue_Empty(q)) {
    	        data = q.data[q.read];
    	        
    	        q.read = (q.read + 1) % q.size;
    	        q.space++;
    	        return true;
    	    }
    	    return false;
    	}
    	
        /**
         * 批量写入长度为len的字节到队列
         *
         * @param    q    目标队列
         * 
         * @param    data    写入的byte数组
         * 
         * @param    len    写入的数组长度
         *
         * @return    成功写入的字节数量
         *
         */
    	int WriteQueue(Queue q, byte[] data, int len)
    	{
    	    int ret = 0;
    	    int rest = q.size - q.write;
    
    	    synchronized (mSemaphore) {
    		    if (!Queue_Full(q)) {
    		        if (q.space >= len) {
    		            ret = len;
    		            if (rest >= len) {
    		                System.arraycopy(data, 0, q.data, q.write, len);
    		                q.write = (q.write + len) % q.size;
    		                q.space -= len;
    		            } else {
    		                System.arraycopy(data, 0, q.data, q.write, rest);
    		                q.write = 0;
    		                System.arraycopy(data, rest, q.data, 0, len - rest);
    		                q.write = len -rest;
    		                q.space -= len;
    		            }
    		        } else {
    		            ret = q.space;
    		            if (rest >= q.space) {
    		                System.arraycopy(data, 0, q.data, q.write, q.space);
    		                q.write = (q.write + q.space) % q.size;
    		                q.space = 0;
    		            } else {
    		                System.arraycopy(data, 0, q.data, q.write, rest);
    		                q.write = 0;
    		                System.arraycopy(data, rest, q.data, 0, q.space - rest);
    		                q.write = q.space -rest;
    		                q.space = 0;
    		            }
    		        }   
    		    }
    		    return ret;
    	    }
    	}
    	
        /**
         * 从队列中恢复长度len个字节的数据
         *
         * @param    q    目标队列
         * 
         * @param    len    要恢复的长度
         *
         * @return    成功恢复的字节数
         *
         */
    	int RecoverReadQueue(Queue q, int len) {
    	    int ret = 0;
    	    int rest = q.read;
    
    	    synchronized (mSemaphore) {
    	    	
    	    	if (q.space >= len)
    	    		ret = len;
    	    	else
    	    		ret = q.space;
    	    	
    		    if (rest >= ret) {
    		        q.read -= ret;
    		    } else {
    		        q.read = q.size - (ret - rest);
    		    }
    		    q.space -= ret;
    	
    		    return ret;
    	    }
    	}
    	
        /**
         * 从队列中读取len个字节数据到data数组中
         *
         * @param    q    目标队列
         * 
         * @param    data    用于存放数据的目标数组
         * 
         * @param    start    拷贝至目标数组的起始位置
         * 
         * @param    len    读取的长度
         * 
         * @return    成功读取的字节数
         *
         */
    	int ReadQueue(Queue q, byte[] data, int start, int len) {
    	    int rest = q.size - q.read;
    	    int ret = 0;
    
    	    synchronized (mSemaphore) {
    		    if (!Queue_Empty(q)) {
    		        if (Avail(q) >= len) {
    		            ret = len;
    		            if (rest >= len) {
    		                System.arraycopy(q.data, q.read, data, start, len);
    		                q.read = (q.read + len) % q.size;
    		                q.space += len;
    		            } else {
    		                System.arraycopy(q.data, q.read, data, start, rest);
    		                q.read = 0;
    		                System.arraycopy(q.data, 0, data, start + rest, len - rest);
    		                q.read = len -rest;
    		                q.space += len;
    		            }
    		            return len;
    		        } else {
    		            ret = Avail(q);
    		            if (rest >= Avail(q)) {
    		                System.arraycopy(q.data, q.read, data, start, Avail(q));
    		                q.read = (q.read + Avail(q)) % q.size;
    		                q.space = q.size;
    		            } else {
    		                System.arraycopy(q.data, q.read, data, start, rest);
    		                q.read = 0;
    		                System.arraycopy(q.data, 0, data, start + rest, Avail(q) - rest);
    		                q.read = Avail(q) -rest;
    		                q.space = q.size;
    		            }
    		        }
    		    } 
    		    return ret;
    	    }
    	}
    }
    以上内容为使用该类及相关方法的定义,比较简单,看注解即可。下面针对该类做一个使用与测试程序:

    	public void TestDataQueue() {
    		DataQueue dataq = new DataQueue(100);
    		byte[] a1 = {1, 2, 3, 4, 5, 6};
    		byte[] a2 = {7, 8, 9, 10};
    		byte[] b = new byte[10];
    		int nread = 0;
    		dataq.WriteQueue(dataq.q, a1, a1.length);
    		nread = dataq.ReadQueue(dataq.q, b, 0, 3);
    		System.out.println("length of queue: " + dataq.Avail(dataq.q));
    		for (int i = 0; i < nread; i++) {
    			System.out.printf("byte[%d]: %d\n", i, b[i]);
    		}
    		dataq.WriteQueue(dataq.q, a2, a2.length);
    		System.out.println("length of queue: " + dataq.Avail(dataq.q));
    		nread = dataq.ReadQueue(dataq.q, b, 0, dataq.Avail(dataq.q));
    		System.out.println("length of queue: " + dataq.Avail(dataq.q));
    		for (int i = 0; i < nread; i++) {
    			System.out.printf("byte[%d]: %d\n", i, b[i]);
    		}
    	}
    	
    	public static void main(String args[]) {
    		test t = new test();
    		t.TestDataQueue();
    	}
    运行结果如下所示:



    有疑问或者问题就给我邮件或者评论吧,觉得有用就点赞吧~:-D



    展开全文
  • java 队列总结queue v3 svv.docxjava 队列总结queue v3 svv.docx atitit....2.1. 顺序队列 vs 循环队列 2 2.2. 阻塞队列和非阻塞队列 2 2.3. 单端队列 vs 双端队列 2 3. 队列的基本运算 入...

    java 队列总结queue v3 svv.docxjava 队列总结queue v3 svv.docx  atitit. java queue 队列体系总结o7t

    1. 队列概念 1

    1.1. 队列的实现 数组vs链表 1

    2. 队列分类 2

    2.1. 顺序队列 vs 循环队列 2

    2.2. 阻塞队列和非阻塞队列 2

    2.3. 单端队列 vs 双端队列 2

    3. 队列的基本运算 入队 出队 读队头 判队空 2

    4. 常见的返回模式  可能报异常 返回布尔值 可能阻塞 3

    5. java.util.Queue接口, 3

    5.1. BlockingQueue 3

    5.2. deque 即双端队列 3

    5.2.1. BlockingDeque接口 4

    6. ConcurrentLinkedQueue implements Queue 4

    7. BlockingQueue阻塞队列 4

    7.1. 1. ArrayBlockingQueue 5

    7.2. 2. LinkedBlockingQueue 5

    7.3. 3. DelayQueue 5

    7.4. 4. PriorityBlockingQueue 5

    7.5. SynchronousQueue 6

    8. LinkedBlockingDeque 乃阻塞双端队列 6

    9. 参考 6

     

     

    1. 队列概念

    队列

     

    (常用数据结构之一)

     锁定

    本词条由“科普中国”科学百科词条编写与应用工作项目 审核 。

    队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

     

      1. 队列的实现 数组vs链表

     

    1. 队列分
      1. 顺序队列 vs 循环队列
      2. 阻塞队列和非阻塞队列

    多数生产消费模型的首选数据结构就是队列。Java提供的线程安全的Queue可以分为阻塞队列和非阻塞队列,其中阻塞队列的典型例子是BlockingQueue,非阻塞队列的典型例子是ConcurrentLinkedQueue,在实际应用中要根据实际需要选用阻塞队列或者非阻塞队列。

    同步是阻塞模式,异步是非阻塞模式 

     

    .阻塞队列和非阻塞队列的区别:阻塞队列可以阻塞,非阻塞队列不能阻塞,只能使用队列wait(),notify()进行队列消息传送。而阻塞队列当队列里面没有值时,会阻塞直到有值输入。输入也一样,当队列满的时候,会阻塞,直到队列不为空。

     

      1. 单端队列 vs 双端队列

     

    作者:: 老哇的爪子 Attilax 艾龙,  EMAIL:1466519819@qq.com

    转载请注明来源: http://blog.csdn.net/attilax

     

     

    1. 队列的基本运算 入队 出队 读队头 判队空

    (1)初始化队列:Init_Queue(q) ,初始条件:队q 不存在。操作结果:构造了一个空队;

    (2)入队操作: In_Queue(q,x),初始条件: 队q 存在。操作结果: 对已存在的队列q,插入一个元素x 到队尾,队发生变化;

    (3)出队操作: Out_Queue(q,x),初始条件: 队q 存在且非空,操作结果: 删除队首元素,并返回其值,队发生变化;

    (4)读队头元素:Front_Queue(q,x),初始条件: 队q 存在且非空,操作结果: 读队头元素,并返回其值,队不变;

    (5)判队空操作:Empty_Queue(q),初始条件: 队q 存在,操作结果: 若q 为空队则返回为1,否则返回为0。 [

     

    1. 常见的返回模式  可能报异常 返回布尔值 可能阻塞

     

    1.  java.util.Queue接口,

     

       在java5中新增加了java.util.Queue接口,

     

    用以支持队列的常见操作。该接口扩展了java.util.Collection接口。
    Queue使用时要尽量避免Collection的add()和remove()方法,而是要使用offer()来加入元素,使用poll()来获取并移出元素。它们的优
    点是通过返回值可以判断成功与否,add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素,使用
    element()或者peek()方法。
    值得注意的是LinkedList类实现了Queue接口,因此我们可以把LinkedList当成Queue来用。

     

    继承体系

     Queue<E> extends Collection<E> extends Iterable<E>

      1. BlockingQueue
      2.  deque 即双端队列

    deque 即双端队列。是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行

     

        1. BlockingDeque接口

     

    1. ConcurrentLinkedQueue implements Queue

    ConcurrentLinkedQueue<E> extends AbstractQueue<E> implements Queue<E>

    1. BlockingQueue阻塞队列

    BlockingQueue不光实现了一个完整队列所具有的基本功能,同时在多线程环境下,他还自动管理了多线间的自动等待于唤醒功能,从而使得程序员可以忽略这些细节,关注更高级的功能。

    阻塞实现通常使用加锁上实现...

    常见BlockingQueue


    在了解了BlockingQueue的基本功能后,让我们来看看BlockingQueue家庭大致有哪些成员?

     

    首先,看看BlockingQueue提供的常用方法:
     

    可能报异常

    返回布尔值

    可能阻塞

    设定等待时间

    入队

    add(e)

    offer(e)

    put(e)

    offer(e, timeout, unit)

    出队

    remove()

    poll()

    take()

    poll(timeout, unit)

    查看

    element()

    peek()


    • 从上表可以很明显看出每个方法的作用,这个不用多说。我想说的是: add(e) remove() element() 方法不会阻塞线程。当不满足约束条件时,会抛出IllegalStateException 异常。例如:当队列被元素填满后,再调用add(e),则会抛出异常。
    • offer(e) poll() peek() 方法即不会阻塞线程,也不会抛出异常。例如:当队列被元素填满后,再调用offer(e),则不会插入元素,函数返回false。
    • 要想要实现阻塞功能,需要调用put(e) take() 方法。当不满足约束条件时,会阻塞线程。



    BlockingQueue成员详细介绍

      1. 1. ArrayBlockingQueue
      2. 2. LinkedBlockingQueue

    基于链表的阻塞队列

      1. 3. DelayQueue

    DelayQueue中的元素只有当其指定的延迟时间到了,才能够从队列中获取到该元素

      1. 4. PriorityBlockingQueue

    基于优先级的阻塞队列(优先级的判断通过构造 函数传入的Compator对象来决定),但需要注意的是PriorityBlockingQueue并不会阻塞数据生产者,而只会在没有可消费的数据 时,阻塞数据的消费者。因此使用的时候要特别注意,生产者生产数据的速度绝对不能快于消费者消费数据的速度,否则时间一长,会最终耗尽所有的可用堆内存空 间。在实现PriorityBlockingQueue时,内部控制线程同步的锁采用的是公平锁。

      1. SynchronousQueue
    1. LinkedBlockingDeque 乃阻塞双端队列 

    ArrayDeque 双向队列
    LinkedBlockingDeque 阻塞双端队列
    ArrayBlockingQueue 双向并发阻塞队列
    LinkedBlockingQueue FIFO队列
    ConcurrentLinkedQueue 基于链接节点的无界线程安全队列
    PriorityBlockingQueue 带优先级的无界阻塞队列
    还有很多很多,可以看看AbstractQueue, Deque有哪些实现类。

    1. 参考

    java中线程队列BlockingQueue的用法-shwenwen-ITPUB博客.htm

    Java并发包中的同步队列SynchronousQueue实现原理 _ 并发编程网 - ifeve.com.htm

    Java多线程总结之线程安全队列Queue - 火木棉的日志 - 网易博客.htm

    展开全文
  • Java队列Queue详情

    2019-04-19 11:19:17
    Queue: 基本上,一个队列就是一个先入先出(FIFO)的数据结构 Queue接口与List、Set同一...没有实现阻塞接口的LinkedList: 实现了java.util.Queue接口和java.util.AbstractQueue接口  内置的不阻塞队列: Prio...
    • Queue: 基本上,一个队列就是一个先入先出(FIFO)的数据结构

    • Queue接口与List、Set同一级别,都是继承了Collection接口。LinkedList实现了Deque接 口。

    • Queue的实现

    1. 没有实现阻塞接口的LinkedList: 实现了java.util.Queue接口和java.util.AbstractQueue接口
        内置的不阻塞队列: PriorityQueue 和 ConcurrentLinkedQueue
        PriorityQueue 和 ConcurrentLinkedQueue 类在 Collection Framework 中加入两个具体集合实现。
        PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序(通过其 java.util.Comparable 实现)或者根据传递给构造函数的 java.util.Comparator 实现来定位。
        ConcurrentLinkedQueue 是基于链接节点的、线程安全的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们,所以只要不需要知道队列的大 小,       ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢,需要遍历队列。

    2. 实现阻塞接口的:
        java.util.concurrent 中加入了 BlockingQueue 接口和五个阻塞队列类。它实质上就是一种带有一点扭曲的 FIFO 数据结构。不是立即从队列中添加或者删除元素,线程执行操作阻塞,直到有空间或者元素可用。

    • 五个队列所提供的各有不同:
        * ArrayBlockingQueue :一个由数组支持的有界队列。
        * LinkedBlockingQueue :一个由链接节点支持的可选有界队列。
        * PriorityBlockingQueue :一个由优先级堆支持的无界优先级队列。
        * DelayQueue :一个由优先级堆支持的、基于时间的调度队列。
        * SynchronousQueue :一个利用 BlockingQueue 接口的简单聚集(rendezvous)机制。
        
      Collection接口示意图

    下表显示了jdk1.5中的阻塞队列的操作:

    方法名称作用情况
    add增加一个元索left-aligned 如果队列已满,则抛出一个IIIegaISlabEepeplian异常
    remove移除并返回队列头部的元素如果队列为空,则抛出一个NoSuchElementException异常
    element返回队列头部的元素如果队列为空,则抛出一个NoSuchElementException异常
    offer添加一个元素并返回true如果队列已满,则返回false
    poll移除并返问队列头部的元素如果队列为空,则返回null
    peek返回队列头部的元素如果队列为空,则返回null
    put添加一个元素如果队列满,则阻塞
    take移除并返回队列头部的元素如果队列为空,则阻塞

    remove、element、offer 、poll、peek 其实是属于Queue接口。

    阻塞队列的操作可以根据它们的响应方式分为以下三类:
      aad、remove和element操作在你试图为一个已满的队列增加元素或从空队列取得元素时 抛出异常。当然,在多线程程序中,队列在任何时间都可能变成满的或空的,所以你可能想使用offer、poll、peek方法。这些方法在无法完成任务时 只是给出一个出错示而不会抛出异常。

    注意:poll和peek方法出错进返回null。因此,向队列中插入null值是不合法的

    最后,我们有阻塞操作put和take。put方法在队列满时阻塞,take方法在队列空时阻塞。

    LinkedBlockingQueue的容量是没有上限的(说的不准确,在不指定时容量为Integer.MAX_VALUE,不要然的话在put时怎么会受阻呢),但是也可以选择指定其最大容量,它是基于链表的队列,此队列按 FIFO(先进先出)排序元素。

    ArrayBlockingQueue在构造时需要指定容量, 并可以选择是否需要公平性,如果公平参数被设置true,等待时间最长的线程会优先得到处理(其实就是通过将ReentrantLock设置为true来 达到这种公平性的:即等待时间最长的线程会先操作)。通常,公平性会使你在性能上付出代价,只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队 列,此队列按 FIFO(先进先出)原则对元素进行排序。

    PriorityBlockingQueue是一个带优先级的 队列,而不是先进先出队列。元素按优先级顺序被移除,该队列也没有上限(看了一下源码,PriorityBlockingQueue是对 PriorityQueue的再次包装,是基于堆数据结构的,而PriorityQueue是没有容量限制的,与ArrayList一样,所以在优先阻塞 队列上put时是不会受阻的。虽然此队列逻辑上是无界的,但是由于资源被耗尽,所以试图执行添加操作可能会导致 OutOfMemoryError),但是如果队列为空,那么取元素的操作take就会阻塞,所以它的检索操作take是受阻的。另外,往入该队列中的元 素要具有比较能力。

    DelayQueue(基于PriorityQueue来实现的)是一个存放Delayed 元素的无界阻塞队列,只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的 Delayed 元素。如果延迟都还没有期满,则队列没有头部,并且poll将返回null。当一个元素的 getDelay(TimeUnit.NANOSECONDS) 方法返回一个小于或等于零的值时,则出现期满,poll就以移除这个元素了。此队列不允许使用 null 元素。

    在这里插入图片描述

    代码用例:

    package com.yao;
    import java.util.concurrent.ArrayBlockingQueue;
    import java.util.concurrent.BlockingQueue;
    import java.util.concurrent.ExecutorService;
    import java.util.concurrent.Executors;
    public class BlockingQueueTest {
     /**
     定义装苹果的篮子
      */
     public static class Basket{
      // 篮子,能够容纳3个苹果
      BlockingQueue<String> basket = new ArrayBlockingQueue<String>(3);
    
      // 生产苹果,放入篮子
      public void produce() throws InterruptedException{
       // put方法放入一个苹果,若basket满了,等到basket有位置
       basket.put("An apple");
      }
      // 消费苹果,从篮子中取走
      public String consume() throws InterruptedException{
       // get方法取出一个苹果,若basket为空,等到basket有苹果为止
       String apple = basket.take();
       return apple;
      }
    
      public int getAppleNumber(){
       return basket.size();
      }
    
     }
     // 测试方法
     public static void testBasket() {
      // 建立一个装苹果的篮子
      final Basket basket = new Basket();
      // 定义苹果生产者
      class Producer implements Runnable {
       public void run() {
        try {
         while (true) {
          // 生产苹果
          System.out.println("生产者准备生产苹果:" 
            + System.currentTimeMillis());
          basket.produce();
          System.out.println("生产者生产苹果完毕:" 
            + System.currentTimeMillis());
          System.out.println("生产完后有苹果:"+basket.getAppleNumber()+"个");
          // 休眠300ms
          Thread.sleep(300);
         }
        } catch (InterruptedException ex) {
        }
       }
      }
      // 定义苹果消费者
      class Consumer implements Runnable {
       public void run() {
        try {
         while (true) {
          // 消费苹果
          System.out.println("消费者准备消费苹果:" 
            + System.currentTimeMillis());
          basket.consume();
          System.out.println("消费者消费苹果完毕:" 
            + System.currentTimeMillis());
          System.out.println("消费完后有苹果:"+basket.getAppleNumber()+"个");
          // 休眠1000ms
          Thread.sleep(1000);
         }
        } catch (InterruptedException ex) {
        }
       }
      }
    
      ExecutorService service = Executors.newCachedThreadPool();
      Producer producer = new Producer();
      Consumer consumer = new Consumer();
      service.submit(producer);
      service.submit(consumer);
      // 程序运行10s后,所有任务停止
      try {
       Thread.sleep(10000);
      } catch (InterruptedException e) {
      }
      service.shutdownNow();
     }
     public static void main(String[] args) {
      BlockingQueueTest.testBasket();
     }
    }
    

    本文引自:低调人生

    展开全文
  • java队列queue

    千次阅读 2015-11-09 22:42:32
    Java多线程总结之线程安全队列QueueJava多线程应用中,队列的使用率很高,多数生产消费模型的首选数据结构就是队列。Java提供的线程安全的Queue可以分为阻塞队列和非阻塞队列,其中阻塞队列的典型例子是...
  • Java中的队列Queue

    2021-01-12 11:00:31
    我们都知道队列(Queue)是一种先进先出(FIFO)的数据结构,Java中定义了java.util.Queue接口用来表示队列Java中的Queue与List、Set属于同一个级别接口,它们都是继承于Collection接口。 Java中还定义了一种双端队列...
  • 设一循环队列Queue,只有头指针front,不设尾指针,另设一个内含元素个数的计数器,试写出相应的进队、出队算法。
  • Java循环队列

    千次阅读 2018-01-21 21:36:56
    队列的主要作用是存储数据并且其能保证先进先出,正如排队一样,先进入的先处理 代码 Queue.java ... *循环队列的基本操作 */ public class Queue{ /** * 队头 */ private int front; /** * 队尾 */
  • Java线程安全队列Queue

    千次阅读 2017-06-05 17:06:12
    Java提供的线程安全的Queue可以分为阻塞队列和非阻塞队列,其中阻塞队列的典型例子是BlockingQueue,非阻塞队列的典型例子是ConcurrentLinkedQueue,在实际应用中要根据实际需要选用阻塞队列或者非阻塞队列。...
  • java队列——queue详细分析

    万次阅读 2018-11-07 10:42:02
    Queue: 基本上,一个队列就是一个先入先出(FIFO)的数据结构 ...1、没有实现的阻塞接口的LinkedList: 实现了java.util.Queue接口和java.util.AbstractQueue接口  内置的不阻塞队列: Prior...
  • 3 * 继续学习Java数据结构————队列(列队) 4 * 队列和栈一样,都是使用数组,但是队列多了一个队头,队头访问数据,队尾插入数据 5 * 队列的重要数据特性————先进先出 6 * 入队、出队、队满、队空...
  • 什么是队列队列是一种线性的数据结构【线性数据结构:数组、栈、队列】 相比数组,队列对应的数据操作是数组的子集。 只能从一端(队尾)添加元素,只能从另一端(队首)取出元素。   数组队列 代码实现 ...
  • Java循环队列的实现

    千次阅读 2018-01-03 10:19:45
    队列是一种特殊的线性表,其特殊性体现在...在实际使用中,由于顺序队列经常会因数组下标越界出现”假溢出“问题,所以除了一些简单应用之外,真正实用的队列是循环队列。 队空状态:  front=rear=0 队满状态: f
  • Java实现循环队列

    2021-06-05 17:30:41
    Java实现循环队列什么是循环队列循环队列操作1.自定义循环队列结构2.队列初始化3.判断队列是否为空4.判断队列长度5.队列入队6.队列出队7.取队头元素QueueDemoTest 什么是循环队列 顺序队列在操作时容易暴露假溢出...
  • Java 循环队列的实现

    千次阅读 2019-06-07 19:03:38
     队列Queue)是限定只能在一端插入、另一端删除的线性表。允许删除的一端叫做队头(front),允许插入的一端叫做队尾(rear),没有元素的队列称为“空队列”。  队列具有先进先出(FIFO)的特性。  普通顺序...
  • java循环队列的实现

    千次阅读 2018-11-15 10:33:05
    * 循环队列 * &amp;lt;p&amp;gt; * 注意:判空和判满的两种情况: * 情况1.另设一个标识位区别队列是空还是满 * 情况2.少用一个元素空间,约定以&quot;队列头指针在队尾指针的下一位位置上&...
  • java实现循环队列

    2020-03-03 16:31:10
    java实现循环队列 public class Queue { int maxcount; //最大长度 int count; //当前长度 Object[] a; int front; //头指针 int rear; //尾指针 public Queue(int size) { //初始化队列 a=new Object[size]...
  • java队列实现(顺序队列、链式队列、循环队列
  • Queue: 基本上,一个队列就是一个先入先出(FIFO)的数据结构 ...1、没有实现的阻塞接口的LinkedList: 实现了java.util.Queue接口和java.util.AbstractQueue接口  内置的不阻塞队列: Prior...
  • 1.什么是队列队列是数据结构中比较重要的一种类型(是一种数据结构),它支持 FIFO,尾部添加、头部删除(先进队列的元素先出队列),跟我们生活中的排队类似。 2.什么情况下使用队列? 一般情况下,如果是...
  • import java.util.Queue; /** * java.util.Queue * 队列 * 队列也可以存放一组元素,但是存放元素必须遵循:先进先出原则。 * @author kaixu * */ public class QueueDemo { public static vo...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 70,825
精华内容 28,330
关键字:

java循环队列queue

java 订阅