Стек, очередь, дек

1. Стек- это линейный список, на котором все включения и исключения элементов делаются на одном конце. Пример стека: Монетница (монеты добавляются строго по одной), стопка тарелок. В любой момент времени пользователю доступен только верхний элемент. Таким образом, самый первый элемент, добавленный в стек, будет исключен из него самым последним. Или иными словами последний добавленный первым "выйдет". Last in, First Out. LIFO.

2. Очередь - линейный список, в котором все включения делаются на одном конце, а все исключения - на другом. В очереди первый добавленный элемент оказывается самым ближайшим элементом на выходе, после его удаления из очереди можно будет удалить второй добавленный элемент. Таким образом, исключение из очереди осуществляется в линейном порядке его добавления. Такой принцип получил название «First In, First Out», FIFO.

3. Дек - является обобщением очереди и стека, то есть включения, и исключение элементов могут быть выполнены на любом конце. Различают деки, ограниченные по входу (все включения в элементы списка - строго на одном конце), и деки, ограниченные по выходу.

Реализация стека, дека и очереди на основе ЛСС (Линейного связанного списка)

type pUzel=^TUzel;

TUzel = record

INFO: integer;

next: pUzel

end;

Любой линейный список, реализованный как линейный связанный список, должен иметь голову - указатель на первый элемент линейного списка. Для стека это означает, что элемент HEAD должен быть Var head:pUzel; - который указывает на верхний элемент стека. Тогда добавление нового элемента в стек заключается в разрыве связи между головой и первым элементом:

1. В оперативке выделяется новый элемент рис.1

procedure insert_into_stak

Var tmp:pUzel;

Begin

{1} new(tmp);

{2} tmp^.next=head;

{3} head:=tmp;

end;

Исключение стека заключается:

В tmp мы занесли значение head;

{2} head:=head^.next;

{1} tmp:=head;

{3} delete(tmp);

Таким образом, добавление и удаление элементов в стек происходит за единицу времени O(1).

2. Добавление и удаление в очередь. В случае очереди возникает двусмысленность с понятием головы: т.к. первый элемент располагается "с другой стороны".

O(N - 1) = O(N)

Элемент списка

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

Удаление из очереди состоит из двух этапов. Проход по всей очереди для определения её конца, т.е. того первого элемента, который выталкивается из очереди.

Delete.from_queue(head:pUzel);

Var tmp,prev: pUzel;

Begin

If tmp<> nil then

Begin

tmp:= head;

while tmp^.next<>nil do

Begin

End;

tmp:= tmp^.next;

Delete(tmp); prev^.next:= nil;

(*) If head = tmp then head:= nil;

Недостатком данного алгоритма является:

1. Частая проверка оператора *, которую можно было бы избежать или исключить, заметив что элемент "голова" формально является предшественником первого элемента, однако в данном случае типы данных головы и элемента различаются. pUzel и tUzel соответственно. Для обобщения можно использовать в качестве головы статическую переменную типа tUzel. В этом случае при реализации поле head типа tUzel можно использовать двумя способам:

1.1. поле инфо(Info) не используется, а используется только поле next, для указывает ан первый элемент линейного связанного списка

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

2. Удаление из очереди осуществляется за U(n). Чтобы улучшить оценку необходимо

	Вход

Такой способ организации очереди обозначим через очередь с двумя указателями. при этом хвост линейного списка является входом в очередь, а голова - выходом. при такой организации удаление и добавление элементов осуществятся за U(1).