/**
 * 数据对象: D=(ai/ai属于ElemSet, 121.2..... n>=0}
 * 数据关系: R1=(<ai-1,ai>)ai-1, ai属于D, i=2..... n)
 * 约定a1端为队列头, an端为队列尾。
 */
ADT Queue {
    //基本操作
    InitQueue( & Q) // 操作结果: 构造 - 个空队列Q.
    QueueEmpty(Q) // 初始条件: 队列Q已存在   操作结果若队列Q为空栈则返回TRUE, 否则FALSE
    EnQueue( & Q e) // 初始条件:队列Q已存在  操作结果:插入元素e为Q的新队尾元素
    DeQueue( & Q & e) // 初始条件:队列Q已存在且非空    操作结果:删除Q的队头元素, 井用e返回其值
    GetHead(Q & e) // 初始条件: 队列Q非空   操作结果: 用e返回Q的对头元素
    DestroyQueue( & Q) // 初始条件:队列Q已存在   操作结果:队列Q被销毁
    ClearQueue( & Q) // 初始条件:队列Q已存在    操作结果:队列Q清为空栈
    Queuelength(Q)  // 初始条件: 队列Q已存在    操作结果: 返回Q的元素个数, 即队列的长度
    QueueTraverse (S, visit()) // 初始条件:队列Q已存在并非空   操作结果:从队头到队尾, 依次对Q的每个数据元素调用函数visit) ,一旦visit()失败, 则返回操作失败。
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 *
 * @author macfmc
 * @date 2020/6/3-15:34
 */
public class MyQueue {
    LinkedList<Integer> A, B;
    public CQueue() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }
    public void appendTail(int value) {
        A.addLast(value);
    }
    public int deleteHead() {
        if(!B.isEmpty()) return B.removeLast();
        if(A.isEmpty()) return -1;
        while(!A.isEmpty())
            B.addLast(A.removeLast());
        return B.removeLast();
    }
}

public class MyQueue {
    // 因为Stack继承自Vector，Vector底层是elementData的Object类型的数组
    Stack<Integer> s1 = new Stack<Integer>();
    Stack<Integer> s2 = new Stack<Integer>();
    public void appendTail1(int value) {
        s1.push(value);
    }
    public int deleteHead1() {
        if (s2.isEmpty()) {
            if (s1.isEmpty())
                return -1;
            while (!s1.isEmpty())
                s2.push(s1.pop());
        }
        return s2.pop();
    }
}

class CQueue {
    Integer[] queue = new Integer[16];
    int headInt = 0;
    int endInt = 0;
    double threshold = 0.75;
    public void appendTail(int value) {
        // 是否扩容
        if (queue.length * threshold < endInt) {
            queue = addLengthArray(queue, headInt, endInt);
        }
        queue[endInt] = value;
        ++endInt;
    }
    public int deleteHead() {
        int result = 0;
        if (queue[headInt] != null) {
            result = queue[headInt];
            queue[headInt] = null;
        } else
            return -1;
        ++headInt;
        return result;
    }
    public Integer[] addLengthArray(Integer[] array, int headInt, int endInt) {
        Integer[] newArray = new Integer[array.length * 2];
        //将array数组从headInt位置至endInt位置，复制到newArray数组0位置到endInt - headInt位置。
        for (int i = headInt,j = 0; i <= endInt; i++) {     //复制
            newArray[j] = array[i];
            j++;
        }
        this.endInt = endInt-headInt;
        this.headInt = 0;
        return newArray;
    }
}

/**
 * 循环队列
 *
 * @author macfmc
 * @date 2020/6/4-11:56
 */
