Лекція № 19
Тема: Поняття черги і стека
План заняття:
1. Поняття черги.
2. Поняття стека
Поняття черги
У програмуванні поняття черги як динамічної структури даних використовують для моделювання процесів, пов'язаних з почерговим виконанням деяких замовлень. Над чергою визначені дві операції: введення елемента в чергу і вибір елемента з черги для обслуговування з вилученням із черги. Є такі два види черг, що відрізняються дисципліною обслуговування:
1) черги з дисципліною обслуговування FIFO (First In -First Out) перший у чергу - перший з черги, тобто раніше буде обслужений той елемент, який раніше потрапив у чергу;
2) черги з дисципліною обслуговування LIFO (Last In -First Out) останній у чергу - перший із черги, тобто першим буде обслужений той елемент, який останнім потрапив у чергу.
Поняття стека
Другий вид черги називають стеком. Для відображення стека використаємо введену раніше структуру - динамічний ланцюг ланок. У цьому випадку єдино доступною позицією вважатимемо першу ланку ланцюга, яку називають вершиною стека. Нульової ланки тепер не потрібно, а значення вказівника, що визначає весь стек, є вказівка на вершину стека. В кожній ланці є вказівка на наступну, значення вказівки останньої ланки є nil.
Отже, стек можна описати за допомогою таких типів:
type
TypeElm=Char;
Link=^Ls;
Ls=record
Elem: Char;
Next: Link;
end;
Stack=Link;
Тепер, використовуючи ці описи, стек як об'єкт програми можна ввести за допомогою опису змінної:
var
St: Stack;
Схематично стек зображено на рис. 1.
……….
Рис 1. Стек
Перед формуванням стека його треба зробити порожнім за допомогою присвоєння
St:=nil;
Працюючи зі стеком, найчастіше використовують дві процедури: введення елемента в стек і вибір елемента зі стека. Процедура введення в стек містить як формальні параметри вказівку на потрібний стек і значення елемента, який уводять у цей стек:
program Form7;
type
TypeElm=Char;
Link=^Ls;
Ls=record
Elem: Char;
Next: Link;
end;
Stack=Link;
procedure lnStack(var St: Stack; Elm: Char);
var Rb: Link;
begin
new(Rb);
Rb^.EIem:=Elm;
Rb^.Next:=St;
St:=Rb;
end;
begin
end.
Процедура вибору зі стека полягає у виборі елемента, що є в його вершині, і присвоєнні значення цього елемента деякій змінній, а також ліквідації першої ланки стека:
program Form8;
type
TypeElm=Char;
Link=^Ls;
Ls=record
Elem: Char;
Next: Link;
end;
Stack=Link;
procedure OutStack(var St: Stack; var a: Char);
var Rb: Stack;
begin
Rb:=St;
a:=St^.EIm;
St:=St^.Next;
Dispose(Rb)
end;
begin
end.
Це найпростіший варіант процедури вибору із стека. Досконалішою буде процедура, яка враховує можливість порожнього стека і видає в цьому випадку повідомлення про спробу вибору елемента з порожнього стека. Інше можливе вдосконалення - знищення першої ланки стека за допомогою процедури Dispose. В нашій процедурі OutStack, хоча вершина й переноситься на наступну ланку, попередня вершина залишається в пам'яті.