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


 

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

55258. Найважливіші принципи розміщення продуктивних сил, їх значення для ефективного розміщення підприємств і галузей 24.31 KB
  Принцип розміщення підприємств згідно з раціональними формами суспільної організації виробництва. До таких форм належать концентрація, спеціалізація, кооперування й комбінування.
55260. Природно-ресурсний потенціал, його структура. Забезпеченість України природними ресурсами 25.81 KB
  Природно-ресурсний потенціал території – цілісна система складноорганізованих обєктів, цілісність якого визначається закономірним сполученням взаємозумовлених природних і соціально-економічних звязків і залежностей, що поєднують територіально всі природні ресурси
55261. Презентация фрагментов работы учащихся 7-го класса по созданию учебного проекта «Построение средневекового города в Киевской Руси и Британии» (в рамках «global simulation») 58 KB
  Смещается акцент с фронтальной на групповую парную и самостоятельную работу результат выводится на продуктивный уровень обеспечивается развивающий потенциал уроков наряду с познавательной активностью и в довершении способствует формированию навыков командной работы. Тема: Презентация фрагментов работы учащихся 7го класса по созданию учебного проекта Построение средневекового города в Киевской Руси и Британии в рамках globl simultion Тип урока: интегрированный с использованием билингвальных технологий. Цели урока: представить...
55263. Основні фактори розміщення продуктивних сил, їх вплив на розміщення виробництва 25.69 KB
  Фактори розміщення це реалізація закономірностей і принципів при врахуванні конкретних умов, що впливають на вибір місць розташування промислових підприємств і формування територіально-виробничих комплексів.
55264. Поняття компютерної презентації. Основне призначення системи підготовки презентації 68.5 KB
  Мета уроку: навчальна: отримати уявлення про мультимедіа, познайомитися з програмою для створення мультимедійних презентацій; навчитися технології створення і демонстрації електронних презентацій; розвиваюча: розвиток мислення, пізнавальних інтересів, навиків роботи на компютері, роботи з мультимедійними програмними засобами...
55265. Чисельність населення України, особливості його динаміки. Природний рух населення. Демографічна ситуація в Україні, основні шляхи її розв’язання 25.61 KB
  Демографічні передумови є найважливішою складовою розміщення продуктивних сил. Населення країни фактор її комплексного економічного та соціального розвитку. Населення це трудові ресурси і споживач, яке впливає на формування міжрайонних функцій виробництва, потужність і структуру потоку продукції, що вивозиться за межі певної території, розвиток місцевого виробництва.
55266. Комп’ютерна презентація 107.5 KB
  Мета: 1) ввести поняття “презентація”, навчити учнів проектувати презентації, ознайомити з програмою Power Point та її можливостями. З’ясувати призначення комп’ютерної презентації. 2) розвивати алгоритмічне та логічне мислення, вміння порівнювати, виділяти головне, роботи узагальнення і висновки. Розвивати пізнавальну, комунікативну та інформаційну компетентності.