Класс стека

Давайте рассмотрим менее тривиальный пример: реализацию традиционного стека. В главе 11 была приведена реализация стека на базе LinkedList. В этом примере класс LinkedList уже содержал все методы, необходимые для создания стека. Класс стека строился объединением одного параметризованного класса (Stack<T>) с другим параметризованным классом (LinkedList<T>). Этот пример показывает, что параметризованный тип — такой же тип, как и все остальные (за некоторыми исключениями, о которых речь пойдет позже):- Вместо того, чтобы использовать LinkedList, мы также могли реализовать собственный механизм хранения связанного списка:

//: generics/LinkedStack.java

// Стек, реализованный на базе внутренней структуры

public class LinkedStack<T> {

private static class Node<U> {

U item;

Node<U> next;

Node() { item = null; next = null; }

Node(U item, Node<U> next) {

this.item = item;

this.next = next;

}

boolean end() { return item == null && next == null; }

}

private Node<T> top = new Node<T>(); // Предохранитель

public void push(T item) {

top = new Node<T>(item, top);

}

public T pop() {

T result = top.item;

if(!top.end())

top = top.next;

return result;

}

public static void main(String[] args) {

LinkedStack<String> lss = new LinkedStack<String>();

for(String s : "Phasers on stun!".split(" "))

lss.push(s);

String s;

while((s = lss.pop()) != null)

System.out.println(s);

}

}

<spoiler text="Output:">

stun!

on

Phasers

</spoiler> Внутренний класс Node тоже является параметризованным и имеет собственный параметр типа. Для определения наличия элементов в стеке в этом примере используется предохранитель (end sentinel). Он создается при конструировании LinkedStack, а затем при каждом вызове push() новый объект Node<T> создается и связывается с предыдущим Node<T>. При вызове рор() всегда возвращается top.item, после чего текущий объект Node<T> уничтожается и происходит переход к следующему — если только текущим элементом не является предохранитель; в этом случае переход не выполняется. При повторных вызовах рор() клиент будет получать null, что свидетельствует об отсутствии элементов в стеке.