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


 

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

82971. Функции и виды прибыли 152 KB
  Для каждого студента факультета экономики и финансов важнейшим и приоритетным направлением является глубокое изучение экономических дисциплин, в частности такого предмета, как экономика предприятия. Для достижения должного уровня познания данной дисциплины необходим системный подход к ее исследованию.
82972. Гигиена ротовой полости и питания 848.42 KB
  Цель гигиены состоит в предотвращении заболеваний, сохранении и укреплении здоровья, создании оптимальных условий для жизнедеятельности человека методами профилактики. Результатом поставленной цели можно считать оптимизацию условий труда и жизни человека вследствие снижения заболеваемости и т.п.
82973. ДЕЗИНФЕКЦИЯ. СВЕДЕНИЯ ПО ВЕТЕРИНАРНОЙ САНИТАРИИ И ДЕЗИНФЕКЦИИ 52.66 KB
  Дезинфекция слагается из двух последовательно осуществляемых приемов: механической очистки и собственно дезинфекции.Удалением загрязнений создают условия для последующего свободного доступа химических средств в случае проведения дезинфекции к оставшимся на поверхностях микроорганизмам...
82974. Опухолевая прогрессия. Метастазирование, кахексия, рецидирование опухолей 47 KB
  Злокачественные опухоли зачастую становятся причинами смерти людей. Согласно цитологической и гистологической структуре опухолевых клеток и тканей выделяют доброкачественные и злокачественные опухоли. Доброкачественные опухоли. Такие опухоли растут медленно и как правило не метастазируют.
82975. Антропогенные факторы загрязнения гидросферы 45.11 KB
  Существование всего живого на земле и человека в частности основано на использовании воды. Установлено что более 400 видов веществ могут вызвать загрязнение воды. Постоянно загрязняются и подземные воды при просачивании промышленных и хозяйственно-бытовых стоков из хранилищ накопителей отстойников...
82976. Узагальнення та систематизація знань по темі «Поняття» 136 KB
  Систематизувати знання про поняття вдосконалювати вміння розв’язувати логічні задачі класифікувати та порівнювати предмети. Сьогодні ми закріпимо і узагальнимо наші знання з теми Поняття. Побудова Асоціативного куща спираючись на знання дітей по темі Поняття.
82977. Виготовлення геометричних фігур при допомозі аплікації. Порівняння фігур за кольором, розміром, формою 1.67 MB
  Мета: вчити виготовляти геометричні фігури з паперу за допомогою аплікаціїпорівнювати фігури за кольором формою розміром; розвивати розумові здібності мовлення творчі здібності учнів; виховувати любов до своєї родини; допомогти дитині зрозуміти які цінності є духовним фундаментом повноцінної...
82978. Творимо казковий світ «Кольорочас». We create the world of wonder «Colourtime» 623.5 KB
  Мета: географія ознайомити учнів з етапами формування української нації;сформувати в учнів поняття про національний склад населення та пояснити причини його строкатості; назвати етнографічні групи українців та національні меншини; обґрунтувати географію розміщення історико географічних етнографічних...
82979. Казки народів світу, Ш. Перро «Кіт у чоботях» 1.58 MB
  Мета: Продовжити знайомство з казками народів світу. Формувати в учнів уміння повно, точно, емоційно робити висновки і висловлювати судження про прочитане та посилатися під час відповіді на текст книжки; активізувати читацьку пам’ять; збагачувати словниковий запас...