Что такое стек в java

Класс Stack

Современные программисты сейчас практически не используют Stack, который слишком прост и не очень гибок. Тем не менее, изучить его стоит, может именно он вам и пригодится.

Stack является подклассом класса Vector, который реализует простой механизм типа «последний вошёл — первый вышел» (LIFO). Можно представить процесс в виде детской пирамидки, когда вы по одному нанизываете диск на колышек. И снять диски вы сможете только по порядку, начиная с верхнего.

Взять элемент, который положили первым, вам никто не позволит. Даже не пытайтесь сделать так.

Напишем простейший пример применения стека.

 Stack stack = new Stack<>(); stack.push(0); stack.push(1); stack.push(2); System.out.println("Текущий стек: " + stack); System.out.println("Удаляем: " + stack.pop()); System.out.println("Удаляем: " + stack.pop()); System.out.println("Удаляем: " + stack.pop()); System.out.println("Текущий стек: " + stack); 

 I/System.out: Текущий стек: [0, 1, 2] I/System.out: Удаляем: 2 I/System.out: Удаляем: 1 I/System.out: Удаляем: 0 I/System.out: Текущий стек: [] 

Метод push() помещает объект в стек, а метод pop(), наоборот, вытаскивает объект из стека.

Пример с числами слишком скучный. Давайте позовём на помощь котов. Создадим простой класс Cat:

 package ru.alexanderklimov.expresscourse; public class Cat < private String mName; private int mAge; public Cat(String name, int age) < mName = name; mAge = age; >@Override public String toString() < return this.mName; >> 

Представьте себе, что имеется длинная узкая труба, запаянная с одного конца. Мы заталкиваем в трубу пушистого друга, поэтому метод называется «пуш» (push()). А чтобы вытащить кота, хватаем его за попу (метод pop()). Давайте запихаем в трубу трёх котов, а потом вытащим их.

 Cat barsik = new Cat("Барсик", 4); Cat murzik = new Cat("Мурзик", 6); Cat vaska = new Cat("Васька", 9); Stack catStack = new Stack<>(); catStack.push(barsik); catStack.push(murzik); catStack.push(vaska); Log.i(TAG, "Текущий стек: " + catStack); Log.i(TAG, "Брысь " + catStack.pop()); Log.i(TAG, "Кто последний? " + catStack.peek().toString()); Log.i(TAG, "Брысь " + catStack.pop()); Log.i(TAG, "Кто последний? " + catStack.peek().toString()); Log.i(TAG, "Брысь " + catStack.pop()); Log.i(TAG, "Никого? " + catStack.empty()); try < Log.i(TAG, "Кто последний? " + catStack.peek().toString()); >catch (EmptyStackException e) < Log.i(TAG, "Пустой стек. Некого прогонять"); >Log.i(TAG, "Текущий стек: " + catStack); 

У нас есть три кота — Барсик, Мурзик и Васька. В такой последовательности мы их запихнули в трубу и проверяем текущий стек.

 I/ExpressCourse: Текущий стек: [Барсик, Мурзик, Васька] 

Вызываем метод pop() первый раз. Как видите, мы не указываем позицию элемента, так стек работает только с последним элементом. Последним был Васька. Чтобы узнать, кто теперь последний в стеке, не удаляя его оттуда, нужно вызвать метод peek().

 I/ExpressCourse: Брысь Васька I/ExpressCourse: Кто последний? Мурзик 

Повторяем этот шаг ещё раз и вытаскиваем кота Мурзика. Затем и Барсика.

 I/ExpressCourse: Брысь Мурзик I/ExpressCourse: Кто последний? Барсик I/ExpressCourse: Брысь Барсик 

Чтобы убедиться, что в трубе никого не осталось, вызываем метод empty(), который возвращает булево значение.

 I/ExpressCourse: Никого? true 

Если при пустом стеке вызвать методы pop() или peek(), то программа закроется с ошибкой. Чтобы избежать подобной ситуации, нужно обработать исключение EmptyStackException. Тогда программа будет работать без сбоев.

 I/ExpressCourse: Пустой стек. Некого прогонять 

