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


 

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

55112. Банковский мультипликатор: сущность и механизм действия 18.77 KB
  Банковский мультипликатор представляет собой процесс увеличения (мультипликации) денег на депозитных счетах коммерческих банков в период их движения от одного коммерческого банка к другому
55114. ИСТОРИЯ РИТОРИКИ 217.5 KB
  Интерес представляет риторическое обучение в духовных академиях и старообрядческих общинах. В библиотеках Москвы, Киева, Санкт-Петербурга хранятся многочисленные рукописи учебников, созданных учителями риторики для своих учеников, различные сборники с риторическими статьями и школьными речами.
55115. Почвозащитная способность сельскохозяйственных культур и севооборотов. Проектирование севооборотов с учетом уклонов на пашне. Методические указания 318.5 KB
  Озимые зерновые пропашные культуры зернобобовые яровая пшеница гречиха Просо Пласт многолетних трав пропашные культуры озимые зерновые залежь Гречиха Пропашные яровые зерновые зернобобовые культуры Зернобобовые...
55116. Основы молекулярной генетики, моделирование процессов кодирования наследственной информации 38 KB
  Определить антикодоны транспортных РНК, которые осуществляют доставку к рибосомам следующих аминокислот: фенилаланин, серин, тирозин, цистеин, лейцин, треонин, лизин, глутамин.
55117. Рекультивация почв, засоленных и осолонцованных при загрязнении нефтепромысловыми сточными водами (НСВ). Методические указания 309 KB
  Цель занятия: научиться разрабатывать системы мероприятий по рекультивации засоленных и загрязненных НСВ земель; дать студентам знания: по известкованию почвы; изучить методы и расчеты норм известкования почвы; по гипсованию почвы; изучить методы и расчеты норм гипсования почвы; по засолению почв промывке почв; изучить методы и расчеты промывной нормы при засолении почвы....
55118. Единый социальный налог (взнос) 171 KB
  При однократном использовании данной льготы доходы за исключением оплаты труда наемных работников получаемые членами зарегистрированных в установленном порядке родовых семейных общин малочисленных народов Севера от реализации продукции полученной в результате...
55119. Рекультивация земель, загрязненных нефтью и нефтепродуктами. Методические указания 313 KB
  Ликвидация последствий разливов нефти проводится часто таким способом что происходит необратимое уничтожение плодородного слоя почвы например при сжигании нефти засыпке загрязненных участков грунтом вывозе загрязненной почвы в отвалы. 1988 смешивание загрязненных почв с чистой почвой для уменьшения содержания нефти и нефтепродуктов...