Учебно-методическое пособие. Алматы, 2017 ббк

Задание

2. Приведите примеры односвязных списков.

3. Приведите пример двусвязных списков.

4. Что нужно сделать для того, чтобы добавить запись в двухсвязный список?

5. Что нужно сделать для того, чтобы удалить запись из двухсвязного списка?

1.4.2 Очередь

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

Представьте себе, что Вы решили приобрести билет на концерт популярной группы. Вы идете в место продажи билетов, а там уже присутствуют такие же желающие приобрести билеты. Вам ничего не остается, как ждать, пока пришедшие раньше Вас не приобретут билеты, но если кто-то пришел после Вас, он должен дождаться, пока не приобретете билеты Вы. Здесь мы имеем дело с принципом: «Первый пришел, первым ушел!» или на английском языке: «First input, First output». Обычно его называют принципом FIFO.

Очередь – частный случай линейного списка, для которого добавление элемента разрешено только в конец списка (хвост), а удаление элемента - из начала (головы) списка.

Начало очереди										Конец очереди

Рис. 1.14

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

Если количество действий зависит от количества элементов, то такие действия называются массовыми.

Рассмотрим основные действия над очередью. Для того чтобы посмотреть, какие действия мы можем проводить с данными, которые организованы в очередь, введем несколько определений.