队列

package com.hshuo;

/**
 * 数组实现可变长度的队列
 * @author SHshuo
 * @data 2022/2/26--11:39
 */
public class arrayToVolatileQueue {

    private int front;
    private int rear;
    private int length;
    private int[] arr;

    public arrayToVolatileQueue(int capicity){
        length = 0;
        front = 0;
        rear = 0;
        arr = new int[capicity];
    }

    private void resize(int capicity){
        int[] res = new int[capicity];
//        数据迁移时间复杂度为O(n)通过均摊，整体的add、get的时间复杂度仍为O（1）
        System.arraycopy(arr, front, res, 0, rear - front + 1);

//        重置
        rear -= front;
        front = 0;
        arr = res;
    }

    public void add(int value){
        arr[rear++] = value;
        length++;

//        超过数组长度的一半进行扩容
        if(length > 0 && length > arr.length / 2){
            resize(arr.length * 2);
        }
    }

    public int remove(){
        if(length == 0){
            throw new RuntimeException("队列空了，不能再拿了");
        }
        int ans = arr[front++];
        length--;
        if(length > 0 && length < arr.length / 4){
            resize(arr.length / 2);
        }
        return ans;
    }

    public void allData(){
        if(length == 0){
            throw new RuntimeException("队列空了");
        }

        for(int i = front; i < rear; i++){
            System.out.println("i: " + i + "arr: " + arr[i]);
        }
    }

    public static void main(String[] args) {
        arrayToVolatileQueue queue = new arrayToVolatileQueue(6);
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.remove();
        queue.add(4);
        queue.allData();
        queue.add(5);
        queue.add(6);
        queue.add(6);
        queue.add(6);

    }
}

• 数组要预留一处空间，如果容量是capicity则实际空间是capicity - 1；
• 队列已满条件：（rear + 1）% capicity == front;
• 队列已空条件：front == rear；
• 指针增加：front = （front + 1）% capicity 或者 rear= （rear+ 1）% capicity ；
• 数组的有效长度：（capicity + rear - front）% capicity；
• 数组的下标：i % capicity；

package com.hshuo;

/**
 * 数组转化为固定大小的队列、重复利用数组空间，每次都要取模
 * 数组要预留一处空间，如果容量是capicity则实际空间是capicity - 1
 * @author SHshuo
 * @data 2022/2/26--9:50
 */
public class arrayToQueue {
//    数组
    private int[] arr;
    private int front;
    private int rear;
    private int capicity;


//    初始化队列
    public arrayToQueue(int capicity){
        this.capicity = capicity;
        front= 0;
        rear = 0;
        arr = new int[capicity];
    }

//    对列已满的条件
    private boolean isFull(){
        return (rear + 1) % capicity == front;
    }

//    队列已空的条件
    private boolean isEmpty(){
        return rear == front;
    }


    public void add(int value){
        if(isFull()){
            throw new RuntimeException("队列满了，不能再加了");
        }
        arr[rear] = value;
//        rear++需要取模
        rear = (rear + 1) % capicity;
    }


    public int remove(){
        if(isEmpty()){
            throw new RuntimeException("队列空了，不能再拿了");
        }
        int ans = arr[front];
        System.out.println("移除的元素是：" + ans);
//        front++需要取模
        front = (front + 1) % capicity;
        return ans;
    }

//    有效长度
    public int size(){
        if(isEmpty()){
            return 0;
        }
        return (capicity + rear - front) % capicity;
    }

//    返回所有数据
    public void allData(){
        if(isEmpty()){
            throw new RuntimeException("队列空了");
        }

        for(int i = front; i < front + size(); i++){
            System.out.println("i: " + i % capicity + "arr: " + arr[i % capicity]);
        }
    }

    public static void main(String[] args) {
        arrayToQueue queue = new arrayToQueue(6);
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(5);
        queue.remove();
        queue.add(6);
        queue.allData();
    }

}

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();
    }

public void put(E e) throws InterruptedException {
        checkNotNull(e);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (count == items.length)
                notFull.await();
            enqueue(e);
        } finally {
            lock.unlock();
        }
    }

public E take() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (count == 0)
                notEmpty.await();
            return dequeue();
        } finally {
            lock.unlock();
        }
    }