数据结构之Java Queue

本文从通过Java Array 实现一个简单的队列和循环队列，最后对Java Queue 接口及其子类的特点进行一个总结

队列的存储结构

队列与栈不同，是一种先进先出的数据结构，元素从对头读取从队尾写入
示意图如下：

timg.jpeg

本文将使用Java 数组 来实现一个简单队列和一个循环队列，首先定义一个接口

public interface MyQueue<E> {
  boolean enqueue(E e);
  E dequeue();
}

简单队列

代码逻辑参考注释

public class MyArrayQueue<E>  implements MyQueue<E>{

    private Object[] elements;
    private int capacity;
    private int head = 0;
    private int tail = 0;

    public MyArrayQueue(int capacity){
        this.capacity = capacity;
        elements = new Object[this.capacity];
    }

    /**
     * 入队 O(n)
     * 1. tail == capacity ， 并且 head == 0 代表队列没有可用空间
     * 2. 当队列有可用空间时，进行数据搬移
     * @param e
     * @return
     */
    public boolean enqueue(E e) {
        if(tail == capacity){
            // 队列满了
            if(head == 0){
                return false;
            }
            for(int i=head;i<tail;i++){
                elements[i-head] = elements[i];
            }
            tail = tail - head;
            head = 0;
        }
        this.elements[tail] = e;
        tail ++;
        return true;
    }

    /**
     * 出队 O(1)
     * @return
     */
    @SuppressWarnings("unchecked")
    public E dequeue() {
        if(head == tail){
            return null;
        }
        E e = (E)elements[head];
        head ++;
        return e;
    }
}

测试

  @Test
    public void myArrayQueueTest(){
        MyQueue<String> queue = new MyArrayQueue<String>(5);
        queue.enqueue("a");
        Assert.assertEquals(queue.dequeue(),"a");
        queue.enqueue("b");
        Assert.assertEquals(queue.dequeue(),"b");
        queue.enqueue("c");
        Assert.assertEquals(queue.dequeue(),"c");
        queue.enqueue("d");
        queue.enqueue("e");
        queue.enqueue("f");
        queue.enqueue("g");
        queue.enqueue("h");
        Assert.assertFalse(queue.enqueue("s"));
        Assert.assertEquals(queue.dequeue(),"d");
        Assert.assertEquals(queue.dequeue(),"e");
        Assert.assertEquals(queue.dequeue(),"f");
        Assert.assertEquals(queue.dequeue(),"g");
        Assert.assertEquals(queue.dequeue(),"h");
        Assert.assertNull(queue.dequeue());
    }

上个队列中，当队列慢时有数据搬移工作，整体效率不够，所有有了循环队列的实现

循环队列

public class MyCircularQueue<E> implements MyQueue<E> {

   private Object[] elements;
   private int capacity;
   private int head = 0;
   private int tail = 0;

   public MyCircularQueue(int capacity){
       this.capacity = capacity;
       elements = new Object[capacity];
   }

   /**
    * 入队 O(1)
    * 1. (tail+1) % capacity == head 队满，比如 capacity = 5 , tail = 4 , head = 0
    * 2. tail 元素添加后 tail 往后移动一位，当等于capacity 重新归 0
    * @param e
    * @return
    */
   public boolean enqueue(E e) {
       if((tail+1) % capacity == head){
           return false;
       }
       this.elements[tail] = e;
       tail = (tail+1) % capacity;
       return true;
   }

   /**
    * 出队 O(1)
    * 1. head == tail 空队列
    * 2. 去除元素后 head 往后移动一位，当等于capacity 重新归 0
    * @return E
    */
   @SuppressWarnings("unchecked")
   public E dequeue() {
       if(head == tail){
           return null;
       }
       E e = (E)elements[head];
       head = (head+1) % capacity;
       return e;
   }
}

测试

@Test
    public void myCircularQueueTest(){
        MyQueue<String> queue = new MyCircularQueue<String>(5);
        queue.enqueue("a");
        Assert.assertEquals(queue.dequeue(),"a");
        queue.enqueue("b");
        Assert.assertEquals(queue.dequeue(),"b");
        queue.enqueue("c");
        Assert.assertEquals(queue.dequeue(),"c");
        queue.enqueue("d");
        queue.enqueue("e");
        queue.enqueue("f");
        queue.enqueue("g");
        Assert.assertFalse(queue.enqueue("h"));
        Assert.assertEquals(queue.dequeue(),"d");
        Assert.assertEquals(queue.dequeue(),"e");
        Assert.assertEquals(queue.dequeue(),"f");
        Assert.assertEquals(queue.dequeue(),"g");
        Assert.assertNull(queue.dequeue(),"h");
    }

队列作为一种重要的数据格式，在实际应用开发中占有重要地位，本文实现的队列都比较简单，在Java中根据队列不同的应用场景做了不一样的封装，下面总结一下Java 语言中不同队列的特点

Java Queue 接口

Queue接口在java.util包中可用，并扩展了Collection接口。队列集合用于保存要处理的元素，并提供各种操作。它是一个有序的对象列表，其使用仅限于在列表末尾插入元素并从头开始删除元素列表，即它遵循FIFO或先入先出原则。Queue的特征：

• Queue用于在队列末尾插入元素并从队列的开头删除。它遵循FIFO概念。
• Java Queue支持Collection接口的所有方法，包括插入，删除等。
• LinkedList，ArrayBlockingQueue、PriorityQueue是最常用的实现。
• 如果对BlockingQueues执行任何null操作，则抛出NullPointerException
• 带有 blocking 的队列是线程安全的，比如 ArrayBlockingQueue
• java.util 包中可用的队列是无界队列 ，使用不当容易造成内存泄漏
• java.util.concurrent 包中可用的队列是有界队列
• 除 Deques（双端队列）之外的所有队列分别支持在队列的尾部和头部插入和移除。Deques支撑元件在两端插入和移除

操作方法上的一些差别

• offer，add 入队操作，队满时 add 将抛出异常， offer 返回 false
• poll，remove 出队操作，remove 内部调用的是poll ,不过remove 发现元素为null时会抛出异常，poll 返回 null
• peek，element 用于在队列的头部查询元素，在队列为空时， element 抛出一个异常 , peek 返回 null

本文是学习极客时间数据结构与算法之美结合Java语言的一些笔记，如果你对此课程感兴趣可以在下载极客时间App搜索该课程,也可以点击下面链接查看
数据结构与算法之美