Лучшая реализация очереди Java?

Ответ 1

LinkedList, кажется, подходит, LinkedList представляет собой двусвязный список, который подходит для структуры данных Queue (FIFO).

Он поддерживает ссылки на элементы Head и Tail, которые вы можете получить с помощью .getFirst() и .getLast() соответственно.

Вы также можете использовать .push(E e) для добавления элемента в конец очереди и .pop() для удаления из очереди и извлечения последнего элемента очереди.

Ответ 2

Если вы используете LinkedList, будьте осторожны. Если вы используете его следующим образом:

LinkedList<String> queue = new LinkedList<String>();

то вы можете нарушить определение очереди, потому что можно удалить другие элементы, чем сначала (в LinkedList есть такие методы).

Но если вы используете его так:

Queue<String> queue = new LinkedList<String>();

это должно быть хорошо, так как это хедз-ап для пользователей, что вставки должны появляться только сзади и удаления только спереди.

Вы можете преодолеть дефектную реализацию интерфейса Queue, расширив класс LinkedList до класса PureQueue, который выдает UnsupportedOperationException любого из методов оскорбления. Или вы можете принять подход с aggreagation, создав PureQueue только с одним полем, которое является объектом LinkedList типа, списком и единственными методами будет конструктор по умолчанию, конструктор копирования, isEmpty(), size(), add(E element), remove() и element(). Все эти методы должны быть однострочными, например:

/**
* Retrieves and removes the head of this queue.
* The worstTime(n) is constant and averageTime(n) is constant.
*
* @return the head of this queue.
* @throws NoSuchElementException if this queue is empty.
*/
public E remove()
{
    return list.removeFirst();
} // method remove()

Ответ 3

Ознакомьтесь с интерфейсом Deque, который предусматривает вставку/удаление с обоих концов. LinkedList реализует этот интерфейс (как упоминалось выше), но для вашего использования ArrayDeque может быть лучше - вы не понесете стоимость постоянных распределений объектов для каждого node. Опять же, может не иметь значения, какую реализацию вы используете.

Вступает в игру нормальная полиморфность: красота письма против интерфейса Deque, а не какая-либо конкретная реализация, заключается в том, что вы можете очень легко переключать реализации, чтобы проверить, какой из них лучше всего работает. Просто измените строку с new в ней, а остальная часть кода останется прежней.

Ответ 4

Лучше использовать ArrayDeque вместо LinkedList при реализации Stack и Queue в Java. ArrayDeque, скорее всего, будет быстрее, чем интерфейс Stack (в то время как Stack является потокобезопасным) при использовании в качестве стека и быстрее, чем LinkedList при использовании в качестве очереди. Посмотрите на эту ссылку Используйте ArrayDeque вместо LinkedList или Stack.

Ответ 5

Если вы знаете верхнюю границу возможного количества элементов в очереди, круговой буфер быстрее, чем LinkedList, поскольку LinkedList создает объект (ссылку) для каждого элемента в очереди.

Ответ 6

Я думаю, что вы можете с такой простой реализацией

package DataStructures;

public class Queue<T> {

   private Node<T> root;

   public Queue(T value) {
      root = new Node<T>(value);
   }

   public void enque(T value) {
      Node<T> node = new Node<T>(value);
      node.setNext(root);
      root = node;
   }

   public Node<T> deque() {

      Node<T> node = root;
      Node<T> previous = null;

      while(node.next() != null) {
         previous = node;
         node = node.next();
      }
      node = previous.next();
      previous.setNext(null);
      return node;
   }

   static class Node<T> {

      private T value;
      private Node<T> next;

      public Node (T value) {
         this.value = value;
      }

      public void setValue(T value) {
         this.value = value;
      }

      public T getValue() {
         return value;
      }

      public void setNext(Node<T> next) {
         this.next = next;
      }

      public Node<T> next() {
         return next;
      }
   }
}

Ответ 7

Однако, если вы все еще хотите использовать рекурсивный алгоритм, вы можете изменить его как "tail-recursive" , который, вероятно, оптимизирован в JVM, чтобы избежать.

