Стек

14.2 Стек

Стек - это структура данных, которая обеспечивает доступ к списку по принципу LIFO (от первых букв английской фразы "Last Input First Output"): последним вошел, первым вышел. Компонента извлекается из стека таким образом, что первой выбирается та, которая была помещена последней.

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

Значением указателя, представляющего стек как единый объект, является ссылка на ВЕРШИНУ стека. Последнее звено цепочки – стека содержит в поле ссылок значение NIL.

Если стек пуст, то значением указателя является ссылка NIL.

Перед началом заполнения стека его необходимо сделать пустым, т.е. выполнить "обнуление" указателя стека: STACK:= NIL.

Над стеком, как и над очередью, допустимы следующие операции:

1) формирование;

2) занесение нового элемента;

3) удаление элемента;

4) доступ (только для просмотра) к N-му звену стека.

Заметим, кстати, что занесение и удаление происходят в стеке исключительно в его вершине.

Запишем теперь саму процедуру формирования стека:

procedure SOZDAN_STACK (var ST: SS);

var K: SS;

EL: integer;

begin

randomize;

EL:= random(10);

new(ST); ST:= nil;

while EL <> 0 do

begin

¦ new(K); K^.elem:= EL;

¦ k^.next:= ST; ST:= K;

¦ EL:= random(10);

end;

end.

ЗАМЕЧАНИЕ. Как видно из процедуры, организация очереди и стека отличается только порядком установления связи: предыдущий элемент очереди указывает на следующий, а следующий элемент стека ссылается на предыдущий.

Известно, что новый элемент всегда вставляется на первое место - в вершину стека. Отсюда получаем схему вставки звена в стек:

Процедура имеет два параметра: ST - указатель на стек, EL - заносимый элемент:

PROCEDURE VSTAVKA_V_STACK(var ST: SS; EL: integer);

var K: SS;

begin

new(K); K^.elem:= EL;

K^.next:= ST; ST:= K

end.

Схематически процесс удаления можно изобразить так:

По схеме видно, что удаляется N-е звено (вершина стека), которое надо запомнить в специальной ячейке SKLAD:

procedure UDALENIE_IZ_STACK(var ST: SS; var SKLAD: integer);

begin

¦ SKLAD:= ST^.elem;

¦ ST:= ST^.next

end.

Мы видим, что здесь переменная ST начинает хранить ссылку на N-1 элемент.

Данная процедура имеет недостатки:

1) предполагается, что стек заведомо не пуст, иначе программа зависнет;

2) исключаемое звено не уничтожается, т.к. меняется только ссылка в переменной ST. Если таких удалений несколько, то память будет забита "мусором". Поэтому следует исключить элементы не только из списка, но и из памяти. Для этого можно использовать процедуру DISPOSE.

Указанные недостатки учтены в следующей процедуре:

procedure UDALENIE_MOD(var ST: SS; var SKLAD: integer);

var K: SS;

begin

¦ if ST = nil then writeln('стек пустой')

¦ else begin

¦ ¦ SKLAD:= ST^.elem; K:=ST;

¦ ¦ ST:= ST^.next; dispose(K);

end;

end.

Здесь мы ввели в употребление вспомогательную ссылочную переменную К, т.к. писать DISPOSE (ST) нельзя, ведь ST содержит ссылку на вершину стека.

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

Для написания этой процедуры следует уточнить, что под N-м элементом стека следует понимать элемент, отстоящий на N позиций от вершины стека:

procedure VIBORKA_IZ_STACKA(var ST: SS; var SKLAD: integer;

N: integer);

var K: SS; i: integer;

begin

¦ K:= ST;

¦ for i:= 1 to N-1 do

¦ UDALENIE_IZ_STACK(K, SKLAD);

¦ SKLAD:= K^.elem;

end.

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

14.3 Дек

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

Более точно следует представить так:

Формирование дека

Для организации дека в виде динамической цепочки необходимо иметь следующие типы:

type SS = ^ZVENO;

ZVENO = record

ELEM: integer;

next: SS;

pred: SS;

end.

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

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

procedure FORMIR_DEK_1(var L, R: SS);

var Z: SS; EL: integer;

begin

¦ new(L); read(L^.elem);

¦ L^.pred:= nil; R:= L; Z:= L;

¦ WHILE R^.elem <> 0 do

¦ begin

¦ ¦ new(R^.next); R:=R^.next;

¦ ¦ read(r^.elem); R^.pred:= Z; Z:= R;

¦ end;

¦ R^.next:= nil; readln;

end.

ПРИМЕЧАНИЕ. В рассмотренном примере для образования дека используются три ссылочные переменные: L - начало дека, R – конец дека, Z - промежуточное звено. Однако эта программа может быть упрощена за счет использования более сложных ссылок типа R^.NEXT^.ELEM и R^.NEXT^.PRED.

Рассмотрим подробно эти объекты. Пусть ссылочная переменная Z указывает на текущее звено дека:

При таких обозначениях динамическая переменная Z^.NEXT^.ELEM означает числовое поле звена 2 (т.е элемент ELi+1), а переменная Z^.NEXT^.PRED - поле PRED звена 2. Учитывая эти соображения, представим программу формирования дека следующим образом:

procedure FORMIR_DEK_2(var L, R: SS);

begin

¦ randomize; new(L);

¦ L^.elem:= random (10);

¦ L^.pred:= nil; R:= L;

¦ while R^.elem <> 0 do

¦ begin new(R^.next);

¦ ¦ R^.next^.elem:= random(10);

