68990

Поняття черги і стека

Лекция

Информатика, кибернетика и программирование

Поняття стека Поняття черги У програмуванні поняття черги як динамічної структури даних використовують для моделювання процесів пов’язаних з почерговим виконанням деяких замовлень. Поняття стека Другий вид черги називають стеком.

Украинкский

2014-09-28

35.5 KB

1 чел.

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


 

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

18087. Цивільний захист, конспект лекцій 699 KB
  Навчальна дисципліна «Цивільний захист» є нормативною дисципліною, що включається в навчальні плани як самостійна дисципліна обов’язкового вибору. Вона зберігає свою самостійність за будь - якої організаційної структури вищого навчального закладу.
18088. Технология программирования на языке Java. Работа с массивами в Java 561.5 KB
  Лабораторная работа 4 Технология программирования на языке Java. Работа с массивами в Java 1. Цель работы Целью работы является приобретение навыков программирования с использованием операторов управления и массивов в языке программирования Java. 2. Состав рабоч
18089. ОСНОВИ ЗАКОНОДАВСТВА УКРАЇНИ ПРО ОХОРОНУ ПРАЦІ 79.5 KB
  ОСНОВИ ЗАКОНОДАВСТВА УКРАЇНИ ПРО ОХОРОНУ ПРАЦІ Тема 1.1. ЗМІСТ ЦІЛІ І ЗАДАЧІ ОХОРОНИ ПРАЦІ Навчальні питання лекції Місце і роль охорони праці в трудовій діяльності нашого суспільства. Законодавчі та нормативноправові акти з охорони праці. Основні п
18090. ПРАВОВЕ РЕГУЛЮВАННЯ ОХОРОНИ ПРАЦІ 70 KB
  Тема 1.2. ПРАВОВЕ РЕГУЛЮВАННЯ ОХОРОНИ ПРАЦІ Практичне заняття 2 години. Навчальні питання занять: Гарантії прав громадян з охорони праці. Нормування праці і відпочинку. Трудова дисципліна. Література: Законодавство України про охорону праці // Зб...
18091. ОХОРОНА ПРАЦІ ЖІНОК, НЕПОВНОЛІТНІХ, ТА ІНВАЛІДІВ 72.5 KB
  Тема 1.3 ОХОРОНА ПРАЦІ ЖІНОК НЕПОВНОЛІТНІХ ТА ІНВАЛІДІВ Лекція 2 години Навчальні питання лекції: Охорона праці жінок. Охорона праці неповнолітніх. Охорона праці інвалідів.. Література: Законодавство України про охорону праці // Збірни
18092. МЕДИЧНЕ ЗАБЕЗПЕЧЕННЯ ОХОРОНИ ПРАЦІ 56 KB
  Тема 1.4 МЕДИЧНЕ ЗАБЕЗПЕЧЕННЯ ОХОРОНИ ПРАЦІ Практичне заняття 2 години Навчальні питання занять: Види медичного забезпечення охорони праці. Порядок організації і проведення медичних оглядів. Права та обовязки підприємств і працівників щодо медичног...
18093. СОЦІАЛЬНИЙ ЗАХИСТ ПРАЦІВНИКІВ 119 KB
  Тема 1.5. СОЦІАЛЬНИЙ ЗАХИСТ ПРАЦІВНИКІВ Лекція 2 години. Навчальні питання лекції: Державне соціальне страхування. Соціальний захист громадян на ринку праці. Регулювання трудових відносин Література: Законодавство України про охорону праці //...
18094. ПСИХОФІЗІОЛОГІЯ ПРАЦІ 119 KB
  Тема 2.1. ПСИХОФІЗІОЛОГІЯ ПРАЦІ Лекція 2 години. Навчальні питання лекції: Психофізіологічні аспекти праці. Критерії тяжкості та напруженості праці. Адаптація трудової діяльності людини. Література: М.П.Гандзюк Є.П.Желібо М.О.Халімовський. Основи охо
18095. ГІГІЄНА ПРАЦІ І ВИРОБНИЧА САНІТАРІЯ 56.5 KB
  Тема 2.2 ГІГІЄНА ПРАЦІ І ВИРОБНИЧА САНІТАРІЯ Практичне заняття 2 години Навчальні питання занять: Основні поняття гігієни праці і виробничої санітарії. Класифікація умов праці. Пільги і компенсації за шкідливі і важкі умови праці. Література: ...