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


 

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

22981. Робота зі співпроцесором 3.19 MB
  Обгрунтування необхідності співпроцесора Хоча мікропроцесор К1810ВМ86 оперує з 16розрядними числами відносна точність його обчислень не дуже висока. Такий допоміжний процесор має назву співпроцесора. Включення співпроцесора Для спільної роботи зі співпроцесором мікропроцесор МП86 слід включити у максимальний режим = 0.
22982. Тенденції у розвитку мікропроцесорної техніки 1011.5 KB
  Другий шлях полягає навпаки у роздрібненні секціонуванні мікропроцесора на окремі функціональні блоки і модулі кожний з яких виконує свої операції: операційний блок блок мікрокомандного керування блок памяті мікрокоманд та інше. Його система команд майже цілком співпадає з системою команд МП80 і відрізняється від неї лише декількома додатковими командами про які мова йтиме далі. У апаратному відношенні МП85 містить всі ті ж блоки що і МП80 але має крім того: блок керування перериваннями котрий розширює можливість звернення до...
22983. Система команд та методи адресації в мікропроцесорі КР1810ВМ86 1.05 MB
  Серед цього списку можна виявити що деякі команди не змінили ані форми ані змісту наприклад HLT NOP STC IN OUT JMPCALL тощо. Деякі команди зберегли свій зміст але мають дещо іншу мнемоніку: для МП80 INR DCR ANA ORA XRA JZ JNZ JC JNC для МП86 INC DEC AND OR XOR JE JNE JB JNB Зявилися принципово нові команди пoвязані з новими можливостями МП86: MUL множення; DIV ділення; NEG утворення доповняльного коду; NOTінверсія; TEST операція І без фіксації результату тільки заради...
22984. Мультипроцесорні системи 4.79 MB
  Дійсно звернення до памяті або до зовнішніх пристроїв та захоплення системної шини дозволяється одночасно лише одному з процесорів тоді як останні повинні в цей час переробляти раніш одержані дані або знаходитись в режимі очікування. Такий часовий розподіл загальних ресурсів системи має назву арбітражу системної шини і виконується групою пристроїв спеціальних ІМС так званих арбітрів шини. Арбітр шини дозволяє захоплення системної шини лише одному з процесорів що виставили запит тому котрий посідає найвищого пріоритету і...
22985. Мікропроцесори 80386 і 80486 4.79 MB
  Це дозволяє йому здійснювати обмін з памяттю зі швидкістю до 32 Мбайт сек і виконувати до 5 мільйонів операцій у секунду MIPS. Отже під час виконання одної команди відбувається декодування другої а третя видобувається з памяті. Усі можливості МП386 мультипрограмність віртуальна память захист пріоритети зповна відкриваються лише в захищеному режимі. У порівнянні з МП286 у МП386 існують істотні відміни в організації віртуальної памяті.
22986. Поняття про RISC-процесори. Процесори п’ятого та шостого поколінь 6.22 MB
  Процесори пятого та шостого поколінь Поняття про RISCпроцесори Якісний стрибок у розвитку мікропроцесорних систем відбувся з появою мікропроцесора 8086. Такі процесори і компютери дістали назву RISC процесорів та RISC компютерів на відміну від процесорів та компютерів зі складною системою команд Complex Instruction Set Computer CISC компютер. Перший справжній RISC компютер було створено наприкінці 70х років в університеті Берклі.
22987. Діагностика несправностей у мікропроцесорних системах 739 KB
  Тут можна навести таку наочну аналогію: візьміть на сторінці друкованого тексту вертикальний рядок літер що розташовані одна над одною і спробуйте встановити зміст тексту. Тому третя трудність полягає у тому щоб будьякимсь чином представити інформацію що міститься у вихідному тестсигналі у компактній та зрозумілій формі по якій можна було б судити про справність або несправність пристрою що перевіряється. Тестпрограма повинна бути періодичною щоб можна було проконтролювати відтворюваність її результатів від кількох актів тестування....
22988. Декотріі принципи роботи сучасних мікропроцесорів та ЕОМ 1.54 MB
  Вони показують яка команда виконується до якої комірки памяті або зовнішнього пристрою звертається процесор і містять іншу важливу і вичерпну інформацію. Після того як у програмі дається сигнал вивільнити мікросхему вміст усіх регістрів переписується в область памяті що має назву сегмента стану задачі TSS Taske State Segment. При роботі у мультипрограмному режимі можуть виникати певні труднощі з використанням оперативної памяті котра стає тепер вже загальною для кількох задач. Можливі непередбачені ситуації коли одна програма...
22989. Віртуальна пам’ять. Мікропроцесор 80286 4.24 MB
  Мікропроцесор 80286 Як добре відомо процесор може безпосередньо працювати лише з тією інформацією яка записана в його оперативній памяті. Однак обєм оперативної памяті у сучасних ЕОМ порівняно невеликий і часто виявляється недостатнім для розвязання більшменш складних задач. Віртуальна організація памяті дає користувачеві практично необмежений обєм памяті.