常规队列

基本定义

在计算机科学中，queue是以顺序的方式维护的一组数据集合，在一端添加数据，从另一端添加数据。习惯来说，添加的一端为尾，移除的一端为头，就如同生活中的排队买商品。

环形链表实现队列

只要根据队列的基本定义和链表的语法，就可以很轻松的写出队列的方法
特殊：
队列需要有容量限制的，删除和添加只在头尾，不可在中间插入
定义队列的接口

public interface Queue<E> {

    /**
     * 向队列尾插入值
     * @param value-待插入值
     * @return 插入成功返回true，插入失败返回false
     */
    boolean offer(E value);

    /**
     * 从队列头获取值，并移除
     * @return 如果列表非空返回对头值，否则返回null
     */
    E pool();

    /**
     * 从队列头获取值，不移除
     * @return 如果队列非空返回对头值，否则返回null
     */
    E peek();

    /**
     * 检查队列是否为空
     * @return 空返回true，否则返回false
     */
    boolean isEmpty();

    /**
     * 检查队列是否已满
     * @return 满返回true，否则返回false
     */
    boolean isFull();
}

环形链表作为接口的实现类

public class LinkedListQueue<E> implements Queue<E>, Iterable<E> {

    //定义节点内部类
    private static class Node<E> {
        E value;
        Node<E> next;

        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    Node<E> head = new Node<>(null, null);
    //环形链表头尾相连
    Node<E> tail = head;
    private int size; //节点数

    private int capacity = Integer.MAX_VALUE;//容量

    {
        //构造方法共同有的可以抽取出来
        tail.next = head;
    }

    public LinkedListQueue(int capacity) {
        this.capacity = capacity;
    }

    //构造方法
    public LinkedListQueue() {
    }

    //向队列尾部加入值
    @Override
    public boolean offer(E value) {
        //设定队列的容量检查
        if(isFull()) {
            return false;
        }
        Node<E> added = new Node<>(value, null);
        //原来的尾巴指向新节点
        tail.next = added;
        //更新尾巴
        tail = added;
        //节点数量增加
        size++;
        return true;
    }


    //队列头获取值并且移除
    @Override
    public E pool() {
        //队列为空
        if(isEmpty()) {
            return null;
        }
        Node<E> first = head.next;
        //删除
        head.next = first.next;
        //节点数减少
        size--;
        //特殊情况
        if(first == tail){
            tail = head;
        }
        return first.value;
    }

    //队列头获取值不移除
    @Override
    public E peek() {
        //队列为空
        if(isEmpty()) {
            return null;
        }
        //非空就找head.next的值
        return head.next.value;
    }

    @Override
    public boolean isEmpty() {
        //当头结点和尾节点的地址相等，即都指向哨兵节点
        return head == tail;

    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = head.next;
            @Override
            public boolean hasNext() {
                //判断return的条件并且移动指针
                //环形链表遍历结束条件是尾回到头
                return p != head;
            }

            @Override
            public E next() {
                E value = p.value;
                p = p.next;
                return value;
            }
        };
    }
}

环形数组实现队列

好处
1、对比普通数组，起点和终点更为自由，不用考虑数据移动
2、“环”意味着不存在【越界】问题
3、数组性能更佳
4、环形数组比较适合实现有界队列，RingBuffer等

下标计算的方法：
例如，数组长度是5，当前位置是3，向前走2步，此时下标为(3 + 2)%5 = 0
即：(cur + step)%length
·cur当前指针位置
·step前进步数
·length数组长度

方式一(留位置)

public class ArrayQueue1<E> implements Queue<E>, Iterable<E>{

    private final E[] array;
    private int head = 0;
    private int tail = 0;

    @SuppressWarnings("all")//抑制警告产生
    public ArrayQueue1(int capacity) {
        array = (E[])new Object[capacity + 1];
    }

    //向队列尾部加入值
    @Override
    public boolean offer(E value) {
        if(isEmpty()) {
            return false;
        }
        //向尾部添加值
        array[tail] = value;
        //尾指针向前一步
        //这样可以防止索引出现异常，比如数组长度为5但是索引只有0~4
        tail = (tail + 1) % array.length;
        return true;
    }

    //队列头获取值并且移除
    @Override
    public E pool() {
        if(isEmpty()) {
            return null;
        }
        //得到当前头指针的值
        E value = array[head];
        //删除操作把头指针移动到下一个
        head = (head + 1) % array.length;
        return value;
    }

