精华内容
下载资源
问答
  • 队头删除,队尾插入属性:队头指针front,队尾指针rear方法:入列enQueue,出列deQueue,判断是否为空isEmpty,判断是否已满isFull,清空makeEmpty,返回元素个数size循环队列java代码public class MyQueue{private ...

    队列:先进先出;队头删除,队尾插入

    属性:队头指针front,队尾指针rear

    方法:入列enQueue,出列deQueue,判断是否为空isEmpty,判断是否已满isFull,清空makeEmpty,返回元素个数size

    循环队列java代码

    public class MyQueue{

    private int front = 0,rear = 0;

    private String[] queue;

    public MyQueue(int maxSize){

    queue = new String[maxSize];

    }

    //入列

    public void enQueue(String item){

    if(rear == queue.length && front > 0)

    rear = 0;

    if(!this.isFull())

    queue[rear++] = item;

    }

    //出列

    public void deQueue(){

    if(front == queue.length && rear > 0)

    front = 0;

    if(!this.isEmpty())

    queue[front++] = null;

    }

    //判空

    public boolean isEmpty(){

    if(front == rear){

    return true;

    }else{

    return false;

    }

    }

    //判满

    public boolean isFull(){

    if(front ==( rear + 1)% (queue.length + 1)){

    return true;

    }else{

    return false;

    }

    }

    //返回元素个数

    public int size(){

    if(rear >= front)

    return rear - front;

    else

    return queue.length + 1 - front + rear;

    }

    //清空

    public void makeEmpty(){

    rear = front;

    }

    //验证

    public static void main(String[] args){

    MyQueue mq = new MyQueue(3);

    mq.enQueue("Hello");

    mq.enQueue("World");

    mq.enQueue("!");

    System.out.println("size: "+mq.size());

    System.out.println("full? "+mq.isFull());

    mq.deQueue();

    System.out.println("size: "+mq.size());

    System.out.println("full? "+mq.isFull());

    mq.enQueue("test");

    System.out.println("size: "+mq.size());

    System.out.println("full? "+mq.isFull());

    mq.makeEmpty();

    System.out.println("size: "+mq.size());

    System.out.println("full? "+mq.isFull());

    System.out.println("empty? "+mq.isEmpty());

    }

    }

    展开全文
  • 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_队列Queue

    2016-11-10 10:21:00
    队列:先进先出;队头删除,队尾插入属性:队头指针front,队尾指针rear方法:入列enQueue,出列deQueue,判断是否为空...循环队列java代码 public class MyQueue{private int front = 0,rear = 0;private String...

    队列:先进先出;队头删除,队尾插入
    属性:队头指针front,队尾指针rear
    方法:入列enQueue,出列deQueue,判断是否为空isEmpty,判断是否已满isFull,清空makeEmpty,返回元素个数size

    循环队列java代码

     

    public class MyQueue{
     private int front = 0,rear = 0;
     private String[] queue;

     public MyQueue(int maxSize){
      queue = new String[maxSize];
     }

     //入列
     public void enQueue(String item){
      if(rear == queue.length && front > 0)
       rear = 0;
      if(!this.isFull())
       queue[rear++] = item;
     }

     //出列
     public void deQueue(){
      if(front == queue.length && rear > 0)
       front = 0;
      if(!this.isEmpty())
       queue[front++] = null;
     }

     //判空
     public boolean isEmpty(){
      if(front == rear){
       return true;
      }else{
       return false;
      }
     }

     //判满
     public boolean isFull(){
      if(front ==( rear + 1)% (queue.length + 1)){
       return true;
      }else{
       return false;
      }
     }

     //返回元素个数
     public int size(){
      if(rear >= front)
       return rear - front;
      else
       return queue.length + 1 - front + rear;
     }

     //清空
     public void makeEmpty(){
      rear = front;
     }

     //验证
     public static void main(String[] args){
      MyQueue mq = new MyQueue(3);
      mq.enQueue("Hello");
      mq.enQueue("World");
      mq.enQueue("!");
      System.out.println("size: "+mq.size());
      System.out.println("full? "+mq.isFull());

      mq.deQueue();
      System.out.println("size: "+mq.size());
      System.out.println("full? "+mq.isFull());

      mq.enQueue("test");
      System.out.println("size: "+mq.size());
      System.out.println("full? "+mq.isFull());

      mq.makeEmpty();
      System.out.println("size: "+mq.size());
      System.out.println("full? "+mq.isFull());
      System.out.println("empty? "+mq.isEmpty());
     }

    }

    转载于:https://www.cnblogs.com/cx6872/p/6049905.html

    展开全文
  • 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循环队列

    千次阅读 2017-09-15 15:25:44
    一、JAVA 中已经自带了 Queue、DQueue、ArrayList、LinkedList 等常用的数据结构,为什么还要单独实现循环队列? 之所以使用自定义循环队列,出发点还是基于我们在实际应用中对于数据处理各种各样的需求。使用...
  • 文章目录1、什么是队列2、Queue数据结构实现——基于动态数组2.1、基本函数实现2.2 进出队列函数2.3 查询操作3、Queue数据结构实现——基于链表函数3.1、基本函数实现3.2 进出队列函数3.3 查询操作4、LoopQueue循环...
  • Java循环队列

    千次阅读 2018-01-21 21:36:56
    队列的主要作用是存储数据并且其能保证先进先出,正如排队一样,先进入的先处理 代码 Queue.java ... *循环队列的基本操作 */ public class Queue{ /** * 队头 */ private int front; /** * 队尾 */
  • 3 * 继续学习Java数据结构————队列(列队) 4 * 队列和栈一样,都是使用数组,但是队列多了一个队头,队头访问数据,队尾插入数据 5 * 队列的重要数据特性————先进先出 6 * 入队、出队、队满、队空...
  • 队列 1.队列的实现 // "static void main" must be defined in a public class. class MyQueue { // store elements private List<Integer> data; // a pointer to indicate the start position private...
  • Java 循环队列的实现

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 418
精华内容 167
关键字:

java循环队列queue

java 订阅