Стек #3

Здравствуйте, уважаемые читатели.

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

Для реализации структур данных я буду использовать язык программирования С++. Мое решение было обусловлено, тем, что  этот язык является очень популярным и имеет широкие возможности по работе с памятью.

Теперь приступим к теме статьи.


 

Что такое стек и с чем его едят?

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

Стек можно представить себе как стакан с монетками, лежащими столбиком.

Т.е. мы кладем монетку на дно, потом еще одну сверху и так далее. И, чтоб достать монетку, которую мы опустили в стакан первой, нужно вытащить все предыдущие. В этом и заключается принцип стека и звучит он так: «Последним пришёл — первым вышел». Великие мира сего даже придумали специальную аббревиатуру  LIFO (англ. last in — first out).

Теперь монетки переведем в информационный эквивалент.

Имеем мы значит односвязный список. Добавили туда первый элемент (хвост списка), далее добавляем все новые элементы только слева от хвоста, т.е. каждый раз создаем новую голову. А удаляем наоборот —  с головы до хвоста. Таким образом, элемент, который последний попал в стек, выйдет из него первым (помним про LIFO). Вот небольшая картинка для наглядности:

 

С++ программирование стек

Все, как видите, очень просто. Для работы со стеком принято реализовывать три основные функции:

1. Push — втолкнуть элемент.

2. Pop — вытолкнуть элемент.

3. Peek — считать вершину (голову) стека.

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

Далее прилагаю код реализации (исходник можно будет скачать в конце статьи):

Стек реализован на основе класса, но все это можно было сделать, используя только структуру и обычные функцию, но для С++ правильнее делать с классом.

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

Также я добавил метод для чтения количества элементов стека. Поле size не просто так сделал закрытым. Это обусловлено, тем, что size являясь публичным, мог быть вызван и мейна, что могла повлечь за собой неправильную работу класса (например, ему бы присвоили отрицательное значение). Из-за этого и был создан специальный метод для чтения размера стека.

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

Вот пример использования класса стека:

Если в коде вам что-то непонятно, то задавайте вопросы в комментариях — я на них всенепременно отвечу.

Исходник стека скачать.

На этом закончу свое небольшое повествование.

Все спасибо за внимание. До встречи в следующей статье.

 

Поддержать сайт и автора: Z208212694629
R429062753687
Яндекс деньги - https://money.yandex.ru/to/410013974912682

Подпишись:
На мой канал youtube
На рассылку свежих статей
На группу ВК
На группу в ОК

Понравилась статья? Поделись с друзьями)

Опубликовать в Google Buzz
Опубликовать в Google Plus
Опубликовать в LiveJournal
Опубликовать в Мой Мир
Опубликовать в Одноклассники

Стек #3: Один комментарий

  1. Уведомление: Очередь #4 | Всего наилучшего — 73!

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