Что такое стек и зачем он нужен на примере msp430

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

По традиции рассказ начну с определения. Термин пришел из английского языка: слово 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 — индекс элемента, находящегося в вершине стека.

Массив

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

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

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

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

Как создать стек в 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 используется, чтобы показать, сколько полей в начале необходимо оставить пустыми (в случае добавления в начало).

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

Метод EnqueueFirst

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

Метод EnqueueLast

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

Метод DequeueFirst

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

Метод DequeueLast

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

Метод PeekFirst

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

Метод PeekLast

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

Метод Count

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

Где применяются стеки

  • Поворот слова задом-наперед. Поместите все буквы в стек и верните их — благодаря LIFO слово «отзеркалится».
  • В компиляторах. Компиляторы используют стеки для вычисления выражений вроде 2 + 4 / 5 * (7 — 9). Происходит это благодаря его конвертации в префиксную и постфиксную форму. 
  • В браузерах. Кнопка «Назад» хранит в стеке все URL-адреса, которые вы посещали. Каждый раз, когда вы посещаете новую страницу, ее URL-адрес оказывается на «вершине» стека. После нажатия на кнопку «Назад» текущий URL-адрес удаляется из стека, и браузер получает доступ к предыдущему.

Теги

Adblock
detector