Ответ 8

O (1) доступ к первому и последнему узлам.

class Queue {

private Node head;
private Node end;

public void enqueue(Integer data){

    Node node = new Node(data);
    if(this.end == null){
        this.head = node;
        this.end = this.head;
    }
    else {
        this.end.setNext(node);
        this.end = node;
    }
}

public void dequeue (){

    if (head == end){
        end = null;
    }

    head = this.head.getNext();
}


@Override
public String toString() {
    return head.getData().toString();
}

public String deepToString() {

    StringBuilder res = new StringBuilder();
    res.append(head.getData());

    Node cur = head;
    while (null != (cur = cur.getNext())){
        res.append(" ");
        res.append(cur.getData());

    }
    return res.toString();
}

}

class Node {

private Node next;

private Integer data;


Node(Integer i){
    data = i;
}

public Integer getData() {
    return data;
}

public Node getNext() {
    return next;
}

public void setNext(Node next) {
    this.next = next;
}

}

Ответ 9

Вот реализация очереди с итератором и интерфейсом Iterable

Размер очереди будет увеличиваться по мере заполнения

Интерфейс очереди

package com.practice.ds.queue;

import com.practice.ds.queue.exception.QueueException;

public interface QueueInterface<T> {

    public boolean empty();

    public void enqueue(T item);

    public void dequeue() throws QueueException;

    public T front() throws QueueException;

    public void clear();
}

Класс пользовательских исключений

package com.practice.ds.queue.exception;

public class QueueException extends Exception {

    private static final long serialVersionUID = -884127093599336807L;

    public QueueException() {
        super();
    }

    public QueueException(String message) {
        super(message);
    }

    public QueueException(Throwable e) {
        super(e);
    }

    public QueueException(String message, Throwable e) {
        super(message, e);
    }
}

Реализация очереди

package com.practice.ds.queue;

import java.util.Iterator;

import com.practice.ds.queue.exception.QueueException;

public class Queue<T> implements QueueInterface<T>, Iterable<T> {

    private static final int DEFAULT_CAPACITY = 10;
    private int current = 0;
    private int rear = 0;
    private T[] queueArray = null;
    private int capacity = 0;

    @SuppressWarnings("unchecked")
    public Queue() {
        capacity = DEFAULT_CAPACITY;
        queueArray = (T[]) new Object[DEFAULT_CAPACITY];
        rear = 0;
        current = 0;
    }

    @Override
    public boolean empty() {
        return capacity == current;
    }

    @Override
    public void enqueue(T item) {
        if(full())
            ensureCapacity();
        queueArray[current] = item;
        current++;
    }

    @Override
    public void dequeue() throws QueueException {
        T dequeuedItem = front();
        rear++;
        System.out.println("Dequed Item is " + dequeuedItem);
    }

    @Override
    public T front() throws QueueException {
        return queueArray[rear];
    }

    @Override
    public void clear() {
        for (int i = 0; i < capacity; i++)
            queueArray[i] = null;
        current = 0;
        rear = 0;
    }

    @SuppressWarnings("unchecked")
    private void ensureCapacity() {
        if (rear != 0) {
            copyElements(queueArray);
        } else {
            capacity *= 2;
            T[] tempQueueArray = (T[]) new Object[capacity];
            copyElements(tempQueueArray);
        }
        current -= rear;
        rear = 0;
    }

    private void copyElements(T[] array) {
        for (int i = rear; i < current; i++)
            array[i - rear] = queueArray[i];
        queueArray = array;
    }

    @Override
    public Iterator<T> iterator() {
        return new QueueItearator<T>();
    }

    public boolean full() {
        return current == capacity;
    }

    private class QueueItearator<T> implements Iterator<T> {

        private int index = rear;

        @Override
        public boolean hasNext() {
            return index < current;
        }

        @SuppressWarnings("unchecked")
        @Override
        public T next() {
            return (T) queueArray[index++];
        }
    }

}