Структура данных и алгоритмы в python - PullRequest
Новая
       16

Структура данных и алгоритмы в python

0 голосов
/ 12 марта 2020

Q1 - Предположим, что изначально пустая очередь Q выполнила в общей сложности 32 операции постановки в очередь, 10 первых операций и 15 операций удаления из очереди, 5 из которых вызвали пустые ошибки, которые были перехвачены и проигнорированы. Каков текущий размер Q?

Я думаю, что ответ на этот вопрос 22; но мне нужна помощь в этом вопросе ...

Q2 - Если бы очередь предыдущей проблемы была экземпляром ArrayQueue, который использовал исходный массив емкостью 30, а его размер никогда не был больше 30, что будет окончательное значение переменной переднего экземпляра?

1 Ответ

0 голосов
/ 12 марта 2020

Это поможет начать с точного определения операций с очередями:

  • void Enqueue (Item) - вставить Item в конец очереди.
  • Item Dequeue - удалить и вернуть предмет в начало очереди. Выдает пустую ошибку, если очередь пуста при вызове операции.
  • Элемент первый - вернуть элемент в начало очереди, не удаляйте его.

Это означает, что что Enqueues добавляет один к размеру очереди, Dequeues удаляет один из размера очереди, если размер больше 0, и первые не влияют на размер очереди.

Таким образом, у нас есть 32 шага, 10 нет. ОПС и 15 потенциальных декрементов. Пять из этих потенциальных уменьшений не повлияли на размер очереди, поэтому осталось только десять. 

32 * 1 + 10 * 0 + 5 * 0 + 10 * -1 = 22

Это допустимо только в том случае, если операции определены так, как указано выше. Например, если мы изменим определение Enqueue и Dequeue следующим образом:

  • void Enqueue (Список элементов) - вставьте каждый элемент в списке в конец очереди.
  • Список элементов Dequeue (Count) - убрать и вернуть Count Items из передней части очереди. Возвращает max (количество, размер очереди) Items.

Теперь у нас недостаточно информации, чтобы ответить на вопрос. Вот почему важно быть точным в отношении рассматриваемых вами операций.

Что касается второго вопроса, предполагается, что ArrayQueue реализован в виде буфера кругового массива размером 30 (массив из 30 элементов с указателем на элементы "front" и "back"), и если предположить, что Enqueues происходят в "back", а Dequeues происходят в "front", тогда все, что нам нужно сделать, это подсчитать количество Dequeues, так как это единственная операция, которая влияет на передний указатель.

15 общее количество возможных операций может измениться, где передние точки. Пять из них не изменили бы положение спереди, поэтому передние бы переместились в общей сложности 10 раз. Предполагая, что массив имеет нулевое индексирование, front будет указывать на индекс массива 10 (11-й элемент, готовый к следующей операции Dequeue или First).

Другая реализация ArrayQueue будет иметь другой ответ. Опять же, это помогает уточнить c о реализации структур при попытке рассуждать об их внутренней работе.

...