Node в LinkedList. Реализация псевдокода на Java

Question

Как понять что обозначает этот псевдокод? Какова его реализация на Java? Node и Stack в данном случае - это классы? А head переменная?

Node:
  value - значение в обёртке
  prev - элемент, ниже в стеке

Stack:
  head - указатель на обёртку с элементом, который надо вынуть следующим.

Answer 1

Это классы, то что описано в них - это поля классов.

На псевдокоде Java эти классы можно описать так (это в принципе валидный код, но на Java принято делать поля приватными, плюс для работы стека нужна как минимум реализация добавления/удаления элементов):

class Node<T> {
    T value;
    Node<T> prev;
}

class Stack<T> {
    Node<T> head;
}

T - generic тип для объектов, хранящихся в узлах.

Простейшая реализация:

public static class Node<T> {
    private final T value;
    private final Node<T> prev;

    public Node(T value, Node<T> prev) {
        this.value = value;
        this.prev = prev;
    }

    public T getValue() {
        return value;
    }

    public Node<T> getPrev() {
        return prev;
    }
}

public static class Stack<T> {
    private Node<T> head;

    /**
     * Метод для проверки, что список пустой
     */
    public boolean isEmpty() {
        return head == null;
    }

    /**
     * Добавить значение в стек: создаем узел,
     * кладем в него значение и старую голову списка,
     * делаем этот узел головой списка
     */
    public void push(T value) {
        head = new Node<>(value, head);
    }

    /**
     * Вытащить значение из стека и вернуть его из метода.
     * Если стек пустой, бросаем исключение
     * (используем готовый класс исключения java.util.EmptyStackException)
     */
    public T pop() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        }

        T value = head.getValue();  // Достаем значение из головы
        head = head.getPrev();  // Головой становится предыдущий элемент в стеке
        return value;  // Возвращаем значение
    }
}

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

Stack<Integer> stack = new Stack<>();

// Добавляем в стек значения
for (int i=0; i < 10; i++) {
    stack.push(i);
}

// Вытаскиваем и печатаем значения, пока стек не станет пустым
while (!stack.isEmpty()) {
    System.out.println(stack.pop());
}

// Или такой цикл (остановка цикла через отлов исключения):
while (true) {
    try {
        System.out.println(stack.pop());
    } catch (EmptyStackException ex) {
        break;
    }
}

Вывод:

БЛОГ НА HUSL

Node в LinkedList. Реализация псевдокода на Java

Ответы (1 шт):