public class CycQueue<T> {
    int[] queue = null;
    int front = 0;
    int rear = 0;
    boolean empty = true; //true表示循环队列为空
    // 构造指定大小的循环队列
    CycQueue(int max) {
        this.queue = new int[max];
    }
    // 清空循环队列
    public void clearQueue() {
        this.front = 0;
        this.rear = 0;
        this.empty = true;
    }
    // 检测循环队列是否为空
    public boolean queueEmpty() {
        if (this.empty == true) {
            return true;
        } else {
            return false;
        }
    }
    // 返回循环队列的元素个数
    public int queueLength() {
        if (this.front == this.rear && this.empty == false) {
            return this.queue.length;  //如果循环队列已满，返回数组长度即元素个数
        }
        return (this.rear - this.front + this.queue.length) % this.queue.length;   //否则，取模运算得到长度
    }
    // 向队尾插入元素
    public boolean enQueue(int value) {
        if (this.empty == false && this.front == this.rear) {
            return false;
        }
        this.queue[this.rear] = value;
        this.rear = (this.rear + 1) % this.queue.length;
        this.empty = false;
        return true;
    }
    // 返回对头
    private int[] getHead() {
        if (this.empty == true) {
            return null;
        }
        int[] i = new int[1];
        i[0] = this.queue[this.front];  //获取队头元素
        return i;
    }
    // 删除并返回队头元素
    public int[] deQueue() {
        if (this.empty == true) {
            return null;
        }
        int[] i = new int[1];
        i[0] = this.queue[this.front];  //获取队头元素
        this.front = (this.front + 1) % this.queue.length;  //删除队头元素（front指针加一）
        if (this.front == this.rear) {   //如果循环队列变空，改变标志位
            this.empty = true;
        }
        return i;
    }
    // 遍历循环队列
    public String queueTraverse() {   //此处用输出循环队列表示遍历
        String s = "";
        int i = this.front;   //i指向第一个元素
        if (this.front == this.rear && this.empty == false) {   //如果循环队列已满，取出第一个元素，i指向下一个元素
            s += this.queue[i] + "、";
            i = (i + 1) % this.queue.length;
        }
        while (i != this.rear) {   //如果未到末尾，则循环读取元素
            s += this.queue[i] + "、";
            i = (i + 1) % this.queue.length;
        }
        if (s.length() == 0) {   //如果没有读取到元素，直接返回空字符串
            return s;
        }
        return s.substring(0, s.length() - 1);   //除去最后的顿号返回
    }
}

// ArratDeque源码-主要的插入和提取方法有addFirst、addLast、pollFirst、pollLast。其他方法是根据这些定义的。
    // The main insertion and extraction methods are addFirst,addLast, pollFirst, pollLast. The other methods are defined in terms of these.
    /**
     * Inserts the specified element at the end of this deque.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws NullPointerException if the specified element is null
     */
    public boolean add(E e) {
        addLast(e);
        return true;
    }
    /**
     * Inserts the specified element at the end of this deque.
     *
     * <p>This method is equivalent to {@link #add}.
     *
     * @param e the element to add
     * @throws NullPointerException if the specified element is null
     */
    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }
    /**
     * Doubles the capacity of this deque.  Call only when full, i.e.,
     * when head and tail have wrapped around to become equal.
     */
    private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }
    public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // Element is null if deque empty
        if (result == null)
            return null;
        elements[h] = null;     // Must null out slot
        head = (h + 1) & (elements.length - 1);
        return result;
    }
    public E pollLast() {
        int t = (tail - 1) & (elements.length - 1);
        @SuppressWarnings("unchecked")
        E result = (E) elements[t];
        if (result == null)
            return null;
        elements[t] = null;
        tail = t;
        return result;
    }

/**
     * 将指定的元素插入此优先级队列-Inserts the specified element into this priority queue.
     *
     * @return {@code true} (as specified by {@link Queue#offer})
     * @throws ClassCastException if the specified element cannot be
     *         compared with elements currently in this priority queue
     *         according to the priority queue's ordering
     * @throws NullPointerException if the specified element is null
     */
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }
    /**
     * 从此队列中移除的元素o
     * Version of remove using reference equality, not equals.
     * Needed by iterator.remove.
     *
     * @param o element to be removed from this queue, if present
     * @return {@code true} if removed
     */
    boolean removeEq(Object o) {
        for (int i = 0; i < size; i++) {
            if (o == queue[i]) {
                removeAt(i);
                return true;
            }
        }
        return false;
    }

private final BlockingQueue<Runnable> workQueue; //阻塞队列
private final ReentrantLock mainLock = new ReentrantLock() ; //互斥锁
private final HashSet<Worker> workers = new HashSet<Worker>(); //线程集合.一个Worker对应一个线程
private final Condition termination = mainLock.newCondition(); //終止条件
private int largestPoolSize; // 线程池中线程数量曾经达到过的最大值。
private long completedTaskCount; //已完成任务数量
private volatile ThreadFactory threadFactory;// ThreadFactory对象，用于创建线程。
private volatile RejectedExecutionHandler handler ;//拒绝策略的处理句柄
private volatile long keepAliveTime; // 线程池维护线程所允许的空闲时间
private volatile boolean allowCore ThreadTimeOut;
private volatile int corePoolSize; //线程池维护线程的最小数量，哪怕是空闲的
private volatile int maximumPoolSize; // 线程池维护的最大线程数量