Теоретичні відомості. Тема: Робота з елементами стеку.

Тема: Робота з елементами стеку.

Мета: Oзнайомитися з алгоритмами роботи з елементами стеку.

Теоретичні відомості.

Cтеком називається структура даних, що організована за принципом «останній прийшов – першим пішов».

Оскільки організація одновимірного масиву аналогічна лінійній структурі пам’яті комп’ютера, то логічним буде представлення стека саме у вигляді одновимірного масиву (див. малюнок)

А от організація обробки елементів цього масиву буде такою, що відповідає означенню структури даних. Для простішого розуміння поняття «стек» проведемо аналогію з стопкою книг.

Додаючи нову книжку в стопку, ми кладемо її зверху, тобто операція запису нового елемента відбувається в кінець масиву додаванням нового елемента. А для того щоб узяти книжки із середини стосу, нам треба всі верхні книжки по одній зняти у зворотному порядку щодо їх складання. Таким чином, операція читання зі стека відбувається також з кінця масиву, але в зворотному порядку.

Обробляючи елементи масиву, ми вводимо поняття поточного порядкового номеру елемента масиву і. В даному випадку нас цікавитиме лише останній елемент: ми його або зчитуємо(↑), або після цього записуємо новий елемент (↓).

Індекс останнього елемента стека називається вершиною. Це означає, що для обробки елементів стека на достатньо знати значення лише однієї величини і вершини стека.

Розглянемо реалізацію алгоритмів роботи з елементами стека мовою Pascal.

Перш за все треба оговорити критичні ситуації, які можуть виникнути при читанні та записі інформації. А саме: при читанні може виникнути ситуація, коли вже читати нема чого, тобто стек порожній, а при записі – стек переповнений, тобто досягнуто останнього елемента масиву, оскільки описуючи масив у програмі, ми повинні вказати межі зміни його індексу.

Процедура читання зі стека:

procedure read_from_stack;

begin

if i=0 then writeln('Stack is empty')

else

begin

writeln(a[i]);

dec(i);

end;

end;

Логічним є твердження, що на початку роботи програми з обробки елементів стека вершина стека повинна мати значення 0, оскільки в початковому стані дозволена лише операція запису в стек.

Процедура запису в стек може виглядати так:

procedure write_to_stack;

begin

if i> =n then writeln('Stack is full')

else begin

inc(i);

readln(a[i]);

end; end;

При виконанні програми, що реалізує роботу зі стеком, нам цікаво спостерігати за вмістом стека під час виконання операцій читання та запису. Для цього можна скористатися процедурою виведення поточного вмісту стека:

procedure print_stack;

var k: word;

begin

for k: =1 to i do

write(a[k], ' ');

writeln

end;

Корисною також є інформація про вміст усього масиву, відведеного для організації стека, під час обробки елементів стека. Саме при виконанні цієї процедури можна спостерігати за появою «сміття» в масиві та заміною його на нові значення при виконанні операції запису в стек.

procedure print_mas;

var j: word;

begin

for j: =1 to n do

write(a[j], ' ');

writeln

end;

Структура даних «стек» є структурою послідовного доступу.