Стеки

Сентябрь 7, 2022

Содержание

2. СТЕКИ Стек – это структура данных, организованная по принципу LIFO – последний вошел, первый вышел.
3. СТЕКИ Для стека не важно фактическое местоположение элементов в памяти. В этом его отличие от массива,
4. СТЕКИ Массив хранит элементы последовательно, поэтому получение любого из них занимает O(1). Каждый элемент стека хранит
5. СТЕКИ Поиск элемента и в массиве, и в стеке в худшем случае сводится к полному перебору
6. СТЕКИ Вставка или удаление элемента в массиве требует времени O(n) В стеке данные добавление и удаление
7. СТЕКИ При удалении элемента из массива память, занимаемая удаленным элементом, не освобождается. При удалении элемента из
8. СТЕКИ Вставка элемента в стек требует дополнительной памяти лишь для нового элемента. Вставка элемента в массив
9. СТЕКИ Операции над стеком: Добавление нового элемента – push Удаление последнего элемента – pop Чтение вершины
10. PUSH/POP В операциях вставки/удаления происходит замена головного элемента стека. При добавлении, новый элемент становится головным. При
11. PUSH/POP Pop Push
12. ПРОБЛЕМЫ Возможно, что элементы, добавленные в стек в начале, так и не будут прочитаны. Данные не
13. #include #include using namespace std; int main() { stack st; return 0; } STL:STACK
14. STL:STACK Операции: pop – удаление элемента empty – проверка на пустоту swap– обмен содержимого с другим
15. STL:STACK - EMPLACE #include #include using namespace std; struct some{ int a, b, c; some(int a,
16. ДЕКИ Деки располагаются в памяти так же, как и стеки. В отличии от стека, в деке
17. ДЕКИ Вставка и удаление данных производится за O(1). Получение, вставка и удаление произвольного элемента производится за
18. ДЕКИ Деки требуют меньше памяти для вставки, чем массивы. Это связано с тем, что элементы в
20. Скачать презентацию

Слайд 2

СТЕКИ
Стек – это структура данных, организованная по принципу LIFO – последний

вошел, первый вышел.

Слайд 3

СТЕКИ
Для стека не важно фактическое местоположение элементов в памяти.
В этом

его отличие от массива, хранящего элементы последовательно.

Слайд 4

СТЕКИ
Массив хранит элементы последовательно, поэтому получение любого из них занимает O(1).
Каждый

элемент стека хранит данные только о себе и положении следующего за ним элементе, поэтому время получения каждого из них - O(n).

Слайд 5

СТЕКИ
Поиск элемента и в массиве, и в стеке в худшем случае

сводится к полному перебору элементов – время поиска будет O(n).

Слайд 6

СТЕКИ
Вставка или удаление элемента в массиве требует времени O(n)
В стеке данные

добавление и удаление данных происходит только в конце и занимает время O(1).

Слайд 7

СТЕКИ
При удалении элемента из массива память, занимаемая удаленным элементом, не освобождается.
При

удалении элемента из стека, занимаемая им память уменьшится.

Слайд 8

СТЕКИ
Вставка элемента в стек требует дополнительной памяти лишь для нового элемента.
Вставка

элемента в массив может потребовать дополнительной памяти до размера ещё одного массива.

Слайд 9

СТЕКИ
Операции над стеком:
Добавление нового элемента – push
Удаление последнего элемента – pop
Чтение

вершины – top

Слайд 10

PUSH/POP
В операциях вставки/удаления происходит замена головного элемента стека.
При добавлении, новый элемент

становится головным.
При удалении из стека удаляется ссылка на последний элемент, а предпоследний элемент становится головным.

Слайд 11

PUSH/POP
Pop
Push

Слайд 12

ПРОБЛЕМЫ
Возможно, что элементы, добавленные в стек в начале, так и не

будут прочитаны.
Данные не упорядочены.
Получение произвольного элемента может быть длительным.

Слайд 13

#include
#include
using namespace std;
int main()
{
stack st;
return 0;
}
STL:STACK

Слайд 14

STL:STACK
Операции:
pop – удаление элемента
empty – проверка на пустоту
swap– обмен содержимого с

другим стеком
size – количество элементов в стеке
push – добавление элемента в стек
emplace – создание и добавление элемента в стек

Слайд 15

STL:STACK - EMPLACE
#include
#include
using namespace std;
struct some{
int a, b, c;
some(int

a, int b, int c){
this->a=a;
this->b=b;
this->c=c;}};

int main()
{ stack st;
st.push(f);
//st.push(1,2,3); - не заработает
st.emplace(1,2,3);// - создаст структуру с полями 1,2,3 и добавит её в стек
}

Слайд 16

ДЕКИ
Деки располагаются в памяти так же, как и стеки.
В отличии от

стека, в деке возможно добавление и в начало, и конец.

Слайд 17

ДЕКИ
Вставка и удаление данных производится за O(1).
Получение, вставка и удаление произвольного

элемента производится за O(n).
Поиск элементов происходит за O(n).

Слайд 18

ДЕКИ
Деки требуют меньше памяти для вставки, чем массивы.
Это связано с тем,

что элементы в деке расположены не в одной области памяти.