Что мой профессор подразумевает под «реализацией статического абстрактного типа данных»? - PullRequest
Новая
       27

Что мой профессор подразумевает под «реализацией статического абстрактного типа данных»?

0 голосов
/ 08 октября 2018

В моем классе для нашего задания мы создаем два разных типа абстрактных данных, Double Stack и Leaky Stack.У меня нет проблем с их созданием, но мой профессор добавил в детали назначения для обоих этих ADT «Дать эффективную статическую реализацию ADT».Но что, черт возьми, это значит?Я мог бы спросить его завтра, но я хочу выполнить это задание сегодня.Кто-нибудь знает, что он имеет в виду под этим?

1 Ответ

0 голосов
/ 09 октября 2018

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

Примерстатическая реализация (хотя она позволяет устанавливать общую емкость) может выглядеть следующим образом.Здесь доступ всегда будет O (1), так как индекс используется напрямую, нет обхода структуры данных и перераспределения памяти.Обратите внимание, что код является примером, и не был проверен.Использование Generic может быть удалено, если рассматриваемый подход определяет конкретный тип стека (например, int или char). 

public class AnotherStack<T>
{
  private final T[] values;
  private int loc = 0;

  // must use the suppress, as we are using a raw Object array
  //   which is necessitated as cannot make a generic array  
  // See Effective Java
  @SuppressWarnings("unchecked")
  public AnotherStack(int size)
  {
    values = (T[])new Object[size];
  }


  public void push(T val)
  {
      if (loc < values.length) {
          values[loc++] = val;
      }
      else {
          throw new IllegalStateException("Stack full");
      }
  }

  public T pop()
  {
      if (loc == 0) {
          throw new IllegalStateException("Stack empty");
      }
      return (values[--loc]);
  }

  // other methods
}
...