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


 

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

70663. Патология диафрагмы 255.59 KB
  Грудинная часть диафрагмы самый незначительный отдел диафрагмы начинается от задней поверхности мечевидного отростка и переходит в сухожильный центр. Реберная часть диафрагмы составляет наибольшую часть диафрагмы и начинается зубцами от внутренней поверхности костных и хрящевых...
70664. ЗАБОЛЕВАНИЯ МОЛОЧНОЙ ЖЕЛЕЗЫ 100.5 KB
  Молочная железа располагается на передней поверхности грудной клетки от III до VII ребра. Паренхима состоит из 15-20 трубчато-альвеолярных желёз, открывающихся на вершине соска. Молочная железа находится в соединительнотканном футляре и условно делится на 4 квадранта – 2 наружных...
70665. ЗАБОЛЕВАНИЯ ПИЩЕВОДА 165.5 KB
  Анатомия и физиология пищевода Пищевод полая цилиндрическая мышечная трубка соединяющая глотку с желудком и расположенная на уровне С6Th11 длиной примерно 25 см. С практической точки зрения в грудном отделе пищевода целесообразна следующая топография: Верхняя часть до дуги аорты.
70666. Острая кишечная непроходимость 130 KB
  Непроходимость кишечника – это синдром, характеризующийся нарушением продвижения кишечного содержимого по ЖКТ от желудка до анального отверстия. Часто именуется илеусом (ileus – от слова ileos – заворот кишечника по-гречески), хотя это относится только к частному виду непроходимости – завороту.
70667. МЕХАНИЧЕСКАЯ ЖЕЛТУХА 72 KB
  Большая группа болезней билиарной системы и поджелудочной железы сопровождается развитием механической непроходимости желчных протоков проявляющейся появлением у больного желтушной окрашенности кожи и склер что ошибочно привело к объединению всех этих заболеваний...
70668. ОПУХОЛИ И КИСТЫ СРЕДОСТЕНИЯ 207.28 KB
  Под средостением следует понимать комплекс органов и нервно-сосудистых образований, заключенных между обеими средостенными плеврами и окруженных значительным количеством клетчатки.
70669. ОСТРЫЙ И ХРОНИЧЕСКИЙ ХОЛЕЦИСТИТ 100.5 KB
  Исследование органов брюшной полости: осмотр: форма живота участие в дыхании видимое увеличение желчного пузыря; пальпация: а тонус брюшных мышц локализация болезненности пальпация...
70670. ПАНКРЕАТИТ 91.5 KB
  Железа располагается позади желудка, в сальниковой сумке, забрюшинно; спереди и сзади покрыта расходящимися листками брыжейки поперечно-ободочной кишки; позади нее располагается солнечное сплетение.
70671. Перитониты. Анатомия и физиология брюшины 108.5 KB
  Брюшина это серозный покров стенок париетальная брюшина и органов брюшной полости висцеральная брюшина. Нижний этаж брюшной полости может быть осмотрен после того как большой сальник и поперечно-ободочная кишка будут отвернуты вверх.