Представление стека и очередей в виде списков 1.5.1. Стек
Мультисписки
Иногда возникают ситуации, когда имеется несколько разных списков, которые включают в свой состав одинаковые элементы. В таком случае при использовании традиционных списков происходит многократное дублирование динамических переменных и нерациональное использование памяти. Списки фактически используются не для хранения элементов данных, а для организации их в различные структуры. Использование мультисписков позволяет упростить эту задачу.
Мультисписок состоит из элементов, содержащих такое число указателей, которое позволяет организовать их одновременно в виде нескольких различных списков. За счет отсутствия дублирования данных память используется более рационально.
Рис.1.5. Объединение двух линейных списков в один мультисписок.
Экономия памяти далеко не единственная причина, по которой применяют мультисписки. Многие реальные структуры данных не сводятся к типовым структурам, а представляют собой некоторую комбинацию из них. Причем комбинируются в мультисписках самые различные списки линейные и циклические, односвязанные и двунаправленные.
Стек представляет собой структуру данных, из которой первым извлекается тот элемент, который был добавлен в нее последним. Стек как динамическую структуру данных легко организовать на основе линейного списка. Для такого списка достаточно хранить указатель вершины стека, который указывает на первый элемент списка. Если стек пуст, то списка не существует и указатель принимает значение nil.
Рис.1.6. Организация стека на основе линейного списка.
Приведем пример программы, реализующей стек как динамическую структуру.
Program stack;
element=record
data:string;
next:pointer;
var
n: integer;
current:^element;
pnt:^element;
procedure put_element(s:string); {занесение элемента в стек}
begin
new(pnt);
x^.data:=s;
x^.next:=current;
current:=pnt;
end;
procedure get_element(var s:string); {получение элемента из стека}
if current=nil then s:=‘пусто’ else
pnt:=current;
s:=pnt^.data;
current:=pnt^.next;
end;
end;
{------------program--------------}
begin
current:=nil;
repeat
writeln(‘1 добавить в стек’);
writeln(‘2 удалить из стека’);
writeln(‘0 выход’);
if n=1 then
write(‘элемент ? ‘);
if n=2 then
until n=0;
В программе добавление нового элемента в стек оформлено в виде процедуры put_element, а получение элемента из стека как процедура get_element.
Дек или двусторонняя очередь, представляет собой структуру данных, в которой можно добавлять и удалять элементы с двух сторон. Дек достаточно просто можно организовать в виде двусвязанного ациклического списка. При этом первый и последний элементы списка соответствуют входам (выходам) дека.
Рис.1.7. Организация дека на основе двусвязанного линейного списка
Рис.1.8. Организация дека на основе двусвязанного линейного списка
Простая очередь может быть организована на основе двусвязанного линейного списка. В отличие от дека простая очередь имеет один вход и один выход. При этом тот элемент, который был добавлен в очередь первым, будет удален из нее также первым.
Рис.1.9. Организация дека с ограниченным входом на основе двусвязанного линейного списка
Рис.1.10. Организация дека с ограниченным выходом на основе двусвязанного линейного списка
Очередь с ограниченным входом или с ограниченным выходом также как дек или очередь можно организовать на основе линейного двунаправленного списка.
Разновидностями очередей являются очередь с ограниченным входом и очередь с ограниченным выходом. Они занимают промежуточное положение между деком и простой очередью.
Причем дек с ограниченным входом может быть использован как простая очередь или как стек.
