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
  Цели урока: познакомить учащихся с творчеством выдающихся поэтов и композиторов эпохи серебряного века; развивать умение вслушиваться в музыку стихотворений и музыкальных произведений развивать воображение творческие способности...