В конце выводим информацию о пустом стеке.

 I/ExpressCourse: Текущий стек: [] 

У класса также есть метод int search(Object o), который ищет заданный элемент в стеке, возвращая количество операций pop(), которые требуются для того чтобы перевести искомый элемент в вершину стека. Если заданный элемент в стеке отсутствует, этот метод возвращает -1.

Надеюсь, вы поняли что такое стек. Пожалуйста, не загоняйте котов в трубу.

Основы памяти в Java: Куча и Стек

Узнайте, как устроена память в Java: разбор работы Java-стека и кучи, особенностей управления памятью и роли сборщика мусора в данном процессе.

2 авг. 2023 · 7 минуты на чтение

Мы всё активнее применяем современные языки программирования, обеспечивающие нам возможность писать минимум кода для решения проблем. Возьмём за пример Java: он был разработан с целью максимального упрощения жизни программистов. Вам не приходится заботиться о памяти — ваши мысли целиком направлены на решение бизнес-задач. Однако это облегчение имеет свою цену.

В прошлой статье, мы обсудили общее устройство памяти в компьютере. А в этой статье мы сосредоточимся на том, как язык Java работает с памятью. Это включает в себя обзор стека и кучи в контексте Java, а также их отличия от общего представления. Мы также немного обсудим роль сборщика мусора в управлении памятью.

В данной статье не разбирается JMM. Углубиться в эту тему вы можете ознакомившись с дополнительными материалами в конце статьи.

Спонсор поста

Устройство памяти в программировании

Переходим к анализу ключевых концепций программирования, связанных с управлением памятью. Сначала обсудим стек и кучу — два фундаментальных механизма, лежащих в основе управления памятью. Затем рассмотрим их взаимодействие и особенности работы в процессе выполнения функций и методов.

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

Стек (Stack)

Стек — это область памяти, где функции хранят свои переменные и информацию для выполнения. Представьте стек как физическую стопку подносов в ресторане: вы можете добавить поднос сверху (push) или взять верхний поднос (pop). Аналогично, когда функция вызывается, ее локальные переменные и информация о вызове кладутся на стек сверху, и забираются сверху (уничтожаются), когда функция завершает работу.

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

Куча (Heap)

Куча — это область памяти, где данные могут быть размещены динамически во время выполнения программы. В отличие от стека, где данные удаляются автоматически после выхода из функции, данные в куче остаются, пока их явно не удалить.

Это делает кучу идеальным местом для хранения данных, которые должны пережить вызов функции, или для работы с большими объемами данных. Однако работа с кучей требует аккуратного управления: если вы не удаляете объекты, когда они больше не нужны, может произойти утечка памяти, что в конечном итоге может привести к исчерпанию доступной памяти.

Для удобства визуализируем стек и кучу. Серые объекты потеряли свою ссылку из стека, их необходимо удалить, чтобы освободить память для новых объектов.

Объект может содержать методы, и эти методы могут содержать локальные переменные. Эти локальные переменные также хранятся в стеке потоков, даже если объект, которому принадлежит метод, хранится в куче.

Стек

Когда функция вызывается, для нее выделяется блок памяти на вершине стека. Этот блок памяти, известный как «фрейм стека», содержит пространство для всех локальных переменных функции, а также информацию, такую как возвращаемый адрес: адрес в коде, к которому следует вернуться после завершения функции.

Когда функция вызывает другую функцию, для новой функции выделяется свой фрейм стека, и она становится текущей активной функцией. Когда функция завершает свою работу, ее фрейм стека удаляется, и управление возвращается обратно в вызывающую функцию.

Синхронизация в Java служит для контроля доступа нескольких потоков к общим ресурсам. Синхронизация может быть реализована с использованием ключевого слова synchronized или специальных классов, таких как ReentrantLock или Semaphore .