¦ ¦ R^.next^.pred:= R; R:=R^.next

¦ end;

R^.next:= nil

end.

Для дека справедливы те же операции, что для очереди и стека - вставка и удаление звеньев.

Для процедуры вставки в дек, как и в любой другой линейный список, необходимы два параметра: X - звено, после которого (перед которым) надо поместить элемент, и Y - вставляемое звено. Схема вставки остается такой же, как, например, в очереди, но в деке после включения нового звена нужно установить две связи – на последующий и предыдущий элементы.

Рассмотрим предварительно схему связи между звеньями дека в процессе вставки нового элемента:

Процедура вставки нового звена Y в дек после звена X принимает вид:

procedure VSTAVKA_V_DEK_POSLE(X, Y: SS);

begin

¦ Y^.next:= X^.next;

¦ Y^.pred:= X;

¦ X^.next:= Y;

¦ Y^.next^.pred:= Y;

end.

ЗАМЕЧАНИЕ 1. Мы рассмотрели теперь процедуры вставки нового звена во все виды линейных списков с односторонней связью (цепочки, очереди, стеки) и в дек. Однако во всех этих процедурах новое звено вставлялось ПОСЛЕ указанного звена (в стеке - в вершину, в очереди - в хвост). Конечно, можно в односвязном линейном списке поставить новый элемент и ПЕРЕД указанным, но это требует некоторых дополнительных операций. Например, можно новый элемент поместить в следующее звено, а затем произвести обмен информационными полями. В деке же возможна прямая вставка звена ПЕРЕД указанным с использованием ссылки PRED. В результате получаем:

procedure VSTAVKA_V_DEK_PERED(X, Y: SS);

begin

¦ Y^.next:= X^.pred^.next; X^.pred^.next:= Y;

¦ Y^.pred:= X^.pred; X^.pred:= Y;

end.

ЗАМЕЧАНИЕ 2. При вставке нового звена Y в дек относительно X следует учитывать, что на момент применения рассмотренных процедур звенья X и Y уже сформированы и значения этих ссылочных переменных определены. Так, например, звено Y можно сформировать следующим образом:

NEW(Y); Y^.NEXT:= NIL; Y^.PRED:= NIL; READ(Y^.ELEM).

Что касается звена X, то здесь возможны два случая:

1) известен адрес (ссылка) на элемент X; тогда при обращении к процедуре уже задано значение фактического параметра;

2) известен только сам элемент (информационное поле звена X);

для определения ссылки на звено X в указанном деке следует "прокрутить" дек до этого звена (подобно поиску N-го звена в стеке).

Заметим также, что обе процедуры неприменимы для дека, состоящего из одного звена.

При удалении звена из дека, как и в любом линейном списке, происходит перебрасывание ссылок через удаляемое звено: ссылка NEXT предыдущего звена получает своим значением адрес третьего звена, а ссылка PRED третьего звена указывает на первое звено. В результате второе (удалямое) звено X оказывается изолированным от остальных звеньев, что и означает его удаление из дека.

ЗАМЕЧАНИЕ. Данная процедура применима только для звена X, находящегося внутри дека. Для пограничных случаев, когда звено X является первым или единственным, необходимо использовать более сложную процедуру:

procedure UDAL_DEK_1(X: SS; VAR Y, Z: SS);

begin

¦ if Y^.next = nil then writeln('Дек пуст !') else

¦ if X = Y then Y:= Y^.next else

¦ begin x^.pred^.next:=x^.next;

¦ ¦ {Переброска ссылки next вверху}

¦ ¦ x^.next^.pred:=x^.pred;

¦ ¦ {Переброска ссылки pred внизу}

¦ end;

end.

В этой процедуре введены параметры-переменные: Y - начало дека и Z - ссылка на конец дека. Они необходимы, т.к. здесь могут быть изменены начало и конец дека.

Если Y^.NEXT = NIL, то это означает, что дек пуст и никаких действий не производится. Равенство X = Y показывает, что дек состоит из одного звена, которое удаляется путем присваивания ссылке Y (началу дека) значения указателя на последнее нулевое звено дека. Для остальных случаев все действия производятся, как и в предыдущем примере.

Похожие работы

Основы программирования на языке Паскаль

Скачать

168304

7

26

... .....-46.780 Program Prim24; Var r1,r2:real; BEGIN r1:=-46.78; r2:=-46.78; writeln('r1=',r1:12:3,' r2=',r2:9:4); writeln('_______________________________'); readln; END. 6. Массивы   6. 1. Описание массивов В языке Паскаль можно обрабатывать не только отдельные переменные, но и их совокупности. Одной из таких совокупностей (структурированных) данных является массив. ...

Алгоритмические языки и программирование Системное программное обеспечение Технология программирования"

Скачать

112819

0

0

... . Объясните, для чего служат разрешения и привилегии в Windows NT. Зав. кафедрой --------------------------------------------------   Экзаменационный билет по предмету СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ Билет № 22 Перечислите возможности и инструменты системы программирования Microsoft Developer Studio. Укажите для чего предназначается буфер в системах ввода-вывода, ...

Основные понятия алгоритмического языка

Скачать

91405

0

0

... с внешнего устройства (из входного файла) в основную память ЭВМ, операция вывода - это пересылка данных из основной памяти на внешнее устройство (в выходной файл). Файлы на внешних устройствах часто называют физическими файлами. Их имена определяются операционной системой. В программах на языке Паскаль имена файлов задаются с помощью строк. Например, имя файла на диске может иметь вид: ...