Создание класса стека в Java. Стек — это фундаментальная структура данных… | Ларс Вехтер
https://www.pexels.com/de-de/foto/backen-backerei-behandeln-bunt-1407346/Стек — это фундаментальная структура данных в программировании. Он ведет себя как контейнер данных, в котором новые элементы добавляются в верхнюю часть стека, и у вас есть доступ только к последнему добавленному (самому верхнему элементу).
Определение Oracle (источник)
Класс Stack представляет стек объектов в порядке поступления (LIFO). Предусмотрены обычные операции push и pop, а также метод для просмотра верхнего элемента в стеке, метод для проверки того, пуст ли стек, и метод для поиска в стеке элемента и определения, насколько далеко он находится. это сверху.
Сегодня мы пытаемся воссоздать эту структуру данных на Java с нашим собственным универсальным классом и интерфейсом. Класс является универсальным для хранения различных типов данных. Он должен предоставлять следующие шесть методов:
- push (чтобы добавить новый элемент вверх)
- pop (чтобы удалить самый верхний элемент)
- peek (чтобы получить самый верхний элемент)
- isEmpty (чтобы проверить, пуст ли стек)
- размер (для получения размера стека)
- search (для поиска объектов)
Интерфейс: Stackable.
![](http://toto-school.ru/wp-content/plugins/a3-lazy-load/assets/images/lazy_placeholder.gif)
Начнем с интерфейса для нашего стека. Интерфейс указывает, какие методы должны быть реализованы внутри класса стека. Мы объявляем шесть методов, о которых я только что упоминал.
Конструкция
помечает интерфейс как универсальный. В этом случае T
может быть любым типом данных. Например, Целое число
или Строка
.
Класс: Stack.java
Далее мы создаем класс стека. Здесь нам понадобятся два приватных атрибута: предыдущий
и значение
.
предыдущий
— это ссылка на элемент, расположенный ниже текущего экземпляра в порядке стека (базовый элемент). Это приводит к рекурсивной реализации.
Атрибут value
содержит значение, которое хранит текущий экземпляр стека. Это может быть любой тип данных.
Кроме того, есть несколько конструкторов, которые нам понадобятся позже. Так как класс является универсальным, нам также понадобится конструкция
.
Метод: push
Этот метод помещает элемент на вершину стека. Поэтому мы устанавливаем текущий экземпляр стека на наш предыдущий и сохраняем новое значение.
предыдущие
ссылки теперь на наш старый экземпляр стека.
Метод: pop
Этот метод удаляет элемент с вершины стека и возвращает его значение.
Прежде всего, мы сохраняем текущее значение во временной переменной, потому что оно перезаписывается и нам нужно вернуть его позже.
После этого мы устанавливаем текущее значение
на значение из нашего предыдущего элемента стека
. Более того, мы ссылаемся на текущий предыдущий атрибут
на предыдущий
элемент базового элемента.
В конце возвращаем удаленное значение.
Метод: peek
Этот метод просматривает значение элемента наверху стека и возвращает его. Здесь нам просто нужно вернуть это.
. значение
Метод: isEmpty
Этот метод проверяет, пуст ли стек. Поскольку последний элемент стека не имеет ссылки на другой (лежащий в основе) элемент, нам просто нужно проверить, является ли предыдущий элемент
нулевым
.
Метод: size
Этот метод возвращает количество элементов в нашем стеке. Здесь мы рекурсивно считаем, пока не будет достигнут последний элемент.
Метод: search
Этот метод возвращает отсчитываемую от 1 позицию, в которой элемент находится в стеке. Поэтому мы перебираем все элементы нашего стека и увеличиваем счетчик до тех пор, пока не будет достигнут тот, который равен целевому элементу. И последнее, но не менее важное: мы возвращаем счетчик.
Если совпадений нет, возвращается -1
.
Попробуйте!
Давайте создадим новый экземпляр нашего класса стека и попробуем его.
Программа стекана Java — Sanfoundry
Это Java-программа для реализации стека. Стек — это область памяти, которая содержит все локальные переменные и параметры, используемые любой функцией, и запоминает порядок, в котором вызываются функции, чтобы возврат функции происходил правильно. Операция «push» используется для добавления элемента в стек, а операция «pop» используется для удаления элемента из стека. Также реализована операция peek, возвращающая значение верхнего элемента без его удаления. Связь между операциями push и pop такова, что стек представляет собой структуру данных «последним пришел — первым вышел» (LIFO). Реализованный стек имеет ограниченную емкость.
Вот исходный код Java-программы для реализации стека. Программа Java успешно скомпилирована и запущена в системе Windows. Вывод программы также показан ниже.
Проверка стека Введите размер целочисленного стека 5 Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 4 Пустой статус = правда Стек = пустой Вы хотите продолжить (Введите y или n) у Операции со стеком 1.нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 1 Введите целочисленный элемент для отправки 24 Стек = 24 Вы хотите продолжить (Введите y или n) у Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 1 Введите целочисленный элемент для отправки 6 Стек = 6 24 Вы хотите продолжить (Введите y или n) у Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 1 Введите целочисленный элемент для отправки 162 Стек = 162 6 24 Вы хотите продолжить (Введите y или n) у Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 1 Введите целочисленный элемент для отправки 19 Стек = 19 162 6 24 Вы хотите продолжить (Введите y или n) у Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 1 Введите целочисленный элемент для отправки 94 Стек = 94 19 162 6 24 Вы хотите продолжить (Введите y или n) у Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 5 Полный статус = правда Стек = 94 19 162 6 24 Вы хотите продолжить (Введите y или n) у Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 1 Введите целочисленный элемент для отправки 32 Ошибка: исключение переполнения Стек = 94 19 162 6 24 Вы хотите продолжить (Введите y или n) у Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 3 Элемент просмотра = 94 Стек = 94 19 162 6 24 Вы хотите продолжить (Введите y или n) у Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 2 Выдвинутый элемент = 94 Стек = 19 162 6 24 Вы хотите продолжить (Введите y или n) у Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 2 Выдвинутый элемент = 19 Стек = 162 6 24 Вы хотите продолжить (Введите y или n) у Операции со стеком 1.
нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 2 Выдвинутый элемент = 162 Стек = 6 24 Вы хотите продолжить (Введите y или n) у Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 6 Размер = 2 Стек = 6 24 Вы хотите продолжить (Введите y или n) у Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 2 Выдвинутый элемент = 6 Стек = 24 Вы хотите продолжить (Введите y или n) у Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 2 Выдвинутый элемент = 24 Стек = пустой Вы хотите продолжить (Введите y или n) у Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 2 Ошибка: исключение недополнения Стек = пустой Вы хотите продолжить (Введите y или n) у Операции со стеком 1. нажать 2. поп 3. заглянуть 4. проверить пусто 5. проверить полный 6. размер 4 Пустой статус = правда Стек = пустой Вы хотите продолжить (Введите y или n) п
Sanfoundry Global Education & Learning Series – 1000 Java-программ.
реклама
реклама
Если вы хотите просмотреть все примеры программирования на Java, перейдите в раздел Java Programs.
- Получите бесплатный сертификат качества в структуре данных I
- Принять участие в конкурсе сертификации структуры данных I
- Стать лидером в структуре данных I
- Пройти тесты структуры данных I
- Практические тесты по главам: Глава 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Пробные тесты по главам: глава 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
объявление
объявление
Подпишитесь на наши информационные бюллетени (тематические). Участвуйте в конкурсе сертификации Sanfoundry, чтобы получить бесплатный Сертификат отличия. Присоединяйтесь к нашим социальным сетям ниже и будьте в курсе последних конкурсов, видео, стажировок и вакансий!
Ютуб | Телеграмма | Линкедин | Инстаграм | Фейсбук | Твиттер | Пинтерест
Маниш Бходжасиа, ветеран технологий с более чем 20-летним опытом работы в Cisco и Wipro, является основателем и техническим директором компании Sanfoundry .![](/800/600/http/i.stack.imgur.com/4Ttvc.png)