Как сделать неразрушающий анализ очереди в Java

Question

Я помогаю своему сыну на уроке программирования в колледже, и, наверное, мне тоже нужен урок. Он выполнил задание, но я не верю, что он делает это наилучшим образом. К сожалению, я не могу заставить его работать с моим лучшим способом. Это явно лучше, потому что это еще не работает.

Его просят реализовать некоторые методы для класса, который расширяет другой класс.

Ему сказали, что он должен использовать следующее определение класса, и он не может ничего изменить в ListQueue.

public class MyListQueue <AnyType extends Comparable<AnyType>> extends ListQueue<AnyType>

Вот что находится в ListQueue

// Queue interface
//
// ******************PUBLIC OPERATIONS*********************
// void enqueue( x )      --> Insert x
// AnyType getFront( )    --> Return least recently inserted item
// AnyType dequeue( )     --> Return and remove least recent item
// boolean isEmpty( )     --> Return true if empty; else false 
// void makeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// getFront or dequeue on empty queue

/**
 * Protocol for queues.
 */

ОК. Я чувствую себя довольно хорошо, просматривая связанный список в Паскале или Си (показывая мой возраст), но никогда раньше не работал на языке ООП.

Когда я пытаюсь что-то подобное

dummyQueue = this.front.next;

Я получаю следующую ошибку. * фронт имеет частный доступ в ListQueue *

С чем я согласен, но кроме удаления элемента из очереди, как я могу пройти по списку или иным образом получить доступ к переднему, заднему, следующему и предыдущему, которые все находятся в ListQueue.

Образование будет оценено.

Спасибо, David

Answer 1

Если я вас правильно понимаю, вы делаете что-то вроде этого:

MyListQueue<String> dummyQueue = new MyListQueue<String>();
dummyQueue = this.front.next;

Если это так, одним из основных принципов ООП является инкапсуляция, то есть скрытие данных. Идея состоит в том, что пользователи вне класса не имеют доступа к внутреннему состоянию класса.

Если вы хотите определить размер очереди и не можете изменить ни интерфейс, ни реализацию, одну вещь, которую вы можете сделать, - создать делегат очередь, которая переопределяет очереди и очереди увеличить и уменьшить счетчик.

Answer 2

Если вы выбираете очередь, вы обычно хотите ставить в очередь и удалять элементы из очереди. Вы хотите знать, пуста ли очередь, и хотите посмотреть на передний элемент, если он вам нужен, или оставить его кому-то другому. Очередь - это своего рода буфер, который позволяет избежать блокировки, если отправитель быстрее, чем получатель. При наличии очереди получатель может решить , когда , прочитать следующую запись. Очередь может реализовать некоторую (основанную на приоритете) сортировку и решить, какой элемент является передним элементом.

Если вам нужны другие операции, такие как обход списка, то очередь может оказаться не лучшим выбором. Посмотрите на другие типы коллекций, возможно, на ArrayList.

Хотя некоторые вещи можно сделать, вы можете создать подкласс ListQueue и переопределить некоторые методы. Поэтому, если вам нужен дополнительный метод size(), это может быть решением:

public class MyListQueue <T extends Comparable<T>> extends ListQueue<T> {

  private size = 0;

  public void enqueue(T element) {
    size++;
    super.enqueue(element);
  }

  public T dequeue() {
    if (isEmpty()) {
       return null; // that's a guess...
    }
    size--;
    super.dequeue(element);
  }

  public int size() {
    return size;
  }
}

Я заменил AnyType на T, что более распространено.

Answer 3

Вы спросили: «Кроме удаления элемента из очереди, как я могу пройти по списку или иным образом получить доступ к переднему, заднему, следующему и предыдущему, которые все находятся в ListQueue».

В чистом смысле вы не должны быть в состоянии.

Идеализированная очередь обещает только несколько вещей:

• Толкаем предметов в спину
• Поп предметы с фронта
• (возможно) Проверить лицевой элемент, если не пустой
• (возможно) предикат пространства определения для pop и inspect , определяющий, пуста ли очередь

На данный момент я предполагаю, что очередь не предназначена для использования ни с одновременными считывателями (получающими доступ к фронту одновременно), ни с одновременными считывателями и записывающими устройствами (обращающимися одновременно с задней и передней панелями).

Принимая во внимание это определение, нет причин искать «внутри» очереди. Вы кладете вещи в одну сторону, а вещи - в другую. Если вы учитываете , ограничивающий размера очереди, вам может потребоваться дополнительный предикат пространства определения для операции push , чтобы определить, заполнена ли очередь. «Быть ​​заполненным» имеет смысл, только если очередь ограничена. «Быть ​​пустым» имеет значение, только если поток, вызывающий pop или inspect , не хочет блокировать.

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

Вот почему очереди обычно не являются конкретными типами в библиотеках структуры данных. В C ++ тип std::queue является декоратором для некоторого другого типа контейнера. В Java java.util.Queue - это интерфейс. Scala использует другой подход: класс scala.collection.mutable.Queue является расширением типа MutableList. Это похоже на подход, предусмотренный в назначении вашего сына, но неясно, намеревался ли ваш ListQueue когда-либо позволить посторонним (включая подклассы) воспользоваться его «природой списка» - проникнуть в представление очереди, чтобы использовать последовательность внутри.

У вас есть требование, чтобы иметь возможность посещать что-либо, кроме главы вашей очереди? Необходимость сделать это ограничивает ваш выбор относительно того, какие очереди могут обслуживать ваши потребляющие функции. Похоже, что мы изучаем неправильные уроки с этим заданием.