Сборщик мусора в Java работает в многопоточной среде и способен обрабатывать объекты из всех потоков. Однако следует быть внимательным с долгоживущими объектами и ресурсами, которые могут заблокировать сборщик мусора.

Заключение

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

В случае с Java, управление памятью становится еще более интересным благодаря сборщику мусора, который автоматически освобождает неиспользуемую память, и разделению памяти на Heap Space и Stack Space. Эти особенности делают язык Java удобным для работы, но также требуют осознанного использования памяти для предотвращения проблем с производительностью.

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

Дополнительные материалы

• Habr: Глубокое погружение в Java Memory Model
• Habr: Откуда растут ноги у Java Memory Model

Стек технологий, используемый в работе с Java Virtual Machine

Подборка технологий, инструментов, фреймворков и библиотек для создания утилит и интеграционных решений на Java/Scala.

Подборку подготовил Дмитрий Плужников, директор департамента прикладных разработок Arenadata

Мы — IT-вендор, разрабатывающий собственные продукты на базе Open Source проектов (Greenplum, Hadoop, Apache Kafka, Apache NiFi, ClickHouse и др.). В этом кратком обзоре речь пойдёт об инструментах и технологиях, которые используются в нашей компании для создания утилит и интеграционных решений на Java/Scala.

Технологический ландшафт

• Apache ZooKeeper — сервер для высоконадёжной распределённой координации приложений;
• Apache Spark — фреймворк с открытым исходным кодом для реализации распределённой обработки неструктурированных и слабоструктурированных данных, входящий в экосистему проектов Hadoop;
• Apache Kafka — распределённый программный брокер сообщений;
• Apache NiFi — ETL-инструмент с открытым исходным кодом;
• ClickHouse — колоночная аналитическая СУБД (Яндекс);
• Tarantool — система управления in-memory БД (база данных) с неблокирующим сервером (Mail.ru Group);
• Greenplum — массивно-параллельная СУБД для хранилищ данных на основе PostgreSQL.

Инструменты

• YourKit Java Profiler — для профилирования процессора и памяти Java;
• SonarQube — для анализа качества программного кода;
• Git — система управления версиями;
• SBT — система автоматической сборки для Java и Scala;
• Apache Maven и Gradle — для автоматизации сборки проектов;
• Jenkins — для обеспечения процесса непрерывной интеграции программного обеспечения;
• Portainer — для управления Docker-контейнерами;
• Docker — программа для автоматизации развёртывания и управления приложениями и контейнеризации приложений;
• Docker Compose — для запуска и управления Docker-контейнерами.

Библиотеки и фреймворки

• Spring Framework — универсальный фреймворк как основа для наших Java-приложений;
• Lombok — проект по добавлению дополнительной функциональности в Java c помощью изменения исходного кода перед компиляцией;
• Vert.x — фреймворк для реализаций реактивных сервисов;
• Apache Calcite — фреймворк для синтаксического анализа и построения SQL-выражений, а также для планирования запросов;
• JUnit — фреймворк для написания юнит-тестов;
• Akka, Akka HTTP, Akka Streams — набор инструментов для создания параллельных, распределённых и отказоустойчивых приложений для Java и Scala;
• Finagle — расширяемая RPC-система от компании Twitter для построения высоконагруженных систем;
• ScalikeJDBC — библиотека для доступа к БД с помощью JDBC;
• ScalaTest, TestContainers — для написания unit и интеграционных тестов;
• Spark (Core, Streaming, SQL) — для реализации коннекторов к различным источникам данных.

Для работы с фреймворком Spring также может быть полезен Spring Boot. Это проект, который упрощает создание приложений на основе Spring.

Стек Java: реализация, методы

Класс Java Stack, java.util.Stack, представляет собой классическую структуру данных стека. Вы можете поместить элементы на вершину стека и снова извлечь их, что означает чтение и удаление элементов с его вершины.

Класс фактически реализует интерфейс List, но вы редко используете его в качестве списка – за исключением, когда нужно проверить все элементы, хранящиеся в данный момент в стеке.

