Реализовать типизированный безразмерный Stack

82. Реализовать типизированный безразмерный Stack

Условие задачи:
Необходимо самостоятельно реализовать структуру данных Stack без использования стандартных коллекций Java.

Требования:

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

Спойлеры к решению

Подсказки

💡 Стек работает по принципу LIFO: последний добавленный элемент извлекается первым.
💡 Для безразмерного стека удобно использовать собственные связанные узлы.
💡 Каждый узел должен хранить значение и ссылку на предыдущий узел.
💡 Для push() и pop() не требуется обходить весь стек.

Решение

public class Stack<T> {

    private Node<T> top;
    private int size;

    public void push(T value) {
        top = new Node<>(value, top);
        size++;
    }

    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException(
                    "Stack is empty"
            );
        }

        T value = top.value;
        top = top.previous;
        size--;

        return value;
    }

    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException(
                    "Stack is empty"
            );
        }

        return top.value;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public int size() {
        return size;
    }

    private static class Node<T> {

        private final T value;
        private final Node<T> previous;

        private Node(
                T value,
                Node<T> previous
        ) {
            this.value = value;
            this.previous = previous;
        }
    }
}

Пример использования:

public static void main(String[] args) {
    Stack<String> stack = new Stack<>();

    stack.push("one");
    stack.push("two");
    stack.push("three");

    System.out.println(stack.peek());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.size());
}

Результат:

three
three
two
1

При push() новый узел становится вершиной стека и хранит ссылку на предыдущую вершину:

three
  ↓
two
  ↓
one

При pop() вершина удаляется, а top начинает указывать на предыдущий узел.

Сложность основных операций:

push() — O(1);
pop() — O(1);
peek() — O(1);
isEmpty() — O(1);
size() — O(1).

Дополнительная память — O(n).