双端队列、队列

队列的最大值

public class MaxQueue {

    Queue<Integer> queue;
    Deque<Integer> help; // 使用双端队列, 维护queue的单调序列

    public MaxQueue() {
        queue = new LinkedList<>();
        help = new LinkedList<>();
    }

    public int max_value() {
        if (help.isEmpty()) {
            return -1;
        }
        return help.peekFirst();
    }

    public void push_back(int value) {
        queue.offer(value);
        // 辅助队列保持从大到小, 相等的元素也要保留
        while (!help.isEmpty() && value > help.peekLast()) {
            help.removeLast();
        }
        help.addLast(value);
    }

    // 如果常规队列是空就返回-1, 不然正常返回, 辅助队列需要判断是否是最大值, 是的话就要删除, 但不影响相同最大值
    public int pop_front() {
        if (queue.isEmpty()) {
            return -1;
        }
        int e = queue.remove();
        if (e == help.peekFirst()) {
            help.removeFirst();
        }
        return e;
    }

}

---

按递增顺序显示卡牌

模拟

    public int[] deckRevealedIncreasing(int[] deck) {
        int N = deck.length;
        Deque<Integer> index = new LinkedList();
        for (int i = 0; i < N; ++i)
            index.add(i);

        int[] ans = new int[N];
        Arrays.sort(deck);
        for (int card: deck) {
            ans[index.pollFirst()] = card;
            if (!index.isEmpty())
                index.add(index.pollFirst());
        }

        return ans;
    }

---

设计有限阻塞队列

public class BoundedBlockingQueue {

    private int capacity;
    private Queue<Integer> queue;

    public BoundedBlockingQueue(int capacity) {
        this.capacity = capacity;
        this.queue = new LinkedList<>();
    }

    public void enqueue(int element) throws InterruptedException {
        synchronized (queue){
            while (queue.size() == this.capacity){
                queue.wait();
            }
            queue.add(element);
            queue.notifyAll();
        }
    }

    public int dequeue() throws InterruptedException {
        synchronized (queue){
            while (queue.size() == 0){
                queue.wait();
            }
            int ans = queue.poll();
            queue.notifyAll();
            return ans;
        }
    }

    public int size() {
        return queue.size();
    }

}

---