>}
Writeln;
list; { роздруківка вмісту стека }
Writeln);
х: = stacktop; { зчитування без видалення }
Writeln;
Writeln;
List;
For i: = 1 To 2 Do Begin
х: = pop; { зчитування з видаленням }
Writeln
End;
Writeln;
List;
х : = pop;
Writeln;
Writeln;
list;
Writeln);
Недолік реалізації стека на основі масиву - це його обмеженість в довжині, для подолання цього недоліку використовують стек на основі лінійного списку.
2. Черга
Черга - окремий випадок лінійного односвязного списку, для якого дозволені тільки дві дії: додавання елемента в кінець черги і видалення елемента з початку черзі. Для створення і роботи з нею необхідно мати як мінімум два покажчика:
В· На початок черги.
В· На кінець черги.
Черга можна представити у вигляді ланок, кожна з яких складається з двох полів: перше - поле елемента, друге - поле посилання на наступний елемент черги.
Для черг застосовні наступні операції:
В· Зробити порожній.
В· Додати в чергу.
В· Взяти з черги.
В· Черга порожня.
В· Черговий елемент.
Реалізація черзі на основі лінійного списку
Опис типу змінних для реалізації черги: користуємося рекурсивним описом полів:
Type typeelem = Integer; тип елемента черзі
connect = ^ data; рекурсивне визначення покажчика
data = Record
elem: typeelem; тип інформаційної осередку
next: connect тип покажчика
End;
В цьому випадку кожна ланка міститься в покажчику попереднього ланки.
Процедура ініціалізації черзі включає в себе виділення пам'яті для створення нової осередки, покажчики присвоюються рівними нової осередку, покажчик на наступне ланка одно nil:
Процедура друкування вмісту черзі: незалежної змінної присвоюємо значення покажчика початку, задаємо цикл, до того моменту як покажчик не буде дорівнює nil; виписуємо вміст ланки і вказівником задаємо значення наступної ланки:
S: = Sn;
While s <> nil do begin
Write;
S: = S ^. Next; end;
Функція перевірки на порожнечу черзі виглядає наступним чином:
Empty : = Sn = SK ;
Функція може приймати два значення. Якщо початок і кінець співпадають, то функція дорівнює правді, і навпаки: не збігаються - брехні.
Процедура вставки:
new;
P ^. Next : = nil ;
P ^. Elem: = x;
Sk ^. Next: = p;
sk : = p ;
створюється нова ланка, покажчик якого дорівнює nil, інформаційної осередку надається якесь значення, і покажчик кінця пересувається до цієї ланки.
Черговий елемент черги: функції присвоюється значення першого елемента, покажчик початку пересувається на одну ланку.
Remove = Sn ^. Elem;
Sn: = Sn ^. Next ;
Sk
Для того щоб не було заповнення пам'яті непотрібною інформацією, використовують процедуру dispose , яка звільняє пам'ять.
P: = Sn;
Remove = Sn ^. Elem;
Sn: = Sn ^. Next;
Dispose;
Тема № 3: деки .
грудня як динамічна структура даних включає в себе характерні особливості черги і стека. Переміщення в черги здійснюється від її лівого кінця до правого, тобто від першого до останньому елементу. У стеці рух також йде в одну сторону, але порядок проходження елементів зворотний - від останнього елемента до першого. Грудень ж є двонаправленим списком, де рух може здійснюватися в обидві боку. Дек, як і чергою, визначається посиланнями на свої два кінця, однак, в відміну від черги, можна обробляти елементи на початку, в кінці і в середині.
грудня можна представити у вигляді ланок, кожен з яких складається з трьох полів: перше поле - поле елемента, друге - поле посилання на наступний елемент, третє - поле посилання на попередній. У схемі є дві посилання nil , кожна з яких обмежує рух по деку на його кінцях. Спосіб опису використовуваних типів даних, порівняємо з чергами, але тут вже є три поля.
Uses CRT ; {опис змінних}
Type typeelem = Integer;
connect = ^ data;
data = Record
elem: typeelem;
Next: connect;
Pred : connect
End ;
Процес вставки ланки в дек істотно відрізняється від раніше розглянутих випадків. У деці, як і в динамічній ланцюжку загального вигляду, новий елемент можна вставляти в будь-якому його місці, а, крім того, враховуючи двосторонній зв'язок ланок в деці, можна поставити питання про вставці до або після зазначеного елемента. Звідси випливає, що для вставки елемента в дек необхідно мати дві процедури: процедуру вставки елемента до заданого ланки і процедуру вставки елемента після заданого ланки. Вставка ланки в дек також супроводжується встановленням чотирьох зв'язків.
Для зменшення процедур можна використовувати допоміжні процедури:
Procedure insert1;
{занесення елемента в дек після заданого ланки}
var s1, s2, p: connect;
Begin
s1: = sn1;
s2: = sn2;
while s1 ^. elem <> y do s1: = s1 ^. next;
while s2 ^. pred ^. elem <> y do s2: = s2 ^. pred;
new;
p ^. elem: = x;
p ^. next: = s2;
p ^. pred: = s1;
s2 ^. pred: = p;
s1 ^. next: = p;
end;
{процедура Insert1 використовується при вставці елементу після заданого ланки за умови що це не початок або не кінець дека.}
Procedure insert3;
{занесення елемента в дек до заданого ланки}
var s1, s2, p: connect;
Begin
s1: = sn1;
s2: = sn2;
while s1 ^. next ^. elem <> y do s1: = s1 ^. next;
while s2 ^. elem <> у do s2: = s2 ^. pred;
new;
p ^. elem: = x;
p ^. next: = s2;
p ^. pred: = s1;
s2 ^. pred: = p;
s1 ^. next: = p;
end;
{процедура Insert3 використовується при вставці елементу до заданого ланки за умови що це не початок або не кінець дека}
Procedure insert2;
{занесення елемента в дек}
var p: connect;
Begin
if k = 'до ' then begin
new;
p ^. next: = nil;
p ^. elem: = x;
p ^. pred: = sn2;
sn...
