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

Двусвязный список аналогичен односвязному списку, но отличается наличием пары указателей в каждом элементе: на предыдущий элемент (prev) и на следующий (рис.2). Кроме того добавляется особый элемент, называемый указателем конца списка или хвостом списка (tail).

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

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

Cтек

Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Примеры стека: винтовочный патронный магазин, тупиковый железнодорожный разъезд для сортировки вагонов.

Основные операции над стеком - включение нового элемента (английское название push - заталкивать) и исключение элемента из стека (англ. pop - выскакивать). Полезными могут быть также вспомогательные операции:

· определение текущего числа элементов в стеке;

· очистка стека;

неразрушающее чтение элемента из вершины стека.

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

а). пустого;

б-г). после последовательного включения в него элементов с именами 'A', 'B', 'C';

д, е). после последовательного удаления из стека элементов 'C' и 'B';

ж). после включения в стек элемента 'D'.

Поиск по сайту: