Java LinkedList методы для очереди и стека

Question

Если вы посмотрите на методы LinkedList в Java, он предлагает операции для очереди, стека, очереди.

И я знаю, что вы можете реализовать очередь, стек или Deque с помощью LinkedList.Если вы посмотрите на реализацию C #, то Queue и Stack используют массивы.

Мне интересно, почему они предлагают метод push (T e) для связанного списка?

Почему Queue и Stack не являются отдельными классами, как C #.

Ниже приведен код для push и pop, который звучит как дух.Но почему?

public void push(Object obj)
{
    addFirst(obj);
}

public Object pop()
{
    return removeFirst();
}

Если вы посмотрите на HashMap или HashSet, он использует массив внутри, и есть LinkedHashSet и map соответственно для поддержания порядка.

Это не совсем сбивает с толку, но на самом деле это не имеет смысла.

Почему java имеет такую ​​реализацию?

Answer 1

Фокус на реализации структуры данных:

Связанный список эффективен для частого добавления и удаления.(как обычно делают Queue и Stack, и итерационные операции выполняются редко).Массива нет, ему нужна операция копирования массива, которая занимает много времени .

Answer 2

Двойной связанный список, такой как Java LinkedList, является довольно гибкой структурой данных, поэтому имеет смысл реализовать несколько структур данных, используя его в качестве основы. Поэтому, если вы хотите просмотреть его как очередь, вы должны сказать что-то вроде этого (я опускаю параметры типа):

Queue q = new LinkedList();

Если вы хотите использовать его в качестве стека, вы должны объявить его так:

Deque s = new LinkedList();

И так далее. В конце концов, все сводится к повторному использованию кода, зачем реализовывать несколько разных классов для аналогичной функциональности, когда достаточно одного класса (в данном случае LinkedList)?

Answer 3

Basic OOD: хотя, возможно, нечеткая строка, Queue, Stack и Deque приблизительно описывают операции, которые вы можете выполнять над коллекцией, и, следовательно, заслуживаете того, чтобы быть интерфейсами.LinkedList описывает реализацию и характеристики производительности интерфейса и, следовательно, заслуживает того, чтобы быть классом.Эта реализация может быть (представлена) как несколько интерфейсов.Для меня реальный вопрос: «Почему Stack - это класс?»

Answer 4

LinkedList реализует интерфейс Queue, поскольку вы можете использовать связанный список в качестве очереди в некоторых местах. Это означает, что метод, который принимает очередь в качестве входного параметра, также может обрабатывать связанные списки. Следующие работы

List<String> linkedList = new LinkedList<String>();
linkedList.add("element1");
linkedList.add("element2");

Queue<String> q = (Queue<String>)linkedList; 
q.poll(); //removes and returns element1 from the linkedList

Java имеет отдельный класс, называемый java.util.Stack, который расширяется от вектора, который, в свою очередь, является реализацией на основе массива. Но это потокобезопасная версия. Если вас не беспокоит безопасность потоков, вы можете использовать ArrayDeque в качестве стека.

Answer 5

Очередь является интерфейсом и имеет другие реализации, помимо LinkedList.Есть также класс Stack.

В конечном счете, это просто кажется произвольным решением, и базовая реализация на самом деле не имеет большого значения (IMO).