4.基础数据结构-队列

4.基础数据结构-队列

4.1 概述

? ? ? ?队列是一种基础且广泛应用的线性数据结构，它模拟了现实生活中的排队现象，遵循“先进先出”（First-In-First-Out, FIFO）原则。在队列中，元素的添加和移除遵循特定的顺序：

? ? ? ?入队操作（Enqueue）：新元素被添加到队列的尾部（称为队尾或rear），意味着最近到达的元素将排在队列的末尾等待处理。

? ? ? ?出队操作（Dequeue）：从队列的头部（称为队头或front）移除元素，确保最先到达的元素最先离开队列并被处理。

队列的主要特性包括：

? ? ? ?线性结构：队列中的元素按一定的顺序排列。
? ? ? ?动态变化：队列的大小可以随着元素的入队和出队而动态改变。
? ? ? ?有限或无限容量：取决于实现方式，队列可能有预先设定的最大容量（如固定大小的数组实现），也可以理论上支持无限数量的元素（如链表实现）。
? ? ? ?队列在计算机科学中有多种应用，例如任务调度、消息传递、打印机任务管理、缓冲区管理等场合，都利用了其有序和公平的特性来组织和处理数据流。队列可以用数组或链表等多种数据结构来实现，并且根据应用场景的不同，还发展出了优先队列、循环队列、双端队列等多种变体。

队列接口

package org.alogorithm.queue;

public interface Queue<E> extends   Iterable<E> {
    /**
     * @Description 向队尾插入值
     * @Author LY
     * @Param [value] 待插入的值
     * @return boolean 是否成功
     * @Date 2024/1/18 9:53
     **/
    boolean offer(E value);

    /**
     * @Description 从队头获取值，并移除
     * @Author LY
     * @return E    如果队列非空，返回队头值，否则返回null
     * @Date 2024/1/18 9:53
     **/
    E pool();

    /**
     * @Description 从队头获取值，不移除
     * @Author LY
     * @return E    如果队列非空，返回队头值，否则返回null
     * @Date 2024/1/18 9:55
     **/
    E peek();

    /**
     * @Description  检查队列是否为空
     * @Author LY
     * @return boolean 空返回true，否则返回false
     * @Date 2024/1/18 9:55
     **/
    boolean isEmpty();
    /**
     * @Description 队列是否满已满
     * @Author LY
     * @return boolean 满 true 否则 false
     * @Date 2024/1/18 11:34
     **/
    boolean isFull();

}

4.2 链表实现

public class LinkedListQueue<E> implements Queue<E>, Iterable<E> {
    public static void main(String[] args) {
        LinkedListQueue<Integer>queue=new LinkedListQueue<Integer>(1);
        Integer peek1 = queue.peek();
        boolean empty1 = queue.isEmpty();
        //向尾部添加开始
        boolean offer1 = queue.offer(1);
        boolean offer2 = queue.offer(2);
        //向尾部添加结束
        boolean empty2 = queue.isEmpty();
        Integer peek2 = queue.peek();
        Integer pool1 = queue.pool();
        Integer pool2 = queue.pool();
    }

    @Override
    public boolean offer(E value) {
        //满了
        if(isFull()){
            return false;
        }
        //新节点.next指向头
        Node newNode = new Node(value, head);
        //原尾节点.next指向新节点
        tail.next = newNode;
        //tail指向新节点
        tail = newNode;
        size++;
        return true;
    }
    @Override
    public E pool() {
        if(this.isEmpty()){
            return null;
        }
        Node<E> first=head.next;
        head.next=first.next;
        //如果是最后一个节点
        if(first==tail){
            tail=head;
        }
        size--;
        return first.value;
    }
    @Override
    public E peek() {
        if(this.isEmpty()){
            return null;
        }
        return head.next.value;
    }

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

    @Override
    public boolean isFull() {
        return size==capacity;
    }
    //节点类
    private static class Node<E> {
        E value;
        Node<E> next;

        public Node(E value, Node<E> next) {
            this.next = next;
            this.value = value;
        }
    }
    @Override
    public Iterator iterator() {
        return new Iterator<E>() {
            Node<E>p=head.next;
            @Override
            public boolean hasNext() {
               return p.next!=head;
            }

            @Override
            public E next() {
                E value=p.value;
                return value;
            }
        };
    }
    Node<E> head = new Node<E>(null, null);
    Node<E> tail = head;
    //当前大小
    private Integer size=0;
    //容量
    private Integer capacity =Integer.MAX_VALUE;
    {
        tail.next = head;
    }
    public LinkedListQueue(Integer capacity) {
        this.capacity = capacity;

    }
    public LinkedListQueue() {
    }
}

4.3 环形数组实现

