Двунаправленные и кольцевые списки


Помимо односвязных списков используются также такие разновидности списков, как двусвязные (или двунаправленные) и кольцевые списки. Семантика этих понятий продемонстрирована на рисунках:


Ассоциативная связь

Двусвязный список


Ассоциативная связь

Кольцевой список


Стек


Частным случаем списка является стек. Стеком называется набор элементов, в котором размещение новых элементов и удаление существующих происходит только с одного его конца, называемого вершиной стека. Также стек называют структурой типа LIFO (Last In First Out, первым вошел, последним вышел). Размер стека не должен быть ограничен. По мере появления новых элементов и удаления старых память должна динамически выделяться и освобождаться. Состояние стека характеризуется только его вершиной.


Операции над стеком имеют специальные названия:


push (s, el); - вталкивание элемента el в стек s.

el=pop(s); - выталкивание вершины из стека s. При этом функция возвращает значение выталкиваемого элемента.

el=peek(s); - просмотр вершины стека. Функция возвращает значение вершины стека.


Так же, как и в списках, в стеках можно размещать данные произвольных типов.


Очередь


Еще одним частным случаем списка является очередь Очередью называется набор элементов, которые могут удаляться с одного ее конца (называемого началом очереди) и помещаться в другой конец этого набора (называемого концом очереди). Очередь также называют структурой типа FIFO (First In First Out, первым вошел, первым вышел). Как и для списков, размер очереди не должен лимитироваться: память должна запрашиваться и высвобождаться динамически.


Базовые операции над очередью такие же, как и над списком:


insert –добавить в конец очереди новый элемент;

remove – удалить из очереди первый элемент;