Для чего нужны стеки?. Кратко и просто об одной из самых…

Содержание материала

Что такое стек простыми словами

По традиции рассказ начну с определения. Термин пришел из английского языка: слово stack переводится как «пробка».

Стек — это один из способов организации и хранения информации в программировании. Если говорить профессиональным языком, это одна из структур данных.

Википедия дает определение стеку как абстрактному типу данных, представленному в виде организованного по принципу LIFO списка элементов. В свою очередь, аббревиатура LIFO расшифровывается как last in — first out, то есть «пришел последним, а вышел первым».

Термин появился в середине XX века благодаря Алану Тьюрингу. В таких языках программирования как Python и Lisp стеком называют любой список, потому что для них доступны операции выталкивания (pop на английском) и проталкивания (push). Для стека характерна еще одна операция — чтение головного элемента (по-английски — peek).

Видео

Для чего нужен стек?

Главное предназначение стека — решение типовых задач, предусматривающих поддержку последовательности состояний или связанных с инверсионным представлением данных. В компьютерной отрасли стек применяется в аппаратных устройствах (например, в центральном процессоре, как уже было упомянуто выше).

Практически каждый, кто занимался программированием, знает, что без стека невозможна рекурсия, так как при любом повторном входе в функцию требуется сохранение текущего состояния на вершине, причём при каждом выходе из функции, нужно быстро восстанавливать это состояние (как раз наша последовательность LIFO).

Если же копнуть глубже, то можно сказать, что, по сути, весь подход к запуску и выполнению приложений устроен на принципах стека. Не секрет, что прежде чем каждая следующая программа, запущенная из основной, будет выполняться, состояние предыдущей занесётся в стек, чтобы, когда следующая запущенная подпрограмма закончит выполняться, предыдущее приложение продолжило работу с места остановки.

Способы реализации стека

Существует несколько способов реализации стека:

с помощью одномерного массива;
с помощью связанного списка;
с помощью класса объектно-ориентированного программирования.

Пример реализации стека с помощью одномерного массива Стек можно реализовать в виде следующей структуры:

1 2 3 4 5#define NMAX 100 struct stack { float elem[NMAX]; int top; };

NMAX — максимальное количество элементов в стеке; elem — массив из NMAX чисел типа float, предназначенный для хранения элементов стека; top — индекс элемента, находящегося в вершине стека.

Массив

Это непрерывный блок памяти. Из-за этого при маленьком размере стека массив будет занимать лишнее место. Ещё один недостаток в том, что каждый раз при увеличении размера массива придётся копировать все уже существующие элементы в новую ячейку памяти.

Как работает стек

Стек работает следующим образом:

Указатель TOP используется для отслеживания «верхнего» элемента стека.
После инициализации стека его значение равно -1. Так можно легко проверить заполненность стека: если TOP == -1, стек пуст.
Когда мы «проталкиваем» элемент, значение TOP увеличивается на единицу. Следующий элемент будет находиться на позиции TOP+1.
Когда мы используем метод pop, мы удаляем элемент, на который указывает TOP. После этого его значение уменьшается на единицу.
Перед добавлением нового элемента мы проверяем, не заполнен ли стек.
Перед удалением мы проверяем, не пуст ли стек.

Как создать стек в C++

Для использования шаблона стека в начале нашей программе мы должны подключить библиотеку — <stack>.

Чтобы создать стек нам понадобится оперировать схемой ниже:

C++

1 stack < типданных> < имя> ;

Давайте тщательнее ее разберем:

С новой строки мы должны написать слова stack.
<тип данных> — здесь нам понадобиться написать тот тип данных, который будет храниться в стеке.
<имя> — здесь вам все должно быть понятно.

Двусторонняя очередь

Двусторонняя очередь (Double-ended queue), или дек (Deque), расширяет поведение очереди. В дек можно добавлять или удалять элементы как с начала, так и с конца очереди. Такое поведение полезно во многих задачах, например, планирование выполнения потоков или реализация других структур данных. Позже мы рассмотрим вариант реализации стека с помощью двусторонней очереди.

Класс Deque

