Очереди, стеки, связанные списки

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

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

СТЕКИ

Организация стека в определенном смысле противоположна организации очереди, поскольку здесь используется доступ по принципу "последней вошел, первый вышел" /такой метод доступа иногда называют методом LIFO/. Представим себе стопку тарелок. Нижняя тарелка из этой стопки будет использована последней, а верхняя тарелка /которая была установлена в стопку последней/ будет использована первой. Стеки широко используются в системном программном обеспечении, включая компиляторы и интерпретаторы.

СВЯЗАННЫЕ СПИСКИ

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

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

В списке с одиночной связью каждый элемент данных имеет связь с последующим элементом в списке. Каждый элемент данных обычно представляет собой запись, которая содержит информационные поля и указатель связи. Список с одиночной связью показан на рис.4.

Рис.4. Расположение списка с одиночной связью в памяти:

1 - информация;

2 - указатель связи;

3 - нуль.

Каждый элемент в списке с двойной связью имеет указатель на следующий элемент списка и указатель на предыдущий элемент списка. Рис.7 иллюстрирует характер связей в таком списке. Список, который вместо одной имеет две связи, отличается двумя основными преимуществами. Во-первых, список может читаться в обоих направлениях. Это не только упрощает сортировку списка, но также позволяет пользователям базы данных просматривать данные в обоих направлениях. Во-вторых, и прямая и обратная связь позволяют прочитать список полностью и поэтому при нарушении одной из связей список может быть восстановлен по другой связи. Это свойство имеет смысл использовать при отказах оборудования, приводящих к нарушению списка.

Рис.7. Список с двойной связью: 1 - информационные поля; 2 - связь с нулевым значением.