Обратите внимание, что класс Stack является подклассом Vector, более старого класса Java, который синхронизируется. Эта синхронизация добавляет небольшую нагрузку на вызовы ко всем методам стека. Кроме того, класс Vector использует несколько более старых (не рекомендуемых) частей Java, таких как Enumeration, который заменяется интерфейсом Iterator.Если вы хотите избежать этих проблем, вы можете использовать Deque вместо стека.

Основы

Стек – это структура данных, в которой вы добавляете элементы к «вершине» стека, а также снова удаляете элементы сверху. Это также называется принципом «первым пришел – первым вышел (LIFO)». В отличие от этого, Queue использует принцип «первым пришел – первым обслужен (FIFO)», когда элементы добавляются в конец очереди и удаляются из начала очереди.

Как создать стек в Java?

Для использования стека необходимо сначала создать экземпляр класса Stack:

Stack stack = new Stack();

Как создать с универсальным типом

Можно задать универсальный тип стека, указав тип объектов, которые может содержать экземпляр стека. Тип стека указывается при объявлении переменной стека. Вот пример:

Stack stack = new Stack();

Стек, созданный выше, может содержать только экземпляры String.

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

Толкающий элемент

Получив экземпляр Stack, вы можете поместить элементы в верхнюю часть стека. Они должны быть объектами. Таким образом, вы фактически толкаете объекты в стек.

Stack stack = new Stack(); stack.push("1");

Этот пример помещает строку с текстом 1 в стек. Строка 1 затем сохраняется в верхней части стека.

Вытолкнутый элемент

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

Stack stack = new Stack(); stack.push("1"); String topElement = stack.pop();

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

Как увидеть верхний элемент

Класс имеет метод peek (), который позволяет увидеть верхний элемент в стеке, не удаляя его:

Stack stack = new Stack(); stack.push("1"); String topElement = stack.peek();

После запуска этого примера переменная topElement будет содержать объект String 1, который был помещен в стек непосредственно перед вызовом peek(). Объект String все еще присутствует в стеке после вызова peek().

Поиск

Вы можете искать объект, чтобы получить его индекс, используйте метод search(). Метод вызывается для каждого объекта, чтобы определить, присутствует ли искомый объект в стеке. Индекс, который вы получаете, является индексом с вершины стека, то есть верхний элемент имеет индекс 1.

Stack stack = new Stack(); stack.push("1"); stack.push("2"); stack.push("3"); int index = stack.search("3"); //index = 3

Перебор элементов

Можно выполнить итерацию элементов, получив итератор из стека с помощью метода iterator().

Stack stack = new Stack(); stack.push(«123»); stack.push(«456»); stack.push(«789»); Iterator iterator = stack.iterator(); while(iterator.hasNext())

Использование потока

Также возможно обрабатывать элементы через API Stream. Вы делаете это, сначала получая его из стека с помощью метода stream().

Как только вы получили поток, можете обрабатывать элементы в потоке.

Stack stack = new Stack(); stack.push("A"); stack.push("B"); stack.push("C"); Stream stream = stack.stream(); stream.forEach((element) -> < System.out.println(element); // print element >);

Обратите внимание, что этот пример использует Lambda в качестве параметра для метода Stream.forEach(). Лямбда просто распечатывает элемент в System.out.

Обратный список

Вы можете использовать стек для реверсирования списка. Вы делать это, перемещая все элементы из списка в стек, начиная с элемента с индексом 0, затем 1 и т. д. Каждый элемент удаляется из списка, а затем помещается в стек. После того, как все элементы находятся в стеке, вы вытаскиваете элементы один за другим и добавляете их обратно в пустой список.

List list = new ArrayList(); list.add("A"); list.add("B"); list.add("C"); System.out.println(list); Stack stack = new Stack(); while(list.size() > 0) < stack.push(list.remove(0)); >while(stack.size() > 0) < list.add(stack.pop()); >System.out.println(list);