Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Стеки

Содержание

СТЕКИСтек – это структура данных, организованная по принципу LIFO – последний вошел, первый вышел.
СТЕКИ СТЕКИСтек – это структура данных, организованная по принципу LIFO – последний вошел, первый вышел. СТЕКИДля стека не важно фактическое местоположение элементов в памяти. В этом его СТЕКИМассив хранит элементы последовательно, поэтому получение любого из них занимает O(1).Каждый элемент СТЕКИПоиск элемента и в массиве, и в стеке в худшем случае сводится СТЕКИВставка или удаление элемента в массиве требует времени O(n)В стеке данные добавление СТЕКИПри удалении элемента из массива память, занимаемая удаленным элементом, не освобождается.При удалении СТЕКИВставка элемента в стек требует дополнительной памяти лишь для нового элемента.Вставка элемента СТЕКИОперации над стеком:Добавление нового элемента – pushУдаление последнего элемента – popЧтение вершины – top PUSH/POPВ операциях вставки/удаления происходит замена головного элемента стека.При добавлении, новый элемент становится PUSH/POPPopPush ПРОБЛЕМЫВозможно, что элементы, добавленные в стек в начале, так и не будут #include #include using namespace std;int main(){stack st;return 0;}STL:STACK STL:STACKОперации:pop – удаление элементаempty – проверка на пустотуswap– обмен содержимого с другим STL:STACK - EMPLACE#include #include using namespace std;struct some{int a, b, c;some(int a, ДЕКИДеки располагаются в памяти так же, как и стеки.В отличии от стека, ДЕКИВставка и удаление данных производится за O(1).Получение, вставка и удаление произвольного элемента ДЕКИДеки требуют меньше памяти для вставки, чем массивы.Это связано с тем, что ДЕКИОперации над деком:Вставка в начало и конец дека – push_front, push_backУдаление из
Слайды презентации

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

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

LIFO – последний вошел, первый вышел.


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

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

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

последовательно.

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

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

них занимает O(1).
Каждый элемент стека хранит данные только о

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

Слайд 5 СТЕКИ
Поиск элемента и в массиве, и в стеке

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

в худшем случае сводится к полному перебору элементов –

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

Слайд 6 СТЕКИ
Вставка или удаление элемента в массиве требует времени

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

O(n)

В стеке данные добавление и удаление данных происходит только

в конце и занимает время O(1).

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

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

элементом, не освобождается.
При удалении элемента из стека, занимаемая им

память уменьшится.

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

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

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

памяти до размера ещё одного массива.

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

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

элемента – pop
Чтение вершины – top


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

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

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

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

Слайд 11 PUSH/POP
Pop
Push

PUSH/POPPopPush

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

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

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

может быть длительным.




Слайд 13 #include
#include
using namespace std;
int main()
{
stack

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

st;
return 0;
}
STL:STACK


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

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

обмен содержимого с другим стеком
size – количество элементов в

стеке
push – добавление элемента в стек
emplace – создание и добавление элемента в стек


Слайд 15 STL:STACK - EMPLACE
#include
#include
using namespace std;
struct some{
int

STL:STACK - EMPLACE#include #include using namespace std;struct some{int a, b, c;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(1).Получение, вставка и удаление произвольного

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

за O(n).


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

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

связано с тем, что элементы в деке расположены не

в одной области памяти.

  • Имя файла: steki.pptx
  • Количество просмотров: 103
  • Количество скачиваний: 0