1 of 13

Стек

Структури от данни - въведение

2 of 13

Структури от данни

  • Начини да запазваме и четем данни, всеки със своите особености
  • Можем да си представим масива като структура от данни
    • Държи елементите “залепени” един до друг
    • Достапват се чрез индекс
    • Имаме краен брой елементи (големина)
  • Други такива структури са: стек, едносвързан списък, дърво, граф, двусвързан списък, опашка, речник, хийп …
  • Различните структури от данни са подходящи за решаване на различни проблеми

​

3 of 13

Сложност

  • По памет която използват
  • По време за:
    • Достъпване на елемент
    • Добавяне на елемент
    • Изтриване на елемент
    • Търсене на елемент
  • http://bigocheatsheet.com/
  • За различни проблеми използваме различни структури от данни
    • Понякога правим жертви
    • Опознай ги, за да ги обикнеш

4 of 13

RPN

  • Reverse polish notation a.k.a postfix notation или обратна полска нотация
  • 3 2 - е еквивалентно на 3 - 2
  • 3 2 + 5 + е еквивалентно на 3 + 2 + 5
  • 12 3 - 3 / е еквивалентно на (12 - 3 ) / 3
  • 5 3 2 + + е еквивалентно на 2 + 3 + 5

​

5 of 13

RPN калкулатор?

  • Как да направим калкулатор, който пресмята RPN изрази?
  • 3 2 + 5 + => 10
  • 9 5 2 + - 4 + 1 - => 5

6 of 13

Stack I

  • Абстрактна структура от данни
  • Още наричана LIFO - last in, first out
  • Пример: купчина контролни
    • Учениците оставят техните най-отгоре
    • Преподавателят взима най-отгоре
  • Сложност
    • Добавяне, премахване
    • Достъпване на елемент

7 of 13

Stack II

  • Push - добавяне на 1 елемент най-отгоре
  • Pop - вземане на най-горния елемент от�Стека
  • Top - “поглеждане” на най-горния елемент

8 of 13

Stack III

  • Да се дефинира структурата stack_t, която съдържа в себе си данните (като какво?), текущ брой елементи и капацитет
  • Да се дефинира функцията struct stack_t stack_init(int initial_capacity), която заделя памет за един стек със зададения капацитет
  • Да се дефинира функцията void stack_destroy(struct stack_t* st), която освобождава паметта за даденият стек

9 of 13

Stack IV

  • Да се дефинира int push(struct stack_t *stack, int elem), която добавя елемента към началото на стека
  • Да се дефинира int top(struct stack_t), която връща най-горния елемент
  • Да се дефинира int pop(struct stack_t *stack), която премахва най-горния елемент
  • Да се дефинира int size(struct stack_t stack), която връща колко елемента има в стек

10 of 13

Stack V

  • Да се дефинира int is_full(struct stack_t stack), която казва дали стека е пълен
  • Да се дефинира int is_empty(struct stack_t stack), която казва дали стека е празен
  • Да се дефинира int stack_resize(struct stack_t *stack), която увеличава капацитета на стека два пъти и запазва всички налични данни
  • Да се дефинира struct stack_t stack_copy(struct stack_t stack), която връща копие на подадения стек

11 of 13

RPN калкулатор!

  • Дефинирайте функцията float rpn_solve(char *rpn_exp), която използвайки стека решава дадения израз и връща разултата
    • Всички оператори са с 1 символ
    • Ще има само цифри т.е. всяко число заема 1 символ
    • Между всички числа и операции ще има точно по един интервал

12 of 13

За любознателните

  • Имплементирайте следният алгоритъм
  • https://en.wikipedia.org/wiki/Shunting-yard_algorithm
    • Приведете го до RPN

13 of 13

Въпроси?