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

0

Существует простая схема реализации методов стеков и очередей с помощью операций дека. В частности, имеется простое соответствие методам стекового АТД.

Метод стека ,

Реализация с помощью дека

size()

size()

isEmpty()

isEmpty()

top()

last()

push(e)

insertLast(e)

pop()

removeLastQ

Такое же соответствие существует и для методов очереди:

Метод очереди

Реализация с помощью Дека

size()

size()

isEmpty()

isEmpty()

front()

first()

enqueue(e)

insertLast(e)

bequeue()

removeFirstQ

При реализации класса MyDeque АТД «дек» можно создать интерфейс Stack с помощью класса DequeStack, как показано во фрагменте кода 4.15.

public class DequeStack implements Stack { private Deque D; public DequeStack() { D = new MyDeque();

}

public int size() { return D.size();

}

public boolean isEmpty() { return D.isEmpty();

}

public void push(Object obj) { D.insertLast(obj);

}

public Object top() throws StackEmptyException { try {

return D.last();

}

catch (DequeEmptyException ece) {

throw new tackEmptyExceptionfStack is empty!");

}

}

public Object pop() throws StackEmptyException { try {

return D.removeLast();

}

catch (DequeEmptyException ece) {

throw new StackEmptyExceptionf Stack is empty!");

}

}

}

Фрагмент кода 4.15. Реализация интерфейса Stack на основе дека. Заметьте, что дек генерирует исключение типа DequeEmptyException, а методы top и pop перехватывают это исключение и используют вместо него исключение StackEmptyException

Все методы класса DequeStack являются в сущности однолинейными обращениями к методам интерфейса Deque. Учтите, что некоторые методы этого интерфейса генерируют исключение типа DequeEmptyException при попытке извлечь или удалить элементы пустого дека.

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

По теме:

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