Реализация stack в Java
Stack — это линейная структура данных, которая следует принципу LIFO (последний пришел, первый ушел). Это означает, что объекты могут быть вставлены или удалены только с одного конца, также называемого вершиной.
Stack поддерживает следующие операции:
- push вставляет элемент на вершину stack (т. е. над его текущим верхним элементом).
- pop удаляет объект из вершины stack и возвращает этот объект из функции. Размер stack будет уменьшен на единицу.
- isEmpty проверяет, пуст stack или нет.
- isFull проверяет, заполнен ли stack или нет.
- peek возвращает объект наверху stack, не удаляя его из stack и не изменяя стек каким-либо образом.
- size возвращает общее количество элементов, присутствующих в stack.
Реализация stack с использованием массива
Стек может быть легко реализован в виде массива. Ниже приведена реализация stack в Java с использованием массива:
Структуры данных в Java — стек и очередь
Привет! Сегодня поговорим о таких важных для любого программиста вещах как структуры данных . Википедия гласит: Структура данных (англ. data structure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Определение немного запутанное, но суть его ясна. Структура данных — это такое своеобразное хранилище, где мы держим данные для дальнейшего использования. В программировании существует огромное количество разнообразных структур данных. Очень часто при решении конкретной задачи самое главное — выбор наиболее подходящей для этого структуры данных. И со многими из них ты уже знаком! Например, с массивами . А также с Map (которую обычно переводят как “словарь”, “карта”, или “ассоциативный массив”). Очень важно понимать: структуры данных не привязаны к какому-то конкретному языку . Это просто абстрактные “чертежи”, по которым каждый язык программирования создает свои собственные классы — реализации этой структуры. Например, одна из самых известных структур данных — связный список . Ты можешь зайти в википедию, почитать о том как он устроен, какие у него есть достоинства и недостатки. Возможно, тебе покажется знакомым его определение 🙂 “Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка” Так ведь это же наш LinkedList ! Точно, так оно и есть 🙂 Структура данных “связный список” реализована в языке Java в классе LinkedList . Но и в других языках связный список тоже реализован! В Python он называется “ llist ”, в Scala называется так же, как в Java — “ LinkedList ”. Связный список — одна из базовых распространенных структур данных, поэтому ее реализацию ты найдешь в любом современном языке программирования. То же самое с ассоциативным массивом. Вот его определение из Википедии: Ассоциативный массив — абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу. Ничего не напоминает? 🙂 Точно, для нас, джавистов, ассоциативный массив — это интерфейс Map . Но эта структура данных реализована и в других языках! Например, программисты на C# знают его под названием “Dictionary”. А в языке Ruby он реализован в классе под названием “Hash”. В общем, ты примерно понял в чем смысл: структура данных — это такая общая для всего программирования штука, которая реализуется по-своему в каждом конкретном языке. Сегодня мы изучим две такие структуры и посмотрим, как они реализованы в Java — стек и очередь.
Стек Java: реализация, методы
Класс Java Stack, java.util.Stack, представляет собой классическую структуру данных стека. Вы можете поместить элементы на вершину стека и снова извлечь их, что означает чтение и удаление элементов с его вершины.
Класс фактически реализует интерфейс List, но вы редко используете его в качестве списка – за исключением, когда нужно проверить все элементы, хранящиеся в данный момент в стеке.
Обратите внимание, что класс Stack является подклассом Vector, более старого класса Java, который синхронизируется. Эта синхронизация добавляет небольшую нагрузку на вызовы ко всем методам стека. Кроме того, класс Vector использует несколько более старых (не рекомендуемых) частей Java, таких как Enumeration, который заменяется интерфейсом Iterator.Если вы хотите избежать этих проблем, вы можете использовать Deque вместо стека.
Основы
Стек – это структура данных, в которой вы добавляете элементы к «вершине» стека, а также снова удаляете элементы сверху. Это также называется принципом «первым пришел – первым вышел (LIFO)». В отличие от этого, Queue использует принцип «первым пришел – первым обслужен (FIFO)», когда элементы добавляются в конец очереди и удаляются из начала очереди.
Как создать стек в Java?
Для использования стека необходимо сначала создать экземпляр класса Stack:
Как создать с универсальным типом
Можно задать универсальный тип стека, указав тип объектов, которые может содержать экземпляр стека. Тип стека указывается при объявлении переменной стека. Вот пример:
Стек, созданный выше, может содержать только экземпляры String.
Рекомендуется использовать универсальный тип в ваших экземплярах стека, поскольку он упрощает код (не требуется преобразование при доступе к объектам в стеке) и снижает риск того, что вы поместите объект неправильного типа в стек.
Толкающий элемент
Получив экземпляр Stack, вы можете поместить элементы в верхнюю часть стека. Они должны быть объектами. Таким образом, вы фактически толкаете объекты в стек.
Этот пример помещает строку с текстом 1 в стек. Строка 1 затем сохраняется в верхней части стека.
Вытолкнутый элемент
Как только элемент помещен в стек, вы можете снова извлечь его. Как только он извлечен, удаляется из стека. В этом случае верхний элемент стека – это любой элемент, который был помещен в стек непосредственно перед тем, как элемент вытолкнулся.
Как только элемент извлечен из стека, элемент больше не присутствует в стеке.
Как увидеть верхний элемент
Класс имеет метод peek (), который позволяет увидеть верхний элемент в стеке, не удаляя его:
После запуска этого примера переменная topElement будет содержать объект String 1, который был помещен в стек непосредственно перед вызовом peek(). Объект String все еще присутствует в стеке после вызова peek().
Поиск
Вы можете искать объект, чтобы получить его индекс, используйте метод search(). Метод вызывается для каждого объекта, чтобы определить, присутствует ли искомый объект в стеке. Индекс, который вы получаете, является индексом с вершины стека, то есть верхний элемент имеет индекс 1.
Перебор элементов
Можно выполнить итерацию элементов, получив итератор из стека с помощью метода iterator().
Использование потока
Также возможно обрабатывать элементы через API Stream. Вы делаете это, сначала получая его из стека с помощью метода stream().
Как только вы получили поток, можете обрабатывать элементы в потоке.
Обратите внимание, что этот пример использует Lambda в качестве параметра для метода Stream.forEach(). Лямбда просто распечатывает элемент в System.out.
Обратный список
Вы можете использовать стек для реверсирования списка. Вы делать это, перемещая все элементы из списка в стек, начиная с элемента с индексом 0, затем 1 и т. д. Каждый элемент удаляется из списка, а затем помещается в стек. После того, как все элементы находятся в стеке, вы вытаскиваете элементы один за другим и добавляете их обратно в пустой список.
Пишем стек на 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 , объявим нужные для работы поля, а далее инициализируем их в конструкторе.