Java-реализация для стека

Question

Есть ли в Java класс, который реализует концепцию стека из книг структуры данных, означает LIFO, pop is O (1) и push в O (1)?

Я немного прочитал кодjava.util.Stack и не похоже, что push - это O (1) - push может вызвать Vector.grow (), и он может принять O (n) (я знаю, что это амортизированный O (1)но я ищу всегда вставлять O (1))

И я хочу понять, почему java.util.Stack был разработан как есть, а не как теоретический принцип стека

Answer 1

ArrayDeque предпочтительно LinkedList.

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

Согласно Джошу Блоху, автору LinkedList, в твитах :

Кто-нибудь на самом деле использует LinkedList? Я написал это, и я никогда не использую это.

и

ArrayDeque создает отличный стек, очередь или дек

Answer 2

Вы можете использовать LinkedList или ArrayDeque, которые реализуют интерфейс Deque, и этот интерфейс имеет стековые методы pop и push. Поскольку LinkedList и ArrayDeque реализуют этот интерфейс, мы можем использовать их, как если бы мы использовали Stack.

Из документов Deque:

Запросы также можно использовать в качестве стеков LIFO (Last-In-First-Out). Этот интерфейс следует использовать предпочтительнее унаследованного класса Stack. Когда в качестве стека используется deque, элементы выталкиваются и выталкиваются с начала deque.

Итак, как вы можете видеть, реализации Deque должны быть предпочтительнее, чем устаревшие Stack класс.

Answer 3

Стек или очередь могут быть реализованы с помощью Linkedlist.

pop (): удалить верхний элемент из стека.

push (): добавление элемента на вершину стека.

public class MyStack<T> {

   private StackNode<T> top;
    private static class StackNode<T> {

        private T data;
        private StackNode<T> next;

        public StackNode(T data) {
            this.data = data;
        }
    }

    public T pop() {
        if (top == null) throw new EmptystackException();
        T item = top.data;
        top = top.next;
        return item;
    }

    public void push(T item) {

        StackNode<T> t = new StackNode<T>(item);
        t.next = top;
        top = t;
    }
}

Answer 4

ТЛ; др

• Избегайте Stack.
• Использование LinkedList.

Stack теперь является устаревшим кодом

Класс java.util.Stack теперь legacy , выходящий из другого унаследованного класса, java.util.Vector. Вы не должны использовать эти классы. И при этом вы не должны изучать их как блестящие примеры.

Java Collections Framework

Оба эти класса были вытеснены два десятилетия назад Java Collections Framework .

Для поведения LIFO вы должны обратить внимание на классы, которые реализуют интерфейсы очереди и deque .

Интерфейс java.util.Queue реализован во многих классах, связанных с Java.

• AbstractQueue
• ArrayDeque
• ConcurrentLinkedDeque
• ConcurrentLinkedQueue
• DelayQueue
• LinkedBlockingDeque
• LinkedBlockingQueue
• LinkedList
• LinkedTransferQueue
• PriorityBlockingQueue
• PriorityQueue
• SynchronousQueue

Коллекции LIFO можно найти в других библиотеках сторонних разработчиков, например, Google Guava .

LinkedList

Как уже упоминалось, первое, что нужно рассмотреть, это LinkedList для поведения O (1), как обсуждено на Как LinkedList добавляет (int, E) O (1) сложность? .