    //队列头获取值不移除
    @Override
    public E peek() {
        if(isEmpty()) {
            return null;
        }
        //得到当前头指针的值
        return array[head];
    }


    @Override
    public boolean isEmpty() {

        return head == tail;
    }

    @Override
    public boolean isFull() {
        //当尾指针走一步就到了头指针的索引值那么就是满的
        return (tail+1) % array.length == head;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;
            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public E next() {
                E value = array[p];
                //p向后移
                p = (p+1) % array.length;
                return value;
            }
        };
    }
}

方式二(size变量控制)

private final E[] array;
   private int head = 0;
   private int tail = 0;
   //引入新变量
   private int size;

   @SuppressWarnings("all")//抑制警告产生
   public ArrayQueue2(int capacity) {
       array = (E[])new Object[capacity];
   }

   //向队列尾部加入值
   @Override
   public boolean offer(E value) {
       if(isEmpty()) {
           return false;
       }
       //向尾部添加值
       array[tail] = value;
       //尾指针向前一步
       //这样可以防止索引出现异常，比如数组长度为5但是索引只有0~4
       tail = (tail + 1) % array.length;
       size++;
       return true;
   }

   //队列头获取值并且移除
   @Override
   public E pool() {
       if(isEmpty()) {
           return null;
       }
       //得到当前头指针的值
       E value = array[head];
       //删除操作把头指针移动到下一个
       head = (head + 1) % array.length;
       size--;
       return value;
   }

   //队列头获取值不移除
   @Override
   public E peek() {
       if(isEmpty()) {
           return null;
       }
       //得到当前头指针的值
       return array[head];
   }


   @Override
   public boolean isEmpty() {

       //return head == tail;
       //用size来判断为不为空
       return size == 0;
   }

   @Override
   public boolean isFull() {
       //当尾指针走一步就到了头指针的索引值那么就是满的
       //return (tail+1) % array.length == head;
       //用size判断是否为满
       return size == array.length;
   }

   @Override
   public Iterator<E> iterator() {
       return new Iterator<E>() {
           int p = head;
           int count = 0;
           @Override
           public boolean hasNext() {
               return count < size;
           }

           @Override
           public E next() {
               E value = array[p];
               //p向后移
               p = (p+1) % array.length;
               count++;
               return value;
           }
       };
   }

方法三(头尾指针移动)

private final E[] array;
    private int head;
    private int tail;

    @SuppressWarnings("all")//抑制警告产生
    public ArrayQueue3(int capacity) {
        //传过来的容量不是2^n两种办法
        //1、抛异常
        /*if ((capacity & capacity - 1) != 0) {
            throw new IllegalArgumentException("capactiy 必须是2的幂");
        }*/
        //2、帮忙改成2^n   13 -> 16  22 -> 32
        capacity -= 1;
        capacity |=capacity>>1;
        capacity |=capacity>>2;
        capacity |=capacity>>8;
        capacity |=capacity>>16;
        capacity += 1;
        array = (E[])new Object[capacity];
    }
    /*
        head =0
        tail = 3 % 3 = 0
        capacity=3

        0 1 2
        d b c
     */

    /*
        求模运算：
            - 如果除数是 2 的前n次方
            - 那么被除数的后n位即为余数(模)
            - 求被除数的后n位方法，与2^n-1 按位与
     */

    @Override
    public boolean offer(E value) {
        if(isEmpty()) {
            return false;
        }
        //tail不直接做索引
        //array[(int) (Integer.toUnsignedLong(tail) % array.length)] = value;
        //如果保证了数组长度是2^n，那么就可以用数组长度 - 1 来按位与运算
        array[tail & (array.length - 1)] = value;
        //添加完指针移动
        tail++;
        return true;
    }

    @Override
    public E pool() {
        if(isEmpty()) {
            return null;
        }
        E value = array[head & (array.length - 1)];
        head++;
        return value;
    }

    @Override
    public E peek() {
        if(isEmpty()) {
            return null;
        }
        return array[head & (array.length - 1)];
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public boolean isFull() {
        //等于数组长度就表示满了
        return tail - head == array.length;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;
            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public E next() {
                E value = array[p & (array.length - 1)];
                p++;
                return value;
            }
        };
    }