使用环形数组而不是线性数组的原因：

空间利用率：

? ? ? ?在普通线性数组中实现队列时，如果队列的头部和尾部相隔较远（例如，头指针在前而尾指针在后接近数组末尾），中间会有很多未使用的空间。当尾指针到达数组末尾时，若没有足够的空间添加新元素，即使数组前面有空闲位置也无法继续入队，这就出现了所谓的“假溢出”问题。
? ? ? ?环形数组通过计算下标时取模（即循环访问数组）的方式，使得队列的尾部可以“绕回”到数组的头部，这样就可以充分利用整个数组空间，避免了假溢出。
高效性：

? ? ? ?环形队列的所有操作（入队、出队）理论上都可以在常数时间内完成（O(1)复杂度）。这是因为可以通过预先设定好的固定大小的数组，并且维护好头指针和尾指针，直接在对应的位置进行插入和删除操作，无需像线性数组那样可能需要移动大量元素以腾出或填补空间。
适用于实时系统和硬件实现：

? ? ? ?环形队列因其简单高效的特性，在实时操作系统、网络通信、多线程间同步通信等场合被广泛应用。例如在网络设备中，数据包的接收和发送常常利用环形缓冲区（即环形队列的一种形式）来缓存和处理数据流，这样可以确保在高频率的数据交换过程中，不会因为频繁地申请释放内存而导致性能下降或不可预测的行为。

4.3.1 环形数组实现1

需要考虑当前数组满了的情况下头尾指针指向的位置。

package org.alogorithm.queue;

import java.util.Iterator;
import java.util.Spliterator;
import java.util.function.Consumer;

public class ArrayQueue1<E> implements Queue<E>{
    public static void main(String[] args) {
        ArrayQueue1<Integer>queue=new ArrayQueue1<Integer>(1);
        Integer peek1 = queue.peek();
        boolean empty1 = queue.isEmpty();
        //向尾部添加开始
        boolean offer1 = queue.offer(1);
        boolean offer2 = queue.offer(2);
        //向尾部添加结束
        boolean empty2 = queue.isEmpty();
        Integer peek2 = queue.peek();
        Integer pool1 = queue.pool();
        Integer pool2 = queue.pool();
    }
    private E[] arr;
    private int head=0;
    private int tail=0;
    //抑制警告产生
    @SuppressWarnings("all")
    public ArrayQueue1(int capacity) {
        this.arr = (E[]) new Object[capacity+1];
    }
    @Override
    public boolean offer(E value) {
        if(isFull()){
            return false;
        }
        arr[tail]=value;
        //防止当前元素时最后一个
        tail=(tail+1)% arr.length;
        return true;
    }
    @Override
    public E pool() {
        if(isEmpty()){
            return null;
        }
        E e = arr[head];
        head=(head+1)%arr.length;
        return e;
    }
    @Override
    public E peek() {
        if(isEmpty()){return null;
        }
        return arr[head];
    }
    @Override
    public boolean isEmpty() {
        return tail==head;
    }

    @Override
    public boolean isFull() {
        return (tail+1)%arr.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 e = arr[p];
                p=(p+1)% arr.length;
                return e;
            }
        };
    }

}

4.3.2?环形数组实现2

增加一个size属性，保存全部元素个数，新建数组时大小，判定满和空，添加元素，移除元素做出相应修改。迭代时也应该增加一个count属性。

public class ArrayQueue2<E> implements Queue<E>{
    public static void main(String[] args) {
        ArrayQueue2<Integer> queue=new ArrayQueue2<Integer>(1);
        Integer peek1 = queue.peek();
        boolean empty1 = queue.isEmpty();
        //向尾部添加开始
        boolean offer1 = queue.offer(1);
        boolean offer2 = queue.offer(2);
        //向尾部添加结束
        boolean empty2 = queue.isEmpty();
        Integer peek2 = queue.peek();
        Integer pool1 = queue.pool();
        Integer pool2 = queue.pool();
    }
    private E[] arr;
    private int head=0;
    private int tail=0;
    //元素个数
    private int size=0;
    //抑制警告产生
    @SuppressWarnings("all")
    public ArrayQueue2(int capacity) {
        this.arr = (E[]) new Object[capacity];
    }

    @Override
    public boolean offer(E value) {
        if(isFull()){
            return false;
        }
        arr[tail]=value;
        //防止当前元素时最后一个
        tail=(tail+1)% arr.length;
        size++;
        return true;
    }
    @Override
    public E pool() {
        if(isEmpty()){
            return null;
        }
        E e = arr[head];
        head=(head+1)%arr.length;
        size--;
        return e;
    }
    @Override
    public E peek() {
        if(isEmpty()){return null;
        }
        return arr[head];
    }
    @Override
    public boolean isEmpty() {
        return size==0;
    }
    @Override
    public boolean isFull() {
        return size==arr.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 e = arr[p];
                p=(p+1)% arr.length;
                count++;
                return e;
            }
        };
    }
}

