java - 高速挿入、削除、フロント要素 java の取得を備えた FIFO キュー

Question

end での高速挿入、front からの削除、および最初の要素の操作を取得するキューを実装するには、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がその役割を果たします。 take()フェッチput()して挿入します。

キューが固定サイズの場合、ArrayBlockingQueueはより効率的になります。

または、高速な固定サイズのキューを自分で実装する必要がある場合:

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