队列 Queue

public class ArrayQueue<E> {
    private ArrayList<E> data = new ArrayList<>();

    public void enqueue(E e) { data.add(e); }

    public E dequeue() {
        if (data.isEmpty()) throw new NoSuchElementException();
        return data.remove(0);     // ❌ O(n)
    }
}

public class LoopQueue<E> {
    private E[] data;
    private int front, tail, size;

    @SuppressWarnings("unchecked")
    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity];
        front = tail = size = 0;
    }

    public void enqueue(E e) {
        if (size == data.length) resize(data.length * 2);
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    public E dequeue() {
        if (isEmpty()) throw new NoSuchElementException();
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        if (size <= data.length / 4 && data.length > 1) resize(data.length / 2);
        return ret;
    }

    public E getFront() {
        if (isEmpty()) throw new NoSuchElementException();
        return data[front];
    }

    public int getSize() { return size; }
    public boolean isEmpty() { return size == 0; }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }
}

public class LinkedQueue<E> {
    private Node<E> head, tail;
    private int size;

    private static class Node<E> { E val; Node<E> next; Node(E v) { val = v; } }

    public void enqueue(E e) {
        Node<E> node = new Node<>(e);
        if (tail == null) head = tail = node;
        else { tail.next = node; tail = node; }
        size++;
    }

    public E dequeue() {
        if (head == null) throw new NoSuchElementException();
        E v = head.val;
        head = head.next;
        if (head == null) tail = null;
        size--;
        return v;
    }
}

Deque<Integer> dq = new ArrayDeque<>();
dq.offerFirst(1);     // 队首入队
dq.offerLast(2);      // 队尾入队
dq.pollFirst();       // 队首出队
dq.pollLast();        // 队尾出队

PriorityQueue<Integer> minPQ = new PriorityQueue<>();        // 最小堆
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a, b) -> b - a);  // 最大堆

BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(1024);
queue.put(1);           // 满时阻塞
int x = queue.take();   // 空时阻塞

void bfs(Node start) {
    Deque<Node> q = new ArrayDeque<>();
    Set<Node> visited = new HashSet<>();
    q.offer(start); visited.add(start);
    while (!q.isEmpty()) {
        Node u = q.poll();
        for (Node v : u.neighbors) {
            if (!visited.contains(v)) {
                visited.add(v);
                q.offer(v);
            }
        }
    }
}

class MyStack {
    Deque<Integer> q = new ArrayDeque<>();

    public void push(int x) {
        q.offer(x);
        for (int i = 1; i < q.size(); i++) q.offer(q.poll());
    }

    public int pop() { return q.poll(); }
    public int top() { return q.peek(); }
    public boolean empty() { return q.isEmpty(); }
}

class MyCircularQueue {
    int[] data;
    int front, tail, size;

    public MyCircularQueue(int k) {
        data = new int[k];
    }

    public boolean enQueue(int v) {
        if (size == data.length) return false;
        data[tail] = v;
        tail = (tail + 1) % data.length;
        size++;
        return true;
    }

    public boolean deQueue() {
        if (size == 0) return false;
        data[front] = 0;
        front = (front + 1) % data.length;
        size--;
        return true;
    }

    public int Front() { return size == 0 ? -1 : data[front]; }
    public int Rear() { return size == 0 ? -1 : data[(tail - 1 + data.length) % data.length]; }
    public boolean isEmpty() { return size == 0; }
    public boolean isFull() { return size == data.length; }
}