Стеки, Деки, Очереди

Стек

Стек

Задачи этого раздела подразумевают реализацию стеков (stack), очередей (queue) и дек (deque) на базе массивов и связных списков. Для тестирования решений используются материалы сайта ecrayon-olimp.com. После того как Вы убедились, что программа работает, необходимо отправить решение на сайт e-olimp.com для тестирования. Решение должно пройти все тесты. Программа не должна использовать каких=либо библиотечных структур данных явно или неявно предоставляющих функциональность стека или очереди. Можно использовать только массивы и связные списки.

Стек = Stack

  1. Простой стек. Для решения задачи необходимо использовать массив.
  2. Стек с защитой от ошибок. Для решения задачи необходимо использовать массив.
  3. Стек неограниченного размера Возможно использовать один из трех вариантов реализации:
    • Связный список. Недостатки: отсутствие прямого доступа к значению элемента массива по его индексу; дополнительный расход памяти на хранение ссылки на следующий элемент списка.
    • Динамические массивы с переносом значений в новый расширенный массив при переполнении исходного. Недостатки: вычислительные затраты на копирование массива; более чем удвоенный объем памяти на момент расширения хранилища.
    • Кластерная реализация: список массивов. Простая реализация стека в виде массива фиксированного размера, но с добавлением нового массива при переполнении предыдущего. Для каждого массива в списке хранится номер первого элемента в нем. Наиболее эффективный по соотношению расхода памяти и скорости работы при правильном выборе размера массивов.

Очередь = Queue

  1. Простая очередь. Для решения задачи необходимо использовать массив.
  2. Очередь с защитой от ошибок. Для решения задачи необходимо использовать массив.
  3. Очередь неограниченного размера Возможно использовать один из трех вариантов реализации:
    • Связный список. Недостатки: отсутствие прямого доступа к значению элемента массива по его индексу; дополнительный расход памяти на хранение ссылки на следующий элемент списка.
    • Динамические массивы с переносом значений в новый расширенный массив при переполнении исходного. Недостатки: вычислительные затраты на копирование массива; более чем удвоенный объем памяти на момент расширения хранилища.
    • Кластерная реализация: список массивов. Простая реализация стека в виде массива фиксированного размера, но с добавлением нового массива при переполнении предыдущего. Для каждого массива в списке хранится номер первого элемента в нем. Наиболее эффективный по соотношению расхода памяти и скорости работы при правильном выборе размера массивов.

Дек (дека) = Deque

  1. Простой дек. Для решения задачи необходимо использовать массив.
  2. Дек с защитой от ошибок. Для решения задачи необходимо использовать массив.
  3. Дек неограниченного размера Возможно использовать один из трех вариантов реализации:
    • Двунаправленный связный список. Недостатки: отсутствие прямого доступа к значению элемента массива по его индексу; дополнительный расход памяти на хранение ссылки на следующий элемент списка.
    • Динамические массивы с переносом значений в новый расширенный массив при переполнении исходного. Недостатки: вычислительные затраты на копирование массива; более чем удвоенный объем памяти на момент расширения хранилища.
    • Кластерная реализация: двунаправленный список массивов. Простая реализация стека в виде массива фиксированного размера, но с добавлением нового массива при переполнении предыдущего. Для каждого массива в списке хранится номер первого элемента в нем. Наиболее эффективный по соотношению расхода памяти и скорости работы при правильном выборе размера массивов.

Решения задач

Решения задач

Related Images:

Добавить комментарий