Java: объектно-ориентированный дизайн; LinkedList и стек

Question

Я пишу BFS и DFS на Java. Я надеялся создать один класс, подобный этому:

/** Preforms BFS and DFS on ...
*/
public class Search{


  private XXX toSearch;
  // where XXX is an interface of Stack and LinkedList that has
  // remove() and add() methods.  

  public Search(boolean isBFS){
    if(isBFS)
      toSearch = new LinkedList();
    else
      toSearch = new Stack();
  }

  public void preformSearch(){
    while(toSearch.size() > 0){
      preformSearchOn(toSearch.remove());  // <----- KEY LINE
    }
  }

  private void preformSearchOn(...){...}

}

Этот класс может выполнять BFS и DFS в зависимости от того, как он инициализируется. Что такое ХХХ? Я не думаю, что это существует.

Я думал, что весь смысл объектно-ориентированного программирования в том, чтобы делать крутые вещи вроде этого.

Какой самый чистый способ справиться с этим?

Answer 1

Я думаю, что вы ищете Стратегию .Способ сделать это не специфичен для Java, или другой «крутой материал» в этом отношении.Эти типы вещей превосходят языки.

Чтобы быть более конкретными, разработайте еще два класса с именами BfsStrategy и DfsStrategy.Требуйте, чтобы каждый класс реализовывал определенный интерфейс Стратегии.Используйте класс, который вы опубликовали, для прозрачного выполнения операций над ними.(Измените имена классов / интерфейсов, чтобы они были более подходящими, если вам нужно.)

Например:

public final class Seeker<E, K> {

    private final E structure;
    private final SearchStrategy strategy;

    public Seeker(final E aStructure, final SearchStrategy aStrategy) {
        structure = aStructure;
        strategy = aStrategy;
    }

    public boolean search(K aKey) {
        return strategy.search(structure, key); //Pretty generic.
    }

}

Answer 2

Что касается поиска в ширину и в глубину, то одним из способов объединения обоих было бы написать реализации java.util.Iterator для каждого из них. Пусть это будет вашей объединяющей абстракцией; это уже часть JDK.

Answer 3

Общий интерфейс: java.util.Queue .

В качестве очереди «первым пришел - первым вышел» вы можете использовать (например) java.util.LinkedList или java.util.ArrayDeque .

В качестве очереди «первым пришел - первым вышел» вы можете обернуть любой Deque, используя java.util.Collections.asLifoQueue .

Stack вместе с суперклассом Vectorустарела, поскольку синхронизирует все методы доступа, что часто не требуется.Я подозреваю, что именно поэтому он не реализует очередь.

Answer 4

XXX должен иметь тип java.util.AbstractList , поскольку оба LinkedList и Stack получены из него.

Но это будетне решить вашу проблему, так как метод remove () для каждого класса будет вести себя одинаково.Чтобы получить другое поведение, вам необходимо вызвать разные методы удаления: remove () или pop () .И как метод, эти remove () и pop () оба реализованы на java.util.Linkedlist (см. Queue interface) тамнет необходимости использовать класс java.util.Stack .

Вы можете вызывать различные методы pop () и remove () с оператором if , но это определенно будет ОО анти-патерне.Базовое решение ОО состоит в реализации 3 классов:

• Абстрактный родительский элемент с именем Поиск Класс
• BfsSearch : работает с remove ()в поиске.
• DfsSearch : работает с pop () при поиске.

Таким образом, пользователь этого класса может работать с Выполните поиск , не зная, использует ли он BfsSearch или DfsSearch.

Еще более продвинутый и гибкий подход ОО будет использовать шаблон стратегии , как описано Майком.Но для простых решений, которые не нуждаются в такой гибкости, это может быть излишним.

Кстати, отличная книга по ОО-дизайну, которая объяснит все эти виды выбора и паттерны, - Ларман :

Применение UML и шаблонов: введение в объектно-ориентированный анализ, проектирование и итеративную разработку (3-е издание)