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, хоча вершина й переноситься на наступну ланку, попередня вершина залишається в пам'яті.


 

А также другие работы, которые могут Вас заинтересовать

33471. Форми співучасті 29 KB
  У такому разі говорять про просту і про складну співучасть: 1 проста співучасть співвиконавство співвинність має місце там де всі співучасники є виконавцями злочину і отже всі вони виконують однорідну роль. Але з погляду форми співучасті їх ролі однорідні всі вони безпосередньо виконують дії описані в диспозиції статті Особливої частини КК як ознаки об'єктивної сторони конкретного складу злочину в даному випадку розбою; 2 складна співучасть співучасть з розподілом ролей виявляється в тому що співучасники виконують різнорідні...
33472. Законодавство 29 KB
  Статті Загальної частини КК містять норми що встановлюють принципи та загальні положення кримінального права; чинність кримінального закону в просторі та часі; визначають поняття злочину; стадії вчинення злочину; ознаки субєкта злочину; зміст вини; співучасть у вчиненні злочинів; види множини злочинів; обставини що виключають злочинність діяння; підстави звільнення від кримінальної відповідальності від покарання та його відбування; загальні засади призначення покарання. Загальна і Особлива частини КК взаємозвязані між собою і складають...
33473. Амністія 28 KB
  Тому акт амністії може полягати у звільненні від покарання основного і додаткового скороченні строку покарання звільненні від додаткового покарання. Помилування акт глави держави за яким певна особа чи кілька осіб повністю або частково звільняється від покарання або до неї застосовується більш м'яке покарання або ж з особи знімається судимість. 87; б повного або часткового звільнення від відбування як основного так і додаткового покарання; в заміни покарання або його невідбутої частини більш м'яким покаранням; г зняття...
33474. Види покарань, які застосовуються до неповнолітніх і особливості їх призначення 32 KB
  98 це такі основні види покарання: 1 штраф; 2 громадські роботи; 3 виправні роботи; 4 арешт; 5 позбавлення волі на певний строк. Крім того значно меншими є строки цих покарань: громадські.роботи можуть бути призначені на строк від тридцяти до ста двадцяти годин і тривалість їх не може перевищувати двох годин на день; строк виправних робіт встановлений від двох місяців до одного року при цьому відрахування в прибуток держави призначаються судом у розмірі від п'яти до десяти відсотків. 101 арешт полягає у триманні неповнолітнього в...
33475. Співучасники в злочині можуть виконувати різні ролі 31.5 KB
  Виконавцем (співвиконавцем) вважається особа, яка у співучасті з іншими субєктами злочину безпосередньо чи шляхом використання інших осіб
33476. Вина 46 KB
  Форми вини — це зазначені в кримінальному законі сполучення певних ознак свідомості і волі особи, що вчиняє суспільно небезпечне діяння
33477. Виправні роботи 26 KB
  57 КК застосовуються до особи за місцем роботи на строк визначений за вироком суду з відрахуванням у доход держави відповідного відсотка її заробітку. Виправні роботи призначаються на строк від шести місяців до двох років і обов'язково супроводжуються відрахуванням із суми заробітку засудженого у доход держави в розмірі встановленому вироком суду в межах від десяти до двадцяти відсотків заробітку засудженого. Виправні роботи це покарання яке широко застосовується на практиці.
33478. Громадські роботи 24.5 KB
  56 КК полягають у виконанні засудженим у вільний від роботи чи навчання час безоплатних суспільне корисних робіт вид яких визначають органи місцевого самоврядування. Громадські роботи встановлюються на строк від шістдесяти до двохсот сорока годин і відбуваються не більш як чотири години на день.
33479. Звільнення від кримінальної відповідальності 26 KB
  Перебіг давності переривається в разі ухилення особи від органу досудового розслідування або суду або в разі вчинення іншого злочину середньої тяжкості тяжкого чи особливо тяжкого. Давність не застосовується в разі вчинення таких злочинів: ст.