Главная » Java, Структуры данных и алгоритмы » Реализация стека на основе однонаправленного связного списка

0

 

Рассмотрим использование однонаправленного связного списка для реализации стекового АТД. В принципе, вершина стека может находиться как в начале, так и в конце списка. С другой стороны, так как добавление и удаление элементов за время 0(1) возможно только в начале списка, именно здесь более эффективно определить вершину стека. Кроме того, для выполнения операции size за время 0(1) контролировать текущее число элементов будем с помощью переменной экземпляра. представлена фрагментом кода 4.11. Все методы интерфейса Stack выполняются за время 0(1).

Кроме экономии времени, данная реализация определяет занимаемое стеком пространство, равное 0(п), где п — текущее число элементов стека. Таким образом, размер используемого места зависит от числа элементов в стеке, а не от задаваемого предела. Кроме того, данная реализация не требует создания нового исключения при превышении задаваемого предела. Вместо этого исполняющая среда будет рассматривать в целом, превысит ли реализация выделенный размер памяти, что приведет к возникновению ошибки OutOfMemoryError (различия между исключениями и ошибками рассмотрены в разделе 2.3). Таким образом, реализация стека на основе однонаправленного связного списка имеет существенное преимущество по сравнению с реализацией на основе массива — не требуется явно устанавливать максимальный размер стека.

Используем переменную ссылочного типа top для обращения к началу списка (имеет нулевое значение при пустом списке). При добавлении в стек нового элемента е создается новый узел v, из v устанавливается ссылка на е, и v добавляется в начало списка. Аналогично при извлечении элемента из стека узел удаляется из начала списка и возвращается его элемент. Таким образом выполняются все добавления и удаления элементов в начале списка.

public class LinkedStack implements Stack {

private Node top; // обращается к головному узлу private int size  // число элементов стека

public LinkedStack() { // инициализирует пустой стек top = null; size = 0;

}

public int size() { return size;

}

public boolean isEmptyO { if (top == null) return true; return false;

}

public void push(Object elem) {

Node v = new Node(); // создает новый узел v.setElement(elem);

v.setNext(top);                                            // связывает новый узел

top = v;

size++;

}

public Object top() throws StackEmptyException { if (isEmptyO)

throw new StackEmptyExceptionfStack is empty."); return top.getElement();

}

public Object pop() throws StackEmptyException { if (isEmptyO)

throw new StadkEmptyExceptionf Stack is empty."); Object temp = top.getElement();

top = top.getNextQ; // перенаправляет предыдущий верхний узел size —; return temp;

}

}

Фрагмент кода 4.11. Класс LinkedStack, реализующий интерфейс Stack на основе однонаправленного связного списка. Узлами списка являются объекты класса Node, представленного во фрагменте кода 4.10

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии