Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

63
Стеки
Алгоритм.поиска.в.глубину.опирается.на.структуру.данных,.известную.как.
стек
..(Если.вы.читали.о.стеках.в.главе.1,.можете.спокойно.пропустить.этот.раз-
дел.).Стек.—.это.структура.данных,.которая.работает.по.принципу.«последним.
пришел.—.первым.вышел».(last-in-first-out,.LIFO)..Стек.можно.представить.
как.стопку.документов..Последний.документ,.помещенный.сверху.стопки,.
будет.первым,.который.оттуда.извлекут..Обычно.стек.реализуется.на.основе.
более.примитивной.структуры.данных,.такой.как.список.(добавление.элемен-
тов.в.начало.списка.и.удаление.элементов.в.его.конце)..Мы.могли.бы.легко.
реализовать.стек.самостоятельно,.но.стандартная.библиотека.Java.содержит.
удобный.класс.
Stack
.
Обычно.стек.имеет.минимум.две.операции:
.
push()
.—.помещает.элемент.в.вершину.стека;
.
pop()
.—.удаляет.элемент.из.вершины.стека.и.возвращает.его.
Другими.словами,.стек.—.это.метаструктура,.обеспечивающая.порядок.удаления.
в.списке..Последний.элемент,.помещенный.в.стопку,.должен.быть.следующим.
элементом,.удаленным.из.стопки.
Алгоритм DFS
Понадобится.учесть.еще.один.момент,.прежде.чем.можно.будет.приступить.
к.реализации.DFS..Требуется.класс.
Node
,.с.помощью.которого.мы.станем.отсле-
живать.переход.из.одного.состояния.в.другое.(или.из.одного.места.лабиринта.
в.другое).во.время.поиска..
Node
.можно.представить.как.обертку.вокруг.состоя-
ния..В.случае.прохождения.лабиринта.эти.состояния.имеют.тип.
MazeLocation
..
Будем.считать.
Node
.состоянием,.унаследованным.от.
parent
..Кроме.того,.для.
класса.
Node
.мы.определим.свойства.
cost
.и.
heuristic
,.чтобы.использовать.его.
позже.в.алгоритме.A*.(листинг.2.16)..Пока.не.беспокойтесь..
Класс Node
.стано-
вится.
Comparable
.путем.сравнения.комбинации.
его
.свойств.
cost
.и.
heuristic
.