精华内容
下载资源
问答
  • 1. 队列定义 队列(Queue)是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表。 (1)允许删除的一端称为队头(Front)。 (2)允许插入的一端称为队尾(Rear)... 在Java编程中,Queue的实现都是用L

    1. 队列定义

       队列(Queue)是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表。
    (1)允许删除的一端称为队头(Front)。
    (2)允许插入的一端称为队尾(Rear)。
    (3)当队列中没有元素时称为空队列。
    (4)队列亦称作先进先出(First In First Out)的线性表,简称为FIFO表。
       在Java编程中,Queue的实现都是用LinkedList

    2. 具体分析

    Java中Queue是一个接口,具有以下方法:
    
    操作说明
    boolean add(E e)插入元素到队尾,若超出队列容量抛异常
    boolean offer(E e)插入元素到队尾,若超出队列容量返回false
    E remove()移除队头元素
    E poll()移除队头元素 ,若队列为空返回null
    E element()返回队头元素 ,若队列为空抛异常
    E peek()返回队头元素 ,若队列为空返回null



      Queue的实现类(2大类):

    1. 未实现BlockingQueue接口的不阻塞队列:

      a.LinkedList(实现了java.util.Deque接口)
        Deque接口是Queue接口的子接口,代表一个双端队列。同时Deque不仅可以作为双端队列使用,而且可以被当成栈来使用,所以可以使用出栈,入栈的方法。


      b.PriorityQueue (实现了java.util.AbstractQueue抽象类和java.util.Queue接口)

      PriorityQueue是个基于优先级堆的极大优先级队列。此队列按照在构造时所指定的顺序对元素排序,既可以根据元素的自然顺序来指定排序(参阅 Comparable),也可以根据 Comparator 来指定,这取决于使用哪种构造方法。优先级队列不允许 null 元素。依靠自然排序的优先级队列还不允许插入不可比较的对象(这样做可能导致 ClassCastException)
      源码分析:

        public PriorityQueue (int initialCapacity,Comparator<? super E >comparator){
          if(initialCapacity < 1)
              throw new  IllegalArgumentException();
          this.qurue = new Object [initialCapacity ];
          this.compatator = comparator;   
      }
      public PriorityQueue(Collection<? extends E> c) {
          initFromCollection(c);
          if (c instanceof SortedSet)
              comparator = (Comparator<? super E>)
                  ((SortedSet<? extends E>)c).comparator();
          else if (c instanceof PriorityQueue)
              comparator = (Comparator<? super E>)
                  ((PriorityQueue<? extends E>)c).comparator();
          else {
              comparator = null;
              heapify();
       }
       // 若要转换为PriorityQueue的Collection类必须实现SortedSet接口,此接口主要用于排序操作,即实现此接口的子类都属于排序的子类

      SortedSet接口中定义的方法:

    方法描述
    public Comparator< ? super E>comparator()返回与排序有关联的比较器
    public E first()返回集合中的第一个元素
    public SortedSet< E > headset(E toElement)返回从开始到指定元素的集合
    public E last()返回最后一个元素
    public SortedSet< E > subSet(E fromElement,E toElement)返回指定对象间的元素
    public SortedSet< E> tailSet(E fromElement)从指定元素到最后



    PriorityQueue深入解析:
    http://blog.csdn.net/kobejayandy/article/details/46832797


    c.ConcurrentLinkedQueue(实现了java.util.AbstractQueue抽象类和java.util.Queue接口)

         2.实现阻塞接口的队列:

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

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

        前 两个类 ArrayBlockingQueue 和 LinkedBlockingQueue 几乎相同,只是在后备存储器方面有所不同, LinkedBlockingQueue 并不总是有容量界限。无大小界限的 LinkedBlockingQueue 类在添加元素时永远不会有阻塞队列的等待(至少在其中有Integer.MAX_VALUE 元素之前不会)。
    PriorityBlockingQueue 是具有无界限容量的队列,它利用所包含元素的 Comparable 排序顺序来以逻辑顺序维护元素。可以将它看作 TreeSet 的可能替代物。不过对 PriorityBlockingQueue 有一个技巧。从 iterator() 返回的 Iterator 实例不需要以优先级顺序返回元素。如果必须以优先级顺序遍历所有元素,那么让它们都通过 toArray() 方法并自己对它们排序,像 Arrays.sort(pq.toArray())。
    新的 DelayQueue 实现可能是其中最有意思(也是最复杂)的一个。加入到队列中的元素必须实现新的 Delayed 接口(只有一个方法 —— long getDelay(java.util.concurrent.TimeUnit unit) )。因为队列的大小没有界限,使得添加可以立即返回,但是在延迟时间过去之前不能从队列中取出元素。如果多个元素完成了延迟,那么最早失效/失效时间最长 的元素将第一个取出。实际上没有听上去这样复杂。
        SynchronousQueue 类是最简单的。它没有内部容量。它就像线程之间的手递手机制。在队列中加入一个元素的生产者会等待另一个线程的消费者。当这个消费者出现时,这个元素就直接在消费者和生产者之间传递,永远不会加入到阻塞队列中。

    展开全文
  • Java笔试面试-数据结构队列

    万次阅读 多人点赞 2019-09-18 09:04:13
      与栈相对的一种数据结构, 集合(Collection)的一个子类。队列允许在一端进行插入操作,而在另一端进行删除操作的线性表,栈的特点是后进先出,而队列的特点是先进先出。队列的用处很大,比如实现消息队列。...

    队列(Queue)

      与栈相对的一种数据结构, 集合(Collection)的一个子类。队列允许在一端进行插入操作,而在另一端进行删除操作的线性表,栈的特点是后进先出,而队列的特点是先进先出。队列的用处很大,比如实现消息队列。Queue 类关系图,如下:
    在这里插入图片描述

    1.Queue 分类

    • 双端队列:双端队列(Deque)是 Queue 的子类也是 Queue 的补充类,头部和尾部都支持元素插入和获取。
    • 阻塞队列:阻塞队列指的是在元素操作时(添加或删除),如果没有成功,会阻塞等待执行。例如,当添加元素时,如果队列元素已满,队列会阻塞等待直到有空位时再插入。
    • 非阻塞队列:非阻塞队列和阻塞队列相反,会直接返回操作的结果,而非阻塞等待。双端队列也属于非阻塞队列。

    2.Queue 方法

    • add(E):添加元素到队列尾部,成功返回 true
    • offer(E):添加元素到队列尾部,成功返回 true
    • remove():删除元素,成功返回 true,失败返回 false
    • poll():获取并移除此队列的第一个元素,若队列为空,则返回 null
    • peek():获取但不移除此队列的第一个元素,若队列为空,则返回 null
    • element():获取但不移除此队列的第一个元素,若队列为空,则抛异常

    3.Queue 使用实例

    Queue<String> linkedList = new LinkedList<>();
    linkedList.add("Dog");
    linkedList.add("Camel");
    linkedList.add("Cat");
    while (!linkedList.isEmpty()) {
        System.out.println(linkedList.poll());
    }
    

    程序执行结果:

    Dog
    Camel
    Cat
    

    阻塞队列

    1.BlockingQueue
      BlockingQueue 在 java.util.concurrent 包下,其他阻塞类都实现自 BlockingQueue 接口,BlockingQueue 提供了线程安全的队列访问方式,当向队列中插入数据时,如果队列已满,线程则会阻塞等待队列中元素被取出后再插入;当从队列中取数据时,如果队列为空,则线程会阻塞等待队列中有新元素再获取。

    BlockingQueue 核心方法

    插入方法:

    • add(E):添加元素到队列尾部,成功返回 true
    • offer(E):添加元素到队列尾部,成功返回 true
    • put(E):将元素插入到队列的尾部,如果该队列已满,则一直阻塞

    删除方法:

    • remove(Object):移除指定元素,成功返回 true,失败返回 false
    • poll(): 获取并移除队列的第一个元素,如果队列为空,则返回 null
    • take():获取并移除队列第一个元素,如果没有元素则一直阻塞

    检查方法:

    • peek():获取但不移除队列的第一个元素,若队列为空,则返回 null

    2.LinkedBlockingQueue
      LinkedBlockingQueue 是一个由链表实现的有界阻塞队列,容量默认值为 Integer.MAX_VALUE,也可以自定义容量,建议指定容量大小,默认大小在添加速度大于删除速度情况下有造成内存溢出的风险,LinkedBlockingQueue 是先进先出的方式存储元素。

    3.ArrayBlockingQueue
      ArrayBlockingQueue 是一个有边界的阻塞队列,它的内部实现是一个数组。它的容量是有限的,我们必须在其初始化的时候指定它的容量大小,容量大小一旦指定就不可改变。

      ArrayBlockingQueue 也是先进先出的方式存储数据,ArrayBlockingQueue 内部的阻塞队列是通过重入锁 ReenterLock 和 Condition 条件队列实现的,因此 ArrayBlockingQueue 中的元素存在公平访问与非公平访问的区别,对于公平访问队列,被阻塞的线程可以按照阻塞的先后顺序访问队列,即先阻塞的线程先访问队列。而非公平队列,当队列可用时,阻塞的线程将进入争夺访问资源的竞争中,也就是说谁先抢到谁就执行,没有固定的先后顺序。

    示例代码如下:

    // 默认非公平阻塞队列
    ArrayBlockingQueue queue = new ArrayBlockingQueue(6);
    // 公平阻塞队列
    ArrayBlockingQueue queue2 = new ArrayBlockingQueue(6,true);
    
    // ArrayBlockingQueue 源码展示
    public ArrayBlockingQueue(int capacity) {
        this(capacity, false);
    }
    public ArrayBlockingQueue(int capacity, boolean fair) {
        if (capacity <= 0)
            throw new IllegalArgumentException();
        this.items = new Object[capacity];
        lock = new ReentrantLock(fair);
        notEmpty = lock.newCondition();
        notFull =  lock.newCondition();
    }
    

    4.DelayQueue
      DelayQueue 是一个支持延时获取元素的无界阻塞队列,队列中的元素必须实现 Delayed 接口,在创建元素时可以指定延迟时间,只有到达了延迟的时间之后,才能获取到该元素。实现了 Delayed 接口必须重写两个方法 ,getDelay(TimeUnit)compareTo(Delayed),如下代码所示:

    class DelayElement implements Delayed {
            @Override
            // 获取剩余时间
            public long getDelay(TimeUnit unit) {
                // do something
            }
            @Override
            // 队列里元素的排序依据
            public int compareTo(Delayed o) {
                // do something
            }
        }
    

    DelayQueue 使用的完整示例,请参考以下代码:

    public class DelayTest {
        public static void main(String[] args) throws InterruptedException {
            DelayQueue delayQueue = new DelayQueue();
            delayQueue.put(new DelayElement(1000));
            delayQueue.put(new DelayElement(3000));
            delayQueue.put(new DelayElement(5000));
            System.out.println("开始时间:" +  DateFormat.getDateTimeInstance().format(new Date()));
            while (!delayQueue.isEmpty()){
                System.out.println(delayQueue.take());
            }
            System.out.println("结束时间:" +  DateFormat.getDateTimeInstance().format(new Date()));
        }
    static class DelayElement implements Delayed {
        // 延迟截止时间(单面:毫秒)
        long delayTime = System.currentTimeMillis();
        public DelayElement(long delayTime) {
            this.delayTime = (this.delayTime + delayTime);
        }
        @Override
        // 获取剩余时间
        public long getDelay(TimeUnit unit) {
            return unit.convert(delayTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
        }
        @Override
        // 队列里元素的排序依据
        public int compareTo(Delayed o) {
            if (this.getDelay(TimeUnit.MILLISECONDS) > o.getDelay(TimeUnit.MILLISECONDS)) {
                return 1;
            } else if (this.getDelay(TimeUnit.MILLISECONDS) < o.getDelay(TimeUnit.MILLISECONDS)) {
                return -1;
            } else {
                return 0;
            }
        }
        @Override
        public String toString() {
            return DateFormat.getDateTimeInstance().format(new Date(delayTime));
        }
    }
    

    }
    程序执行结果:

    开始时间:2019-6-13 20:40:38
    
    2019-6-13 20:40:39
    
    2019-6-13 20:40:41
    
    2019-6-13 20:40:43
    
    结束时间:2019-6-13 20:40:43
    

    非阻塞队列

      ConcurrentLinkedQueue 是一个基于链接节点的无界线程安全队列,它采用先进先出的规则对节点进行排序,当我们添加一个元素的时候,它会添加到队列的尾部;当我们获取一个元素时,它会返回队列头部的元素。它的入队和出队操作均利用 CAS(Compare And Set)更新,这样允许多个线程并发执行,并且不会因为加锁而阻塞线程,使得并发性能更好。

    ConcurrentLinkedQueue 使用示例:

    ConcurrentLinkedQueue concurrentLinkedQueue = new ConcurrentLinkedQueue();
    concurrentLinkedQueue.add("Dog");
    concurrentLinkedQueue.add("Cat");
    while (!concurrentLinkedQueue.isEmpty()) {
        System.out.println(concurrentLinkedQueue.poll());
    }
    

    执行结果:

    Dog
    
    Cat
    

    优先级队列

      PriorityQueue 一个基于优先级堆的无界优先级队列。优先级队列的元素按照其自然顺序进行排序,或者根据构造队列时提供的 Comparator 进行排序,具体取决于所使用的构造方法。优先级队列不允许使用 null 元素。

    PriorityQueue 代码使用示例:

    Queue<Integer> priorityQueue = new PriorityQueue(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            // 非自然排序,数字倒序
            return o2 - o1;
        }
    });
    priorityQueue.add(3);
    priorityQueue.add(1);
    priorityQueue.add(2);
    while (!priorityQueue.isEmpty()) {
        Integer i = priorityQueue.poll();
        System.out.println(i);
    }
    

    程序执行的结果是:

    3
    
    2
    
    1
    

    PriorityQueue 注意的点:

    • PriorityQueue 是非线程安全的,在多线程情况下可使用 PriorityBlockingQueue 类替代;
    • PriorityQueue 不允许插入 null 元素。

    面试笔试题

    1.ArrayBlockingQueue 和 LinkedBlockingQueue 的区别是什么?

    答:ArrayBlockingQueue 和 LinkedBlockingQueue 都实现自阻塞队列 BlockingQueue,它们的区别主要体现在以下几个方面:

    • ArrayBlockingQueue 使用时必须指定容量值,LinkedBlockingQueue 可以不用指定;
    • ArrayBlockingQueue 的最大容量值是使用时指定的,并且指定之后就不允许修改;而 LinkedBlockingQueue 最大的容量为 Integer.MAX_VALUE
    • ArrayBlockingQueue 数据存储容器是采用数组存储的;而 LinkedBlockingQueue 采用的是 Node 节点存储的。

    2.LinkedList 中 add() 和 offer() 有什么关系?

    答:add() 和 offer() 都是添加元素到队列尾部。offer 方法是基于 add 方法实现的,Offer 的源码如下:

    public boolean offer(E e) {
        return add(e);
    }
    

    3.Queue 和 Deque 有什么区别?

    答:Queue 属于一般队列,Deque 属于双端队列。一般队列是先进先出,也就是只有先进的才能先出;而双端队列则是两端都能插入和删除元素。

    4.LinkedList 属于一般队列还是双端队列?

    答:LinkedList 实现了 Deque 属于双端队列,因此拥有 addFirst(E)addLast(E)getFirst()getLast() 等方法。

    5.以下说法错误的是?

    A:DelayQueue 内部是基于 PriorityQueue 实现的
    B:PriorityBlockingQueue 不是先进先出的数据存储方式
    C:LinkedBlockingQueue 默认容量是无限大的
    D:ArrayBlockingQueue 内部的存储单元是数组,初始化时必须指定队列容量

    答:A

    题目解析:LinkedBlockingQueue 默认容量是 Integer.MAX_VALUE,并不是无限大的。

    6.关于 ArrayBlockingQueue 说法不正确的是?

    A:ArrayBlockingQueue 是线程安全的
    B:ArrayBlockingQueue 元素允许为 null
    C:ArrayBlockingQueue 主要应用场景是“生产者-消费者”模型
    D:ArrayBlockingQueue 必须显示地设置容量

    答:B

    题目解析:ArrayBlockingQueue 不允许元素为 null,如果添加一个 null 元素,会抛 NullPointerException 异常。

    7.以下程序执行的结果是什么?

    PriorityQueue priorityQueue = new PriorityQueue();
    priorityQueue.add(null);
    System.out.println(priorityQueue.size());
    

    答:程序执行报错,PriorityQueue 不能插入 null。

    8.Java 中常见的阻塞队列有哪些?
    答:Java 中常见的阻塞队列如下:

    • ArrayBlockingQueue,由数组结构组成的有界阻塞队列;
    • PriorityBlockingQueue,支持优先级排序的无界阻塞队列;
    • SynchronousQueue,是一个不存储元素的阻塞队列,会直接将任务交给消费者,必须等队列中的添加元素被消费后才能继续添加新的元素;
    • LinkedBlockingQueue,由链表结构组成的阻塞队列;
    • DelayQueue,支持延时获取元素的无界阻塞队列。

    9.有界队列和无界队列有哪些区别?

    答:有界队列和无界队列的区别如下。

    • 有界队列:有固定大小的队列叫做有界队列,比如:new ArrayBlockingQueue(6),6 就是队列的大小。
    • 无界队列:指的是没有设置固定大小的队列,这些队列的特点是可以直接入列,直到溢出。它们并不是真的无界,它们最大值通常为 Integer.MAX_VALUE,只是平常很少能用到这么大的容量(超过 Integer.MAX_VALUE),因此从使用者的体验上,就相当于 “无界”。

    10.如何手动实现一个延迟消息队列?

    答:说到延迟消息队列,我们应该可以第一时间想到要使用 DelayQueue 延迟队列来解决这个问题。实现思路,消息队列分为生产者和消费者,生产者用于增加消息,消费者用于获取并消费消息,我们只需要生产者把消息放入到 DelayQueue 队列并设置延迟时间,消费者循环使用 take() 阻塞获取消息即可。完整的实现代码如下:

    public class CustomDelayQueue {
        // 消息编号
        static AtomicInteger MESSAGENO = new AtomicInteger(1);
    public static void main(String[] args) throws InterruptedException {
        DelayQueue<DelayedElement> delayQueue = new DelayQueue<>();
        // 生产者1
        producer(delayQueue, "生产者1");
        // 生产者2
        producer(delayQueue, "生产者2");
        // 消费者
        consumer(delayQueue);
    }
    
    //生产者
    private static void producer(DelayQueue<DelayedElement> delayQueue, String name) {
        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    // 产生 1~5 秒的随机数
                    long time = 1000L * (new Random().nextInt(5) + 1);
                    try {
                        Thread.sleep(time);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    // 组合消息体
                    String message = String.format("%s,消息编号:%s 发送时间:%s 延迟:%s 秒",
                            name, MESSAGENO.getAndIncrement(), DateFormat.getDateTimeInstance().format(new Date()), time / 1000);
                    // 生产消息
                    delayQueue.put(new DelayedElement(message, time));
                }
            }
        }).start();
    }
    
    //消费者
    private static void consumer(DelayQueue<DelayedElement> delayQueue) {
        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    DelayedElement element = null;
                    try {
                        // 消费消息
                        element = delayQueue.take();
                        System.out.println(element);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();
    }
    
    // 延迟队列对象
    static class DelayedElement implements Delayed {
        // 过期时间(单位:毫秒)
        long time = System.currentTimeMillis();
        // 消息体
        String message;
        // 参数:delayTime 延迟时间(单位毫秒)
        public DelayedElement(String message, long delayTime) {
            this.time += delayTime;
            this.message = message;
        }
        @Override
        // 获取过期时间
        public long getDelay(TimeUnit unit) {
            return unit.convert(time - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
        }
        @Override
        // 队列元素排序
        public int compareTo(Delayed o) {
            if (this.getDelay(TimeUnit.MILLISECONDS) > o.getDelay(TimeUnit.MILLISECONDS))
                return 1;
            else if (this.getDelay(TimeUnit.MILLISECONDS) < o.getDelay(TimeUnit.MILLISECONDS))
                return -1;
            else
                return 0;
        }
        @Override
        public String toString() {
            // 打印消息
            return message + " |执行时间:" + DateFormat.getDateTimeInstance().format(new Date());
        }
    }
    

    }
    以上程序支持多生产者,执行的结果如下:

    生产者1,消息编号:1 发送时间:2019-6-12 20:38:37 延迟:2 秒 |执行时间:2019-6-12 20:38:39

    生产者2,消息编号:2 发送时间:2019-6-12 20:38:37 延迟:2 秒 |执行时间:2019-6-12 20:38:39

    生产者1,消息编号:3 发送时间:2019-6-12 20:38:41 延迟:4 秒 |执行时间:2019-6-12 20:38:45

    生产者1,消息编号:5 发送时间:2019-6-12 20:38:43 延迟:2 秒 |执行时间:2019-6-12 20:38:45

    ……

    展开全文
  • 队列(Queue)是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表。 这篇文章详细给大家介绍了java数据结构队列,感兴趣的朋友跟随小编一起学习吧
  • java数据结构——队列

    千次阅读 2019-02-21 17:12:33
    上一篇博客我们拒了羽毛球筒的例子来类比栈这种数据结构,这次我们用排队这种模型来类比我们接下来要说的数据结构——队列

    1.概述

    上一篇博客我们拒了羽毛球筒的例子来类比栈这种数据结构,这次我们用排队这种模型来类比我们接下来要说的数据结构——队列。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

    队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。

    我们拿单向队列举例。
    入队示例:
    在这里插入图片描述
    出队示例:

    在这里插入图片描述
    队列分为:
    ①、单向队列(Queue):只能在一端插入数据,另一端删除数据。
    ②、双向队列(Deque):每一端都可以进行插入数据和删除数据操作。
    ③、优先级队列(Priority):优先级队列是比栈和队列更专用的数据结构,在优先级队列中,数据项按照关键字进行排序,关键字最小(或者最大)的数据项往往在队列的最前面,而数据项在插入的时候都会插入到合适的位置以确保队列的有序。

    2.数组实现简单的单向队列

    
    public class ArrayQueue {
    
        private final Object[] data;
    
        private final int maxSize;
    
        private int currentSize;
    
        private int front;
    
        private int tail;
    
        public ArrayQueue(int maxSize){
             if (maxSize <= 0) {
                throw new IllegalArgumentException("容量应该大于0 : " + maxSize);
            }
            this.maxSize = maxSize;
            data = new Object[this.maxSize];
            this.front = -1;
            this.tail = -1;
            this.currentSize = 0;
        }
    
        public void insert(Object obj){
            if(currentSize == maxSize){
                throw new IllegalArgumentException("队列已经满了,不能插入数据");
            }else{
                if(tail == -1 && front == -1 ){  //为空的时候,当remove掉最后一个元素的时候将front和tail都重置
                    front ++;
                    tail ++;
                    currentSize++;
                    data[front] = obj;
                }else{
                    tail = (tail+1)%maxSize;
                    currentSize++;
                    data[tail] = obj;
                }
            }
        }
    
        public Object remove(){
            Object rtn = null;
            if(currentSize == 1){
                currentSize--;
                rtn = data[front];   /*先取值*/
                data[front] = null;
                front = -1;
                tail = -1;
            }else if(currentSize >1){
                currentSize--;
                rtn = data[front];
                data[front] = null;
                front = (front+1)%maxSize;
    
            }
            return rtn;
        }
    
        public boolean isEmpty(){
            return currentSize ==0;
        }
    
        public boolean isFull(){
            return currentSize == maxSize;
        }
    
        public void display(){
            if(isEmpty()){
                System.out.print("队列为空");
            }else{
                System.out.print("[ ");
                for(Object o : data){
                    System.out.print(o+" ");
                }
                System.out.print(" ]");
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            ArrayQueue arrayQueue = new ArrayQueue(5);
            arrayQueue.insert("0");
            arrayQueue.insert("1");
            arrayQueue.insert("2");
            arrayQueue.insert("3");
            arrayQueue.insert("4");
            arrayQueue.display();
    
            System.out.println("//");
            System.out.println(arrayQueue.remove());
            System.out.println(arrayQueue.remove());
            arrayQueue.display();
    
            System.out.println("//");
            arrayQueue.insert("5");
            arrayQueue.display();
    
            System.out.println("//");
            System.out.println(arrayQueue.remove());
            System.out.println(arrayQueue.remove());
            System.out.println(arrayQueue.remove());
            arrayQueue.display();
    
            System.out.println("//");
            arrayQueue.insert("6");
            arrayQueue.display();
    
        }
    
    
    }
    

    输出
    [ 0 1 2 3 4 ]
    //
    0
    1
    [ null null 2 3 4 ]
    //
    [ 5 null 2 3 4 ]
    //
    2
    3
    4
    [ 5 null null null null ]
    //
    [ 5 6 null null null ]

    3.双端队列

    双端队列就是一个两端都是结尾或者开头的队列, 队列的每一端都可以进行插入数据项和移除数据项,这些方法可以叫做:insertRight()、insertLeft()、removeLeft()、removeRight()
    1)如果严格禁止调用insertLeft()和removeLeft()(或禁用右端操作),那么双端队列的功能就和前面讲的栈功能一样。
    2)如果严格禁止调用insertLeft()和removeRight(或相反的另一对方法),那么双端队列的功能就和单向队列一样了。

    4.数组实现简单的优先级队列(数字越大优先级越高,优先remove最大的)

    public class PriorityArrayQueue {
    
        private final int size;
    
        private final int[] data;
    
        private int currentSize;
    
        public PriorityArrayQueue(int size){
            if(size <=0){
                throw new IllegalArgumentException("容量应该大于0 : " + size);
            }
            this.size = size;
            data = new int[this.size];
            currentSize = 0;
        }
    
        public void insert(int value){
            if(value < 0){
                System.out.println("不允许添加小于0的数");
            }
            if(currentSize == size){
                System.out.println("队列已经满了");
            }else if(currentSize == 0){
                data[0] = value;
                currentSize++;
            }else{
                data[currentSize] = value;
                for (int i = 0; i < currentSize; i++) {
                    if(data[currentSize]<data[i]){
                        int tmp = data[currentSize];
                        data[currentSize] = data[i];
                        data[i] = tmp;
                    }
                }
                currentSize++;
            }
        }
    
    
        public int remove(){
            int rtn = -1;
            if(currentSize > 0){
                rtn = data[currentSize-1];
                data[currentSize-1] = -1;
                currentSize--;
            }
            return rtn;
        }
    
        public void display(){
            if(currentSize == 0){
                System.out.println("队列为空");
            }
            System.out.print("[ ");
            for(int i : data){
                System.out.print(i+" ");
            }
            System.out.print(" ]");
                    System.out.println();
        }
    
    
        public static void main(String[] args) {
            PriorityArrayQueue priorityArrayQueue = new PriorityArrayQueue(3);
    
            priorityArrayQueue.insert(4);
            priorityArrayQueue.insert(2);
            priorityArrayQueue.insert(1);
            priorityArrayQueue.display();
            System.out.println("/");
    
            priorityArrayQueue.remove();
            priorityArrayQueue.display();
            System.out.println("/");
        }
    }
    

    输出
    [ 1 2 4 ]
    /
    [ 1 2 -1 ]
    /

    展开全文
  • 主要介绍了Java数据结构队列的简单定义与使用方法,简单描述了队列的功能、特点,并结合java实例形式分析了队列的简单定义与使用方法,需要的朋友可以参考下
  • 图解Java数据结构队列

    千次阅读 2019-08-06 16:00:07
    本篇文章,将对队列进行一个深入的解析。 使用场景 队列在日常生活中十分常见,...刚才通过生活中的例子大致了解了一下队列,那么从数据结构的角度来讲,队列到底是什么呢? 队列是一个有序列表,可以用数组或是...

    本篇文章,将对队列进行一个深入的解析。

    使用场景

    队列在日常生活中十分常见,例如:银行排队办理业务、食堂排队打饭等等,这些都是队列的应用。那么队列有什么特点呢?
    我们知道排队的原则就是先来后到,排在前面的人就可以优先办理业务,那么队列也一样,队列遵循先进先出的原则。

    队列介绍

    刚才通过生活中的例子大致了解了一下队列,那么从数据结构的角度来讲,队列到底是什么呢?

    • 队列是一个有序列表,可以用数组或是链表来实现
    • 遵循先进先出的原则,即:先存入队列的数据,先取出;后存入队列的数据,后取出
    数组模拟队列

    刚才说到,队列可以用数组或是链表来实现。
    那我们先来看看用数组如何模拟队列?
    在这里插入图片描述
    队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如上图,其中MaxSize是该队列的最大容量。
    因为队列的输出、输入是分别从前后端来处理的,因此需要两个变量front和rear分别记录队列前后端的下标,如上图所示,front会随着数据的输出改变;而rear则是随着数据的输入改变。
    继续深入分析:

    • 当我们将数据存入队列时,称为"addQueue",addQueue的处理需要有两个步骤:
      a)将尾指针往后移:rear + 1
      b)若尾指针rear小于队列的最大下标MaxSize - 1,则将数据存入rear所指的数组元素中,否则无法存入数据。rear == MaxSize - 1 时,表示队列已满

    分析过后,我们用代码来实现数组模拟队列:

    //使用数组模拟队列——编写一个ArrayQueue类
    class ArrayQueue {
    	private int maxSize; // 表示数组的最大容量
    	private int front; // 队列头
    	private int rear; // 队列尾
    	private int[] arr; // 该数组用于存放数据
    
    	// 创建队列的构造器
    	public ArrayQueue(int maxSize) {
    		this.maxSize = maxSize;
    		arr = new int[maxSize];
    		front = -1; // 指向队列头部(指向的是队列头的前一个位置)
    		rear = -1;// 指向队列尾部(指向的是队列尾的数据)
    	}
    
    	// 判断队列是否满
    	public boolean isFull() {
    		return rear == maxSize - 1;
    	}
    
    	// 判断队列是否为空
    	public boolean isEmpty() {
    		return rear == front;
    	}
    
    	// 添加数据到队列
    	public void addQueue(int n) {
    		// 判断队列是否满
    		if (isFull()) {
    			System.out.println("队列满,不能加入数据");
    			return;
    		}
    		rear++;// 让rear后移
    		arr[rear] = n;
    	}
    
    	// 获取队列的数据
    	public int getQueue() {
    		// 判断队列是否空
    		if (isEmpty()) {
    			// 抛出异常
    			throw new RuntimeException("队列空,不能取出数据");
    		}
    		front++;// 让front后移
    		return arr[front];
    	}
    
    	// 显示队列的所有数据
    	public void showQueue() {
    		// 遍历
    		if (isEmpty()) {
    			System.out.println("队列为空");
    			return;
    		}
    		for (int i : arr) {
    			System.out.printf("%d\t", i);
    		}
    	}
    }
    

    经过分析后再来编写代码,会觉得非常简单,现在一个数组模拟的队列就编写完成了。接下来编写测试代码:

    public static void main(String[] args) {
    		// 创建一个队列
    		ArrayQueue arrayQueue = new ArrayQueue(3);
    		int key;// 接收用户输入
    		Scanner sc = new Scanner(System.in);
    		boolean loop = true;
    		// 输出一个菜单
    		while (loop) {
    			System.out.println();
    			System.out.println("1:显示队列");
    			System.out.println("2:添加数据到队列");
    			System.out.println("3:从队列获取数据");
    			key = sc.nextInt();// 接收一个字符
    			switch (key) {
    			case 1:
    				arrayQueue.showQueue();
    				break;
    			case 2:
    				System.out.println("输入一个数:");
    				int value = sc.nextInt();
    				arrayQueue.addQueue(value);
    				break;
    			case 3:
    				try {
    					int res = arrayQueue.getQueue();
    					System.out.println("取出的数据是:" + res);
    				} catch (Exception e) {
    					System.out.println(e.getMessage());
    				}
    				break;
    			}
    		}
    	}
    

    运行效果如下:
    在这里插入图片描述
    但是,这个程序有一个很大的问题,就是当你把队列中的元素取出来之后,再添加发现添加不了,一直提示队列为空,因为此时指向队列前后端的两个变量相等,而判断队列是否为空就是依靠这两个变量来判断的。

    数组模拟环形队列

    刚才我们说到这个程序是有问题的,数组只能使用一次,那我们可以对前面的数组模拟队列进行优化,为了能够充分利用数组,我们可将数组看成是一个环形的。
    我们先来分析一下(还是看这张图):
    在这里插入图片描述

    1. 首先我们将front的含义做一个调整:front就指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素,front的初始值为0
    2. 将rear的含义也做一个调整:rear指向队列的最后一个元素的后一个位置,这样调整的目的是希望空出一个空间作为一个约定,rear的初始值也为0
    3. 当队列满时,条件是(rear + 1) % MaxSize == front,那么条件依据是什么呢?我们举个例子,假设现在rear指向的是数组的倒数第二个元素,因为我们要预留出一个空间,所以此时队列应该就是满的,而事实上倒数第二个元素的下标加1然后取模MaxSize确实等于front,因为此时的front为0,就证明该队列已满
    4. 当队列空时,条件是rear == front

    那么如果按照上面的分析实现,队列中的有效元素个数即为:(rear + MaxSize - front) % MaxSize。
    接下来在原来的代码上进行一个优化:

    public class CircleArrayQueueDemo {
    
    	public static void main(String[] args) {
    		// 创建一个队列
    		CircleArrayQueue arrayQueue = new CircleArrayQueue(3);
    		int key;// 接收用户输入
    		Scanner sc = new Scanner(System.in);
    		boolean loop = true;
    		// 输出一个菜单
    		while (loop) {
    			System.out.println();
    			System.out.println("1:显示队列");
    			System.out.println("2:添加数据到队列");
    			System.out.println("3:从队列获取数据");
    			key = sc.nextInt();// 接收一个字符
    			switch (key) {
    			case 1:
    				arrayQueue.showQueue();
    				break;
    			case 2:
    				System.out.println("输入一个数:");
    				int value = sc.nextInt();
    				arrayQueue.addQueue(value);
    				break;
    			case 3:
    				try {
    					int res = arrayQueue.getQueue();
    					System.out.println("取出的数据是:" + res);
    				} catch (Exception e) {
    					System.out.println(e.getMessage());
    				}
    				break;
    			}
    		}
    	}
    }
    
    //使用数组模拟队列——编写一个ArrayQueue类
    class CircleArrayQueue {
    	private int maxSize; // 表示数组的最大容量
    	private int front; // 队列的第一个元素
    	private int rear; // 队列的最后一个元素的后一个位置
    	private int[] arr; // 该数组用于存放数据
    
    	// 创建队列的构造器
    	public CircleArrayQueue(int maxSize) {
    		this.maxSize = maxSize;
    		arr = new int[maxSize];
    	}
    
    	// 判断队列是否满
    	public boolean isFull() {
    		return (rear + 1) % maxSize == front;
    	}
    
    	// 判断队列是否为空
    	public boolean isEmpty() {
    		return rear == front;
    	}
    
    	// 添加数据到队列
    	public void addQueue(int n) {
    		// 判断队列是否满
    		if (isFull()) {
    			System.out.println("队列满,不能加入数据");
    			return;
    		}
    		// 直接将数据加入
    		arr[rear] = n;
    		rear = (rear + 1) % maxSize;// 将rear后移,必须考虑取模(当rear指向最后时,可以通过取模将rear指向队列起始位置)
    	}
    
    	// 获取队列的数据
    	public int getQueue() {
    		// 判断队列是否空
    		if (isEmpty()) {
    			// 抛出异常
    			throw new RuntimeException("队列空,不能取出数据");
    		}
    		// 需要分析出front是指向队列的第一个元素
    		// 1、先把front对应的值保存到一个临时变量中
    		int value = arr[front];
    		// 2、将front后移,考虑取模
    		front = (front + 1) % maxSize;
    		// 3、将临时保存的变量返回
    		return value;
    	}
    
    	// 显示队列的所有数据
    	public void showQueue() {
    		// 遍历
    		if (isEmpty()) {
    			System.out.println("队列为空");
    			return;
    		}
    		// 从front开始遍历
    		for (int i = front; i < front + size(); i++) {
    			System.out.printf("%d\t", arr[i % maxSize]);
    		}
    	}
    
    	// 求出当前队列有效数据个数
    	public int size() {
    		return (rear + maxSize - front) % maxSize;
    	}
    }
    

    运行效果如下:
    在这里插入图片描述
    现在我们就能够循环利用这个队列了。

    推荐阅读

    1.图解Java数据结构之稀疏数组

    2.图解Java数据结构之单链表

    3.图解Java数据结构之双向链表

    4.图解Java数据结构之环形链表

    展开全文
  • 主要介绍了Java数据结构之有效队列定义与用法,结合实例形式分析了java有效队列的数据插入、删除、判断、计算等相关操作技巧,需要的朋友可以参考下
  • 主要介绍了java 数据结构之栈与队列的相关资料,这里对java中的栈和队列都做出实现实例来帮助大家理解学习数据结构,需要的朋友可以参考下
  • 主要介绍了Java数据结构之循环队列简单定义与用法,简要描述了循环队列的概念、原理,并结合实例形式分析了java循环队列的定义与使用方法,需要的朋友可以参考下
  • JAVA数据结构——队列

    千次阅读 2020-01-15 19:11:29
    队列队列是一种特殊的线性表,特殊之处在于它只...队列数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只...
  • 主要介绍了java 数据结构中栈和队列的实例详解的相关资料,主要使用数组与线性表的方法来实现,需要的朋友可以参考下
  • 队列本身是个有序列表,若使用数组的结构来存储队列数据,则队列数组的声明如图,其中5是该队列的最大容量(只代表我这个图) 因为队列的输出,输入都是分别从前后端来处理的,因此需要两个变量(头部)及(尾部)...
  • 标签:Java 数据结构 算法 作者 : Maxchen 版本 : V1.0.0 日期 : 2020/3/29 目录1.队列的概念2.数组模拟队列3.队列运行测试 1.队列的概念 队列同样是一种特殊的线性表,其插入和删除的操作分别在表的两端进行,...
  • 主要介绍了java实现队列数据结构代码详解,简单介绍了队列结构以应用场景,涉及详细实现代码,还是比较不错的,这里分享给大家,需要的朋友可以参考下。
  • 主要介绍了java编程队列数据结构代码示例,简单介绍了队列的相关基础知识,然后通过实例向大家展示其实现方法,具有一定参考价值,需要的朋友可以了解下。
  • Java数据结构和算法——队列.pdf
  • java数据结构——环形队列

    千次阅读 2018-09-24 11:11:32
    这时候环形队列就解决了这样的一个问题,环形队列的front指针始终指向当前队列的最后位置;end指针始终指向第一个元素的前一个位置为-1,存储元素的时候头部和尾部都可以相互移动,而不必造成假溢出现象,节省了内存...
  • java基础笔记数据结构-队列,详细描述了队列的原理及其实现方式,基础数据结构
  • JAVA数据结构——队列(二)

    千次阅读 2020-01-17 20:27:59
    根据上篇文章JAVA数据结构——队列我们留一下一个问题,如何利用队列解决素数环问题,下面我来讲解一下思路: 1. 先映入顺序表类Sqlist 和 链队列类 LinkQueue ,在创建Sqlist类的一个对象L作为顺序表,用于存放素数...
  • 队列也是一种数据结构,类似于栈,只是与栈相反,在队列中先插入的数据也先被移除,即先进先出(FIFO,First In First Out)。队列可以理解成排队,比如,食堂窗口排的队,越在前面的,越早得到服务而先离开。在银行...
  • Java数据结构与算法】队列与环形队列

    千次阅读 多人点赞 2020-04-05 17:14:30
    队列与环形队列
  • 主要介绍了Java数据结构之链表、栈、队列、树的实现方法,结合实例形式分析了Java数据结构中链表、栈、队列、树的功能、定义及使用方法,需要的朋友可以参考下
  • Java数据结构和算法——队列

    千次阅读 2016-07-02 14:39:12
    介绍队列(Queue),是一种线性存储结构。它有以下几个特点: 数据按照”先进先出”方式进出队列; 只允许在”队首”进行删除操作,”队尾”进行插入操作。 队列通常包括的两种操作:入队列 和 出队列。示意图队列中...
  • 1、队列的基本概念 队列(queue)是一种特殊的线性表,特殊之处在于它只允许在表的...队列数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元 素称为出队。因为队列只允许在一...
  • Java数据结构和算法(五)——队列

    千次阅读 2014-10-19 10:36:59
    Java数据结构和算法(五)——队列
  • java数据结构之线性队列的实现

    千次阅读 2016-06-03 21:38:55
    今天介绍一下数据结构中的线性队列以及线性队列中的缺点,和改善线性队列的循环线性队列操作。 队列的定义: 队列(Queue)是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表。 (1)允许...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 227,267
精华内容 90,906
关键字:

java数据结构队列

java 订阅
数据结构 订阅