Стек (Stack, Pinu, LIFO) Стек является одной из наиболее используемых и наиболее важных структур данных. Стеки применяются очень часто: Stekke kasutatakse. - презентация

1 Стек (Stack, Pinu, LIFO) Стек является одной из наиболее используемых и наиболее важных структур данных. Стеки применяются очень часто: Stekke kasutatakse väga tihti: -Распознавание синтаксиса в компиляторе (kompilaatori süntaksi hindamine) -Оценка выражений (avaldise hindamine) -Передача параметров функциям (funktsioonide parameetrite edastamine) -Выполнение вызова функции (funktsioonide väljakutsumine) -Возврат из функции (tagastamine funktsioonidest)

2 Стек предназначен для хранения элементов, доступных естественным путём в вершине стека, например: Стопка подносов (kandikud pakis) Груда тарелок (taldrikud pakis) Шампур с нанизанными овощами (šašlõkivarras juurviljadega) Oперации со стеком: (operatsioonid stekiga) - добавляющие (Push) lisamine - удаляющие / извлекающие (Pop) eemaldamine/kustutamine. Kогда стек достигает максимального количества элементов, наступает ситуация полноты стека (stack full) – в случае использования массивов. Другая крайность – нельзя взять поднос с пустой полки. Условие пустого стека (stack empty) подразумевает, что нельзя удалить\извлечь элемент.

3 А A B A B C A B A A D Push APush BPush CPop Push D Помещение в стек и извлечение из стека. Lisamine ja kustutamine stekist. C B