Класс Deque проще всего реализовать с помощью двусвязного списка. Он позволяет просматривать, удалять и добавлять элементы в начало и в конец списка. Основное отличие двусторонней очереди от обычной — методы Enqueue, Dequeue, и Peek разделены на пары для работы с обоими концами списка.

Метод EnqueueFirst

Поведение: Добавляет элемент в начало очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueFirst.
Сложность: O(1).

Метод EnqueueLast

Поведение: Добавляет элемент в конец очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueLast.
Сложность: O(1).

Метод DequeueFirst

Поведение: Удаляет элемент из начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException.
Сложность: O(1).

Метод DequeueLast

Поведение: Удаляет элемент с конца очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException.
Сложность: O(1).

Метод PeekFirst

Поведение: Возвращает элемент из начала очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException.
Сложность: O(1).

Метод PeekLast

Поведение: Возвращает элемент с конца очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException.
Сложность: O(1).

Метод Count

Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
Сложность: O(1).

Пример: реализация стека

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

У вас, возможно, возник вопрос, зачем реализовывать стек на основе очереди вместо связного списка. Причины две: производительность и повторное использование кода. У связного списка есть накладные расходы на создание узлов и нет гарантии локальности данных: элементы могут быть расположены в любом месте памяти, что вызывает большое количество промахов и падение производительности на уровне процессоров. Более производительная реализация двусторонней очереди требует массива для хранения элементов.

Тем не менее, реализация стека или очереди с помощью массива — непростая задача, но такая реализация двусторонней очереди и использование ее в качестве основы для других структур данных даст нам серьезный плюс к производительности и позволит повторно использовать код. Это снижает стоимость поддержки.

Позже мы посмотрим на вариант очереди с использованием массива, но сначала давайте взглянем на класс стека с использованием двусторонней очереди:

Заметьте, что вся обработка ошибок теперь лежит на классе Deque, и, кроме того, любая оптимизация очереди также отразится на стеке. Реализация обычной очереди на основе двусторонней настолько проста, что мы оставим ее читателю в качестве упражнения.

Хранение элементов в массиве

Как уже было упомянуто, у реализации очереди с использованием массива есть свои преимущества. Она выглядит простой, но на самом деле есть ряд нюансов, которые надо учесть.

Давайте посмотрим на проблемы, которые могут возникнуть, и на их решение. Кроме того, нам понадобится информация об увеличении внутреннего массива из прошлой статьи о динамических массивах.

При создании очереди у нее внутри создается массив нулевой длины. Красные буквы «h» и «t» означают указатели _head и _tail соответственно.

Добавляем элемент в начало

Добавляем элемент в конец

Добавляем еще один элемент в начало

Обратите внимание: индекс «головы» очереди перескочил в начало списка. Теперь первый элемент, который будет возвращен при вызове метода DequeueFirst — 0 (индекс 3).

И еще один в конец

Массив заполнен, поэтому при добавлении элемента произойдет следующее:

Алгорим роста определит размер нового массива.
Элементы скопируются в новый массив с «головы» до «хвоста».
Добавится новый элемент.

Добавляем значение в конец расширенного массива

Теперь посмотрим, что происходит при удалении элемента:

Удаляем элемент из начала

Удаляем элемент с конца

Ключевой момент: вне зависимости от вместимости или заполненности внутреннего массива, логически, содержимое очереди — элементы от «головы» до «хвоста» с учетом «закольцованности». Такое поведение также называется «кольцевым буфером».

Теперь давайте посмотрим на реализацию.

Класс Deque (с использованием массива)

Интерфейс очереди на основе массива такой же, как и в случае реализации через связный список. Мы не будем его повторять. Однако, поскольку список был заменен на массив, у нас добавились новые поля — сам массив, его размер и указатели на «хвост» и «голову» очереди.

Алгоритм роста

Когда свободное место во внутреннем массиве заканчивается, его необходимо увеличить, скопировать элементы и обновить указатели на «хвост» и «голову». Эта операция производится при необходимости во время добавления элемента. Параметр startingIndex используется, чтобы показать, сколько полей в начале необходимо оставить пустыми (в случае добавления в начало).

Обратите внимание на то, как извлекаются данные, когда приходится переходить в начало массива при проходе от «головы» к «хвосту».