java - 一个快速插入、删除和获取前端元素的先进先出队列java

Question

我应该在 java 中使用哪种数据结构来实现队列在末尾快速插入、从前面删除并获取第一个元素的操作？

Answer 1

不合算LinkedList吗？

其实施

public E remove() {
    return removeFirst();
}

public boolean add(E e) {
    linkLast(e);
    return true;
}

它同时具有first和last节点，因此插入速度很快。您可以使用方法从前面删除remove()。您也可以获得第一个元素，即。peek()返回first节点。那也是O(1)。

资源

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

Answer 2

LinkedBlockingQueue does the job. take() to fetch put() to insert.

If your queue is a fixed size, ArrayBlockingQueue will be more efficient.

Or, if you must implement a fast fixed-size queue yourself:

public class Queue<T> {
    private T[] q;
    private int head = 0;
    private int tail = 0;
    private int used = 0;
    private int size;

    @SuppressWarnings("unchecked")
    public Queue(int size) {
        q = (T[]) new Object[size];
        this.size = size;
    }
    public synchronized void put(T o) throws InterruptedException {
        while(isFull()) {
            wait();
        }
        q[head] = o;
        head = (head+1) % size;
        used++;
        notifyAll();
    }
    public synchronized T take() throws InterruptedException {
        while(isEmpty()) {
            wait();
        }
        T result = q[tail];
        tail = (tail+1) % size;
        used--;
        notifyAll();
        return result;
    }
    public synchronized boolean isEmpty() { return used == 0; }
    public synchronized boolean isFull() { return used == size; }
}