Что такое структура данных?
Это контейнер, который хранит и обрабатывает информацию в определенном виде.
Сегодня поговорим о стеке.
Что такое стек?
Стек — это структура данных, в которой элементы добавляются и удаляются в порядке «последним пришел, первым ушел». Из-за такого поведения их иногда называют списками LIFO, или просто LIFO.
Эти элементы могут изменяться только с одной стороны, называющейся вершиной стека.
Пример стека из жизни – стопка книг на столе, тарелки на столе и т.п. Чтобы получить книгу из середины стопки, сперва придется удалить книги сверху.
Операции со стеками:
- Push – вставка элемента наверх стека
- Pop – получение верхнего элемента и его удаление
- isEmpty – возвращает true, если стек пуст
- Top – получение верхнего элемента без удаления
Если рассмотреть разработку под iOS, то яркий пример – UINavigationController. Когда вы делаете push – добавляете контроллер в стек, pop – получаете последний контроллер и возвращаетесь на предыдущий экран и т.д.
Плюсы стека
В высокой скорости работы на ЦП. Это всего лишь пара инструкций и время цикла обновления байта стека очень мало. Для распределения стека не требуется блокировка, потому что они используют локальное хранилище потоков, что является еще одним огромным выигрышем в производительности.
Локальное хранилище потоков (TLS) – это выделенная область хранения, доступ к которой может получить только один поток. Переменные TLS можно рассматривать как глобальные переменные, которые видны только определенному потоку, а не всей программе.
У стека единственный параметр, с которым он работает – это указатель положения стека – поэтому все операции со стеком быстрые.
Но это уже отдельная статья.
Минусы стека
Минус заключается в размере стека – это фиксированная величина, и нельзя изменить размер после его выделения.
Минус еще в том, что доступ к нему только последовательный.
Реализация стека на основе массива
Эта одна из самых популярных реализаций стека.
Создадим структуру и методы, которые реализуют операции со стеком, про которые написаны выше в тексте:
Со стеками мы работаем каждый день, даже не думая об этом.
Теперь мы имеем хотя бы представление об этом.
Если у вас есть что дополнить к статье, я буду только рад, чтобы информации было как можно больше.
Всего просмотров: 94 , Просмотров сегодня: 1