4 Объявление объекта типа Stack. Steki deklareerimine. struct Solm { info;//andmed Solm *next;//järgmise elemendi aadress }; Каждый элемент стека состоит из 2-х полей: информационного и адресного данные Адрес следующего узла данные Адрес следующего узла sõlm

5 Указатель на вершину стека. Tipu steki viit. Solm *Esim; Esim Sõlm

6 Создание пустого стека. Tühja steki koostamine. Esim=NULL; //stekk on tühi NB! NULL – это не нулевой адрес, а отсутствие конкретного адреса памяти. NULL on mälu aadressi puudumine.

7 Добавление первого элемента в стек. Esimese elemendi lisamine. Р NULL andmed Esim p=new Solm; //mälu esiletõstmine p->info=andmed; //kirjutame andmed p->next=NULL; //järgmine puudub Esim=p; //tipu stekiks saab uus element

8 Добавление следующего элемента. Järgmise elemendi lisamine. P =new Solm; p->info=andmed; //kirjutame andmed p->next=Esim; //järgmine on kunagine element Esim=p; //esimene sai uueks elemendiks NULL andmed Р Esim

9 Удаление элемента из вершины стека. Elemendi kustutamine steki tipust. NULL Esim p=Esim; //viit p teab esimese elemendi aadressi Esim=p->next; //tipu element on järgmine element delete p; //kustutada element p

10 Пример применения стека. Steki/Pinu kasutamise näidis. Выражение(avaldis) -8 + (4 * ^2) / 3 cодержит(sisaldab): Унарный (unaarne) оператор – (минус) Бинарные (binaarsed) операторы +, *, /, ^(степень/aste) Операнды(operandid) 8, 4, 12, 5, 2, 3 Круглые скобки (sulud)

11 Пример применения стека (продолжение). Выражение записывается в инфиксной (infix) форме, если каждый бинарный оператор помещается между его операндами и каждый унарный оператор предшествует его операнду. Avaldis on infix vormis, kui binaarne operaator asub operantide vahel, ning unaarne operaator asub operantide ees. Например, выражение * 2 является инфиксным. Avaldis * 2 on infix vormis.

12 Инфиксное выражение вычисляется алгоритмом, который использует два стека для различных типов данных. Infix avaldist arvutatakse algoritmi abil, mis kasutab kahte stekki. Пример применения стека. 1.Для хранения операндов (operantide hoidmiseks); 2. Для хранения операторов (operaatori hoidmiseks).

13 Альтернативой рассмотренной форме является постфиксное (postfix) представление, в котором операнды предшествуют оператору. Kui operandid eelnevad operaatorile, siis avaldis on postfix vormis. Например, инфиксное выражение «А+В» записывается в постфиксной форме как «А В +». Näiteks, infix avaldis «А+В» on postfix vormis «А В +». infix: a+b*c=a+(b*c) postfix: a b c * + Пример применения стека.

14 А * В + С Стек 1 Стек 2 А * В * + С + АВ*С+

15 Пример применения стека. A * B + C A B * C + A * B * C *D *E *F A B * C * D * E * F* A + (B * C + D) / E A B C * D + E / + (B*B–4 *A*C)/(2*A) B B * 4 A * C * – 2 A * / Infix Postfix В постфиксной форме переменные и числа вводятся по мере их появления, а оператор – там, где имеются 2 его операнда.

16 Постфиксное выражение оценивается алгоритмом, который просматривает выражение слева направо и использует стек. Читаем каждый терм и в зависимости от его типа выполняем действия. Инфиксное выражение 4+3*5 записывается в постфиксной форме как *+ Push 4 4 Push Push Pop 4 5*3=15 Pop 15+4=19

17 Как работает электронный калькулятор? Kuidas töötab kalkulaator? Пользователь вводит математическое выражение с числами (операндами) и операторы. Kasutaja sisestab avaldis numbritega ja tehted. Калькулятор использует один стек для вычисления числовых результатов. Kalkulaator kasutab ühte stekki tulemuste avaldamiseks.

18 Описание программы, реализующей работу со стеком. Programmi kirjeldamine. Функции (funktsioonid): -Добавление элемента в вершину стека(lisamine) -Удаление элемента из вершины стека(eemaldamine) -Удаление всех элементов из стека с освобождением памяти(kõikide elementide eemaldamine) - Вывод на экран содержимое стека(väljastamine ekraanile) Main() : инициализация вершины стека, вызов функций (steki tipu initsialiseerimine, funktsioonide väljakutsumine)

19 Добавление элемента в вершину стека. Elemendi lisamine. void Push( ); Функция получает в качестве параметра значение нового элемента и сохраняет его в вершине стека. Funktsioon kirjutab oma parameetri steki tippu.

20 p=new Solm; //malu uuele elementile int andmed;//muutuja coutandmed; //kui lisame esimene element if (Esim==NULL) { p->info=andmed; // p->next=NULL;//jargmine puudub Esim=p; //Esim teab nuud aadres //1.elem } else //kui stekkis on juba elementid { p->info=andmed; p->next=Esim; Esim=p; //uus element on esimene stekkis }

21 Удаление элемента из вершины стека. Elemendi eemaldamine steki tipust. Pop (); Функция удаляет элемент из вершины стека и возвращает значение этого элемента главной функции main(). Funktsioon eemaldab elemendi steki tipust.

22 if (Esim!=NULL) { //eemaldame 1.elem tipust u=Esim; Esim=u->next; delete u; } else cout

23 Удаление всех элементов из стека с освобождением памяти. Kõikide elementide eemaldamine void ClearStack(); В цикле пока стек не опустеет удаляются все его элементы и указатель на вершину стека получает значение NULL. Tsüklis eemaldatakse kõik elemendid kuni stekis on elemendid.

24 Вывод на экран всех элементов, содержащихся в стеке. Ekraanile väljastamine. void PrintStack(); Функция в цикле просматривает весь стек и выводит на экран значения поля info в каждом узле стека. Funktsioon analüüsib kogu stekki ja väljastab ekraanile info andmed igas steki sõlmes.

25 if (Esim!=NULL { u=Esim; cout info next!=NULL) { u=u->next; cout info

26 Задания. Ülesanded. 1.Составить программу, реализующую работу со стеком. Koostada programm, mis realiseerib töö stekiga. 2. Составить программу, моделирующую работу постфиксного калькулятора, имеющего операторы +, -, *, / и ^ (возведение в степень). Калькулятор принимает данные с плавающей точкой и вычисляет выражения. Koostada programm, mis modeleerib postfix kalkulaatori tööd, kasutades tehteid +, -, *, / ja ^ (astmed). Kalkulaator võtab vastu kümnendmurru andmed ja arvutab avaldised.