4.3.3?环形数组实现3

基于方式1，做出优化，head和tail一直递增，使用时在进行计算。

当索引超出int最大值会出现索引为负数的问题。

需要单独处理(int) Integer.toUnsignedLong()。?

方法1

public class ArrayQueue3<E> implements Queue<E>{
    public static void main(String[] args) {
        ArrayQueue3<Integer> queue=new ArrayQueue3<Integer>(1);
        Integer peek1 = queue.peek();
        boolean empty1 = queue.isEmpty();
        //向尾部添加开始
        boolean offer1 = queue.offer(1);
        boolean offer2 = queue.offer(2);
        //向尾部添加结束
        boolean empty2 = queue.isEmpty();
        Integer peek2 = queue.peek();
        Integer pool1 = queue.pool();
        Integer pool2 = queue.pool();
    }
    private E[] arr;
    private int head=0;
    private int tail=0;
    //抑制警告产生
    @SuppressWarnings("all")
    public ArrayQueue3(int capacity) {
        this.arr = (E[]) new Object[capacity];
    }

    @Override
    public boolean offer(E value) {
        if(isFull()){
            return false;
        }
        arr[(int) Integer.toUnsignedLong(tail% arr.length)]=value;
        //防止当前元素时最后一个
        tail++;
        return true;
    }

    @Override
    public E pool() {
        if(isEmpty()){
            return null;
        }
        E e = arr[(int) Integer.toUnsignedLong(head% arr.length)];
        head++;
        return e;
    }

    @Override
    public E peek() {
        if(isEmpty()){return null;
        }
        return arr[(int) Integer.toUnsignedLong(head%arr.length)];
    }

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

    @Override
    public boolean isFull() {
        return tail-head== arr.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 e = arr[(int) Integer.toUnsignedLong(p% arr.length)];
                p++;
                return e;
            }
        };
    }
}

方法2

对于求模运算来讲（二进制）：

如果除数是2的n次方，那么被除数的后n为即为余数（模）。

求除数后的n位方法：与2^n-1 按位与

? ? ? 问题：传入数组长度不一定是2^n，可以抛出异常或者转为比入参大最接近的一个2^n次方值，判断一个数是否是2^n可以与该值-1进行按位与，如果结果为0则是2^n，否则则不是。

public class ArrayQueue3_2<E> implements Queue<E>{
    public static void main(String[] args) {
        ArrayQueue3_2<Integer> queue=new ArrayQueue3_2<Integer>(1);
        Integer peek1 = queue.peek();
        boolean empty1 = queue.isEmpty();
        //向尾部添加开始
        boolean offer1 = queue.offer(1);
        boolean offer2 = queue.offer(2);
        //向尾部添加结束
        boolean empty2 = queue.isEmpty();
        Integer peek2 = queue.peek();
        Integer pool1 = queue.pool();
        Integer pool2 = queue.pool();
    }
    private E[] arr;
    private int head=0;
    private int tail=0;
    //抑制警告产生
    @SuppressWarnings("all")
    public ArrayQueue3_2(int capacity) {
        //方式1
        /*if((capacity&capacity-1)!=0){
            throw new IllegalArgumentException("长度必须为2的n次方");
        }*/
        //方法2
        /*
        * 求以2为底capacity的对数+1
        *
        * */
      /*  int res = (int) (Math.log10(capacity-1) / Math.log10(2))+1;
        int i = 1 << res;*/
        capacity-=1;
        capacity|=capacity>>1;
        capacity|=capacity>>2;
        capacity|=capacity>>4;
        capacity|=capacity>>8;
        capacity|=capacity>>16;
        capacity+=1;
        this.arr = (E[]) new Object[capacity];
    }
    @Override
    public boolean offer(E value) {
        if(isFull()){
            return false;
        }
        arr[tail& (arr.length-1)]=value;
        //防止当前元素时最后一个
        tail++;
        return true;
    }
    @Override
    public E pool() {
        if(isEmpty()){
            return null;
        }
        E e = arr[head&(arr.length-1)];
        head++;
        return e;
    }
    @Override
    public E peek() {
        if(isEmpty()){return null;
        }
        return arr[head&(arr.length-1)];
    }
    @Override
    public boolean isEmpty() {
        return tail==head;
    }
    @Override
    public boolean isFull() {
        return tail-head== arr.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 e = arr[p&(arr.length-1)];
                p++;
                return e;
            }
        };
    }
}