Пишем стек на java

Сегодня рассмотрю такую ​​простую, но нужную структуру, как Стек (Stack). Эта структура данных имеет несколько реализаций (простейшая — реализация на базе одномерного массива или односвязного списка). Остановлюсь на первом варианте.

Теория. Стек в java

Для начала ознакомимся с небольшой теоретической базой.

При использовании стека, есть доступ только к последнему добавленного элемента. Удалив этот элемент, пользователь получает доступ к предпоследнему элемента и тд. Таким образом эта структура данных реализует принцип LIFO (Last In First Out). Для удобства можно провести аналогию со стопкой тарелок или магазином пистолета (последний заряженный патрон, будет подан в патронник первым). Многие микропроцессоров имеют стековую архитектуру. Когда происходит вызов метода, адрес возврата и аргументы заносятся в стек, а при выходе изымаются из него.

Пример стека

Здесь 5 — элемент на вершине стека (назовем последний элемент — top) — рисунок 1.

 Рисунок 1 — Пример стека, который будет реализован на java

Таким образом, чтобы получить из стека элемент «3», для начала нам нужно удалить «5» и «4». На этом небольшая теоретическая часть заканчивается. Добавлю, что элемент TOP, иногда еще называют «головой» (head).

Реализация стека в java

Итак, я предлагаю реализовать следующие методы для нашего стека:

1) addElement — метод, который обеспечит добавление элемента (в top позиции)

2) deleteElement — метод, которых обеспечит удаление элемента (с top позиции)

3) readTop — метод, который вернет значение элемента, который находится в позиции top

4) isEmpty — метод, который будет проверять стек на пустоту

5) isFull — метод, который будет проверять, не переполнен наш массив, в котором мы сохраняем стек

Для начала создадим в нашем проекте, класс Stack, объявим нужные для работы поля, а далее инициализируем их в конструкторе.

Конструктор имеет параметр m, он позволит пользователю ввести максимальный размер стека с клавиатуры. Также, необходимо понимать разницу между синтаксисом top++ и ++top. В первом случае, сначала выполняется определенное действие, а затем инкрементируется (увеличивается) счетчик. Во втором, сначала инкрементируется счетчик, а затем выполняется действие.

Реализуем упомянутые методы взаимодействия со стеком.

1) addElement

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

2) deleteElement

Для удаления существующего top элемента достаточно уменьшить индекс массива. Таким образом нашей вершиной стека станет предпоследней элемент, а последний элемент будет удален с помощью Garbage Collector (встроенный в Java машину механизм для удаления определенных элементов).

Графическая иллюстрация процесса удаления представлена на рисунке 2

Рисунок 2 — Процесс удаления со стека

3) readTop

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

4) IsEmpty

Возвращает true (если массив данных пустой, индекс элемента top = 1, именно для этого мы задавали в конструкторе такое начальное значение для данной переменной).

5) isFull

Метод возвращает значение true (в той ситуации, когда наш массив данных полностью заполнен и нет возможности добавить еще один элемент). Кстати, может возникнуть вопрос, почему именно mSize-1? Если мы задаем максимальное количество элементов массива 10, то максимальный индекс будет 9, так как индексы идут от 0 до 9.

В методе main реализуем введения четырех элементов, удаление одного и дальнейший вывод стека на экран.

Обратите внимание, что стек выдает элементы в порядке, обратном к вводу. То есть если мы вводили в стек 79, 59, 35, 24, то он вернет нам 24, 35, 59, 79. Именно поэтому эту структуру данных удобно применять для решения задачи реверса букв в слове или формирования префиксного записи алгебраических выражений (Reverse Polish Notation ).

Листинг программы:

 

Вот и все, стек на java готов. Следите за обновлениями на Javadevblog.com

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

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