Структуры данных – что такое стек

Структуры данных - что такое стек

Что такое структура данных?

Это контейнер, который хранит и обрабатывает информацию в определенном виде.

Сегодня поговорим о стеке.

Что такое стек?

Стек — это структура данных, в которой элементы добавляются и удаляются в порядке «последним пришел, первым ушел». Из-за такого поведения их иногда называют списками LIFO, или просто LIFO.

Эти элементы могут изменяться только с одной стороны, называющейся вершиной стека.

Пример стека из жизни – стопка книг на столе, тарелки на столе и т.п. Чтобы получить книгу из середины стопки, сперва придется удалить книги сверху.

Операции со стеками:

  • Push – вставка элемента наверх стека
  • Pop – получение верхнего элемента и его удаление
  • isEmpty – возвращает true, если стек пуст
  • Top – получение верхнего элемента без удаления
Структуры данных - что такое стек

Если рассмотреть разработку под iOS, то яркий пример – UINavigationController. Когда вы делаете push – добавляете контроллер в стек, pop – получаете последний контроллер и возвращаетесь на предыдущий экран и т.д.

Плюсы стека

В высокой скорости работы на ЦП. Это всего лишь пара инструкций и время цикла обновления байта стека очень мало. Для распределения стека не требуется блокировка, потому что они используют локальное хранилище потоков, что является еще одним огромным выигрышем в производительности.

Локальное хранилище потоков (TLS) – это выделенная область хранения, доступ к которой может получить только один поток. Переменные TLS можно рассматривать как глобальные переменные, которые видны только определенному потоку, а не всей программе.

У стека единственный параметр, с которым он работает – это указатель положения стека – поэтому все операции со стеком быстрые.

Но это уже отдельная статья.

Минусы стека

Минус заключается в размере стека – это фиксированная величина, и нельзя изменить размер после его выделения.

Минус еще в том, что доступ к нему только последовательный.

Реализация стека на основе массива

Эта одна из самых популярных реализаций стека.

Создадим структуру и методы, которые реализуют операции со стеком, про которые написаны выше в тексте:

Структуры данных - что такое стек

Со стеками мы работаем каждый день, даже не думая об этом.

Теперь мы имеем хотя бы представление об этом.

Если у вас есть что дополнить к статье, я буду только рад, чтобы информации было как можно больше.

Всего просмотров: 94 , Просмотров сегодня: 1 

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *