списки стеки деки очереди в двух словах. Лекция 1. Программа компилятор

• Название: Программа компилятор
• Анкор: списки стеки деки очереди в двух словах
• Дата: 24.09.2019
• Размер: 99.41 Kb.
• Имя файла: Лекция 1.docx
• Тип: Программа; #87592
• страница: 4 из 4

Циклические (кольцевые) списки

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

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

Циклические списки, так же как и линейные, бывают однонаправленными и двунаправленными.

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

Слайд 14 Циклические (кольцевые) списки однонаправленные

Для полного обхода такого списка достаточно иметь указатель на произвольный элемент, а не на первый, как в линейном однонаправленном списке. Понятие "первого" элемента здесь достаточно условно и не всегда требуется. Хотя иногда бывает полезно выделить некоторый элемент как "первый" путем установки на него специального указателя. Это требуется, например, для предотвращения "зацикливания" при просмотре списка.

Слайд 15



Основные операции, осуществляемые с циклическим однонаправленным списком:

• 
  создание списка;
  
• 
  печать (просмотр) списка;
  
• 
  вставка элемента в список;
  
• 
  удаление элемента из списка;
  
• 
  поиск элемента в списке;
  
• 
  проверка пустоты списка;
  
• 
  удаление списка.
  

Слайд 16

Циклические (кольцевые) списки двунаправленные

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



Основные операции, осуществляемые с циклическим двунаправленным списком аналогичны как у циклического однонаправленного.

Слайд 17

Деки

Дек является особым видом очереди.

Дек (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) – это структура данных, представляющая собой последовательность элементов, в которой можно добавлять и удалять в произвольном порядке элементы с двух сторон. Первый и последний элементы дека соответствуют входу и выходу дека.

Слайд 18

Деки



Частные случаи дека – это ограниченные деки:

• 
  дек с ограниченным входом – из конца дека можно только извлекать элементы;
  
• 
  дек с ограниченным выходом – в конец дека можно только добавлять элементы.
  

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

Однако применительно к деку целесообразно говорить не о начале и конце как в очереди, а о левом и правом конце.

Описание элементов дека аналогично описанию элементов линейного двунаправленного списка. Поэтому объявим дек через объявление линейного двунаправленного списка:

• 
  создание дека;
  
• 
  печать (просмотр) дека;
  
• 
  добавление элемента в левый конец дека;
  
• 
  добавление элемента в правый конец дека;
  
• 
  извлечение элемента из левого конца дека;
  
• 
  извлечение элемента из правого конца дека;
  
• 
  проверка пустоты дека;
  
• 
  очистка дека.