68990
Поняття черги і стека
Лекция
Информатика, кибернетика и программирование
Поняття стека Поняття черги У програмуванні поняття черги як динамічної структури даних використовують для моделювання процесів пов’язаних з почерговим виконанням деяких замовлень. Поняття стека Другий вид черги називають стеком.
Украинкский
2014-09-28
35.5 KB
2 чел.
Лекція № 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, хоча вершина й переноситься на наступну ланку, попередня вершина залишається в пам'яті.
А также другие работы, которые могут Вас заинтересовать | |||
57768. | Теорема Піфагора | 271.5 KB | |
Мета: сформулювати і довести теорему Піфагора; познайомити учнів з біографією Піфагора; вчити застосовувати теорему до розвязання задачрозвивати логічне мислення; розвивати інтерес до математики... | |||
57769. | Союз гіпотенузи та катетів. Теорема Піфагора | 1.81 MB | |
Тип проекту: Пізнавальний дослідницький творчий За кількістю учасників: груповий За тривалістю підготовки: короткотривалий два тижні Епіграф: Не роби ніколи того що не знаєш але вчись усьому що потрібно знати і тоді будеш вести спокійне життя. | |||
57770. | Розв’язування квадратних рівнянь та рівнянь, що зводяться до квадратних | 6.68 MB | |
Мета: освітня – узагальнити та систематизувати знання учнів з теми: “Розв’язування квадратних рівнянь та рівнянь, що зводяться до квадратних”; виховна – виховувати самостійність, інтерес до вивчення математики... | |||
57771. | Питание и здоровье | 191 KB | |
Образовательная: установить связь между особенностями питания человека и его здоровьем; пояснить значение рационального питания поддержания здорового образа жизни; познакомить с распространенными болезнями человека... | |||
57772. | Питание и здоровье | 349 KB | |
Базовые понятия и термины: рациональное питание норма питания энергетический баланс. Здоровье человека его трудоспособность долголетие адаптация к изменчивым условиям окружающей среды в значительной степени зависит от правильного питания. Что же является основой рационального питания Нам предстоит сегодня узнать сообщение темы и целей урока запись в тетрадь. | |||
57773. | Програмне забезпечення ПК | 432.5 KB | |
Актуальність теми: Компютер - універсальний пристрій призначений для опрацювання інформації. Утім сам по собі компютер не володіє знаннями у жодній області свого використання. Якщо ми кажемо: компютер зробив мається на увазі що на компютері була виконана програма яка дозволила виконати ці дії. | |||
57774. | Різноманітність, значення та охорона плазунів | 83.5 KB | |
Мета: формувати такі компетентності учнів як: комунікаційну інформаційну логічну аналітичну продуктивну творчу діяльність дослідницьку технологічну мовленеву; ознайомити учнів з різноманітністю плазунів видами поширеними в Україні власному регіоні та рідкісними видами... | |||
57775. | Взаємне розміщення прямих на площині | 3.51 MB | |
Мета та задачі уроку: узагальнити й систематизувати знання учнів з теми; закріпити вміння застосовувати отримані знання під час розв’язування задач; розвивати логічне мислення, комунікативні навички... | |||
57776. | Отзвуки «Серебряного века» | 93.5 KB | |
Цели урока: познакомить учащихся с творчеством выдающихся поэтов и композиторов эпохи серебряного века; развивать умение вслушиваться в музыку стихотворений и музыкальных произведений развивать воображение творческие способности... | |||