Алгоритмы и структуры данных

АТД: Стек

Стек (Stack) — это абстрактный тип данных, представляющий собой коллекцию элементов, организованных по принципу LIFO.

Принцип LIFO (last in, first out, «последним пришёл — первым ушёл») предпологает, что элементы добавляются и удаляются только с одного конца. Данный принцип применяется в тех случаях, когда последние данные, добавленные в коллекцию, должны быть первыми удалены или обработаны.

Операции на стеке

На стеке должны быть определены следующие основные операции:

  • Push: добавить новый элемент
  • Pop: удаляет и возвращает последний добавленный элемент

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

Все эти операции добавляют и забирают элемент с конца стека, известного как вершина (top) стека.

Пример работы стека

Применение

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

  • Создание стековой машины, вычисляющей выражения, записанные в RPN (Reverse Polish notation) нотации
  • Для обхода графов и деревьев — а конкретно Backtracking (поиск решения с возвратом). Пример такого алгоритма — DFS (Depth-First Search)
  • Для реализации Call Stack — участка памяти треда работающего по принципу LIFO. Помните исключение StackOverflow? Оно как раз появляется когда стековая память треда заканчивается

Имплементация

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

Имплементация с помощью массива

С помощью статического массива мы реализуем ограниченный по размеру стек. Хотя можно реализовать и не ограниченный по размеру стек с помощью динамического массива (в действительности ограниченный размером heap памяти), но здесь мы реализуем специально ограниченный по размеру, чтобы показать ошибку StackOverflow.

Для реализации стека нам необходимо будет хранить индекс последнего добавленного элемента — переменную top,- тем самым мы будем знать, где лежит последний элемент и куда нам необходимо вставить новый элемент. На стадии инициализации значение top равно -1, обозначая пустой стек.

Итак, это наши переменные и конструктор:

    private final E[] a;

    private int top; // индекс последнего добавленного элемента

    private final int arraySize = 64;

    @SuppressWarnings({"unchecked"})
    public ArrayStack() {
        a = (E[]) new Object[arraySize];
        top = -1;
    }

Теперь имплементируем операцию push. Сначала нам надо увеличить переменную top, сдвигая индекс последнего элемента, а затем просто положить в ячейку массива новый элемент, при этом не забывая про переполнение стека:

    public E push(E item) {
        if (++top == arraySize) {
            throw new StackOverflowException();
        }
        a[top] = item;
        return item;
    }

Операция pop также довольно тривиальна. Мы сохраняем в области функции последний добавленный элемент, который находится в ячейке arr[top], уничтожаем ссылку на элемент в ячейке массива, декрементируем переменную top, и возвращаем ранее сохраненный элемент:

    public E pop() {
        if (top == -1) {
            throw new EmptyStackException();
        }
        E elem = a[top];
        a[top] = null; // занулить ссылку, чтобы помочь GC
        --top;
        return elem;
    }

Имплементация с помощью связного списка

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

Заводим переменную для внутреннего списка и определим стадию инициализации в конструкторе:

    private SinglyLinkedList linkedList;

    public LinkedListStack() {
        this.linkedList = new SinglyLinkedList<>();
    }

Операция push — нам всего лишь необходимо положить элемент в начало списка:

    public E push(E item) {
        linkedList.insertFirst(item);
        return item;
    }

Операция pop — удаляем и возвращаем элемент с начала списка:

    public E pop() {
        Node node = linkedList.removeFirst();
        if (node == null) {
            throw new EmptyStackException();
        }
        return node.value;
    }

Имплементации в Java Collections

В Java операции стека предоставляет интерфейс Deque (Double-ended queue — это АТД, который обобщает стек и очередь, вбирая в себе как LIFO, так и FIFO принципы). Основная используемая имплементация данного интерфейса — это ArrayDeque, использующая динамический массив. Также существует реализация на основе двусвязного списка (LinkedList), но как я уже говорил ранее, связные списки в Java почти никто не использует.

АТД: Стек: 3 036 комментариев