Java Stack
The Java Stack class, java.util.Stack , is a classical stack data structure. You can push elements to the top of a Java Stack and pop them again, meaning read and remove the elements from the top of the stack.
The Java Stack class actually implements the Java List interface, but you rarely use a Stack as a List — except perhaps if you need to inspect all elements currently stored on the stack.
Please note, that the Java Stack class is a subclass of Vector, an older Java class which is synchronized. This synchronization adds a small overhead to calls to all methods of a Stack. Additionally, the Vector class uses several older (no longer recommended) parts of Java, like the Enumeration which is superseded by the Iterator interface. If you want to avoid these issues you can use a Java Deque as a stack instead.
Java Stack Tutorial Video
If you prefer video, I have a Java Stack tutorial video here: Java Stack Tutorial Video.
Java Stack Basics
A Stack is a data structure where you add elements to the «top» of the stack, and also remove elements from the top again. This is also referred to as the «Last In First Out (LIFO)» principle. In contrast, a Java Queue uses a «First In First Out (FIFO)» principle, where elements are added to the end of the queue, and removed from the beginning of the queue.
Create a Stack
To use a Java Stack you must first create an instance of the Stack class. Here is an example of creating a Java Stack instance:
Create a Stack with a Generic Type
You can set a generic type on a Stack specifying the type of objects the Stack instance can contain. You specify the stack type when you declare the Stack variable. Here is an example of creating a Java Stack with a generic type:
The Stack created above can only contain String instances.
Using a generic type on your Stack instances is recommended as it simplifies your code (no casts needed when accessing objects on the Stack), and decreases the risk that you push an object of the wrong type on the Stack.
Push Element on Stack
Once you have a Java Stack instance, you can push elements to the top of the Stack . The elements you push onto the Stack must be Java objects. Thus, you actually push objects to the Stack .
You push elements onto a Java Stack using its push() method. Here is an example of pushing an element (object) onto a Java Stack :
This Java example pushes a Java String with the text 1 onto the Stack . The String 1 is then stored at the top of the Stack .
Pop Element From Stack
Once an element has been pushed onto a Java Stack , you can pop that element from the Stack again. Once an element is popped off the Stack , the element is removed from the Stack . The top element of the Stack is then whatever element that was pushed onto the Stack just before the element just popped.
You pop an element off a Java Stack using the pop() method. Here is an example of popping an element off a Stack using the pop() method:
Once an element is popped off a Stack , the element is no longer present on the Stack .
Peek at Top Element of Stack
The Java Stack class has a method called peek() which enables you to see what the top element on the Stack is, without popping off the element. Here is an example of peeking at the top of a Java Stack :
After running this Java example the topElement variable will contain the String object 1 which was pushed onto the Stack just before peek() was called. The String object is still present on the Stack after calling peek() .
Search the Stack
You can search for an object on the stack to get it’s index, using the search() method. The object’s equals() method is called on every object on the Stack to determine if the searched-for object is present on the Stack . The index you get is the index from the top of the Stack , meaning the top element on the Stack has index 1.
Here is how you search a Stack for an object:
Stack Size
You can obtain the size of a Java Stack, meaning the number of elements currently stored on the Stack, via the Stack size() method. Here is an example of obtaining the size of a Java Stack via its size() method:
After running this code the size variable will contain the value 3, since the Stack in the example contains 3 elements at the time its size() method is called.
Iterate Elements of Stack
You can iterate the elements of a Java Stack by obtaining a Java Iterator from the Stack . You obtain an Iterator by calling the Stack iterator() method. Here is an example of obtaining an Iterator from a Java Stack and iterating it:
Process Stack Using Stream
It is also possible to process the elements on a Java Stack via the Java Stream API. You do so by first obtaining a Stream from the Stack via the stream() method.
Once you have obtained a Stream from the Stack , you can process the elements in the stream. Here is an example of obtaining a Stream from a Stack and processing the elements:
Notice, that this example uses a Java Lambda as parameter to the Stream.forEach() method. The lambda just prints out the element to System.out
Reverse List Using Stack
You can use a Java Stack to reverse a Java List. You do so by pushing all the elements from the List onto the Stack , starting with the element with index 0, then 1 etc. Each element is removed from the List , then pushed onto the Stack . Once all the elements are on the Stack , you pop the elements off one by one and add them back to the empty list. Here is an example of reversing a Java List using a Java Stack :
Use a Java Deque as a Stack
As mentioned at the top of this Java Stack tutorial, you can use a Java Deque as a stack too. The Java Deque tutorial also shows how you can do that — but I will show you a short example here too:
As you can see, it looks pretty similar to using a regular Java Stack.
Stack Use Cases
A Stack is really handy for some types of data processing, for instance if you are parsing an XML file using either SAX or StAX. For an example, see my Java SAX Example in my Java XML tutorial.
Стек Java
Сегодня будем говорить об алгоритмах и структурах данных для реализации фундаментальных типов данных — мультимножества, очереди и стека. Может быть, вы немного знакомы с ними, но сегодня мы рассмотрим их подробно. Начнем со стека.
Идея в том, что во многих приложениях есть множества объектов для обработки. Это простые операции. Нужно добавлять элементы к коллекции, удалять элементы из неё, проходить по всем объектам, проводя над ними какие-либо операции, проверять, не пуста ли она. Намерения вполне понятные. Ключевой момент: когда нужно удалить элемент коллекции, какой именно удалять? Есть две классические структуры данных: стек и очередь. Они различаются выбором элемента для удаления. В стеке мы удаляем последний добавленный элемент.
Термины, которые мы используем: push для вставки элемента и pop для удаления последнего добавленного элемента. Подход называется LIFO (last in first out)— последний зашел — первый вышел. Для очереди мы берем добавленный раньше всех элемент. Чтобы не путаться в операциях, добавление элемента назовем NQ, а удаление — DQ. Этот способ называется FIFO (first in first out) — первый пришел — первый вышел. Посмотрим, как всё это реализовать.
Подтемой сегодня будет модульное программирование. Идея в том, что бы полностью разделять интерфейс и реализацию. При наличии четко определенной структуры и типов данных, как стек или очередь, мы полностью скрываем детали реализации от клиента. Клиент может выбрать различные реализации но код должен использовать только базовые операции.
С другой стороны, реализация не может знать детально потребности клиента. Код должен лишь реализовать операции. В этом случае, многие клиенты могут использовать одну реализацию. Мы можем создавать модульные, многократно используемые библиотеки алгоритмов и структур данных, из которых строятся более сложные алгоритмы и структуры данных. Это позволяет при необходимости сосредоточиться на быстродействии. Это модульный стиль программирования, который возможен благодаря объектно-ориентированным языкам, как Java. Будем придерживаться этого стиля. Начнем разговор со стеков.
Давайте тщательно разберем реализацию стека прямо сейчас. Для разминки предположим, что у нас есть коллекция строк. Они могут быть короткими или длинными. Мы хотим иметь возможность сохранять коллекцию строк, удалять и выводить последние добавленные строки, проверять, пуста ли она.
Так вот наше API, конструктор для создания пустого стека. Для вставки используется метод push, аргумент которого — строка, для удаления — метод pop, который выводит строку, добавленную последней. Метод isEmpty возвращает логическое значение. В некоторых приложениях, мы будет включать метод Size.
Как обычно, сначала напишем клиент, а затем разберем реализацию.
Наш клиент читает строки из стандартного ввода и использует команду pop, которую обозначим дефисом. Итак, этот клиент читает строки из стандартного ввода. Если строка равна знаку дефис, берем строку сверху стека и печатаем её. В противном случае, если строка не равна дефису, она добавляется наверх стека.
Есть файл tobe.text, клиент будет вставлять строки «to be or not to» в стек. Затем, когда дело доходит до дефиса, он выдаст последний добавленный элемент, в данном случае это «to». Затем добавит «be» наверх стека и выдаст верхний элемент стека, то есть «be» и элемент, добавленный последним. Т.е. «Be» уйдет, «to» тоже, за ними идет «not» и так далее. Этот простой тестовый клиент можно использовать для проверки наших реализаций. Посмотрим код для реализации стека.
Первая реализация использует односвязный список. О связных списках можно подробнее почитать здесь. Нужно хранить односвязный список, который состоит из узлов, в свою очередь состоящих из строки и ссылки на следующий элемент списка.
В реализации стека, когда мы делаем добавление (push), то вставляем новый узел в начало списка. Когда извлекаем элемент, то удаляем первый элемент списка. Это последний добавленный элемент. Посмотрим, как выглядит этот код. Используем внутренний класс Java. То есть будем манипулировать объектами «узел», каждый из которых состоит из строки и ссылки на другой объект «узел». Таким образом операция pop для списка реализуется очень просто. Во-первых нужно вывести первый элемент в списке, поэтому сохраняем его. Возьмем first.item и сохраним в переменную item.
Чтобы избавиться от первого узла, просто сдвигаем указатель первого элемента списка на следующий за ним элемент. Теперь первый элемент готов быть удаленным сборщиком мусора. Остается только вывести элемент, который мы сохранили. Это была операция pop. Что насчет push операции?
Мы хотим добавить новый элемент в начало списка. Первое: сохраняем указатель на начало списка. Это oldfirst = first. Затем создаем новый узел, который поместим в начало списка. Это: first = new Node. Затем присваиваем ему значения. В поле item — строку, которую хотим вставить в начало списка В этом случае «not». И в поле next вставим указатель oldfirst, который теперь второй элемент списка. Так после этой операции, «first» указывает на начало списка. Элементы списка расположены в обратном порядке относительно их добавления в стек.
Эти 4 строки реализуют стековую операцию push(). А вот полная реализация на базе связного списка всего кода для реализации стека строк в Java. В этом классе конструктор ничего не делает, поэтому его нет.
Вот внутренний класс, который мы используем для элементов списка. Делаем его внутренним, чтобы ссылаться напрямую на него. И тогда единственной переменной стека является ссылка на первый узел в списке, и она на старте равна null. Тогда isEmpty просто проверка first на null. Push — это четыре строки кода, которые я уже показывал, pop — это 3 строки кода, которые были даны раньше. Это полный код односвязного списка, который является хорошей реализацией спускающегося списка для любого клиента.
Можно проанализировать алгоритм и предоставить информацию о его быстродействии клиентам. В этом случае видно, что каждая операция в худшем случае тратит постоянное время. Всего несколько инструкций для каждой из операций. Тут нет циклов. Это, очевидно, весьма неплохо.
Что насчет памяти?
Зависит от реализации и компьютера, здесь проанализирована типичная java реализация. Вы можете проверить её для различных сред выполнения, так что она показательна. Для каждого объекта в Java 16 байт идет на заголовок. Дополнительно 8 байт, потому что это внутренний класс. В классе Node есть 2 встроенные ссылки: одна на строку, другая на узел, каждая из них — 8 байт. Итак 40 байт для записи стека.
Если у нас есть стек размером N, он займет 40 N байт. Ещё немного занимает first элемент, это около N для целого стека. При большом N значение 40*N точно оценивает требуемую память. Оно не учитывает место для самих строк внутри клиента. Но с этим мы можем правильно оценить затраты ресурсов реализацией для различных клиентских программ.
Время постоянное, но есть и более быстрые реализации стека. Если стек используется во внутренних циклах неких алгоритмов, то важно поискать более быстрые реализации. Другой способ реализации стека — это использование массива для хранения элементов. Посмотрим на него.
Выбор между связанными структурами и массивами является фундаментальным и будет возникать снова и снова при разборе более продвинутых структур данных и алгоритмов. Рассмотрим массив применительно к стеку, чтобы быть готовыми к более продвинутым приложениям в дальнейшем.
При использовании массива, мы просто держим N элементов стека в массиве. И позиция массива c индексом N — это место расположения вершины стека, куда должен быть помещен следующий элемент. Таким образом, для push(), мы просто добавляем новый элемент в s[N]. А для pop() удаляем элемент s[N-1] и уменьшаем N.
Есть большой минус при использовании массива — его размер должен быть объявлен заранее, значит стек имеет ограниченную вместимость. С этим придется считаться, если количество элементов стека превышает размеры массива. Это фундаментальная проблема, с которой приходится иметь дело при любых структурах данных алгоритмов. В данном простом примере это окупится.
Итак, вот полная реализация стека, использующая массив для представления структуры стека. Здесь переменная экземпляра, представляющая собой массив строк. А также наша переменная N, которая представляет собой как размер стека, так и индекс следующей свободной позиции.
У этого класса есть конструктор. Он создает массив. Здесь мы немного сжульничали для упрощения, займемся этим позже. Обман состоит в требовании указывать размер стека. Это нормально для некоторых приложений, но слишком обременительно для многих других.
Клиент не знает размеров стека. Ему может потребоваться множество стеков одновременно. Они могут достичь максимальной вместимости в разное время. Нужно избавиться от такого требования, и мы это сделаем. Но, код становится почти тривиальным, если мы явно используем вместимость. Для проверки на пустоту мы проверяем, равен ли N нулю.
Для размещения элемента используем N как индекс массива, помещаем туда элемент и увеличиваем N. Вот это, N++, используется во многих языках программирования как сокращение для «используй индекс и увеличь его на 1». А для pop() мы уменьшаем индекс, затем используем его для возврата элемента массива. Таким образом, каждая из операций является однострочной. Это прекрасная реализация для некоторых клиентов. Это реализация стека с помощью массива, но она ломает API, требуя от клиента указания вместимости стека.
Итак, что с этим делать? Есть пара вещей, которые мы не рассмотрели. Мы не написали кода для выброса исключения, если клиент пытается извлечь элемент из пустого стека. Вероятно, следует это сделать. А что случится, если клиент поместит слишком много элементов? Поговорим об изменении размера, которое позволяет избежать переполнения.
Вопрос ещё в том, могут ли клиенты вставлять null элементы в структуру данных. В данном случае мы это позволяем. Но нужно позаботиться о проблеме лойтеринга, когда в массиве хранится ссылка на объект, который на самом деле не используется. Когда мы удаляем значение стека, то в массиве остается ссылка на него. Мы знаем, что больше не используем его, а Java нет.
Для более эффективного использования памяти нужно устанавливать удаленные элементы в Null. Так, чтобы не оставалось ссылок на старые элементы, и сборщик мусора мог освободить память, так как на неё больше никто не ссылается. Это деталь, но для максимально эффективного использования памяти необходимо это учесть.
Автор этого материала — я — Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML — то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.
статьи IT, алгоритмы, стек, java, теория программирования
Реализация stack в Java
Stack — это линейная структура данных, которая следует принципу LIFO (последний пришел, первый ушел). Это означает, что объекты могут быть вставлены или удалены только с одного конца, также называемого вершиной.
Stack поддерживает следующие операции:
- push вставляет элемент на вершину stack (т. е. над его текущим верхним элементом).
- pop удаляет объект из вершины stack и возвращает этот объект из функции. Размер stack будет уменьшен на единицу.
- isEmpty проверяет, пуст stack или нет.
- isFull проверяет, заполнен ли stack или нет.
- peek возвращает объект наверху stack, не удаляя его из stack и не изменяя стек каким-либо образом.
- size возвращает общее количество элементов, присутствующих в stack.
Реализация stack с использованием массива
Стек может быть легко реализован в виде массива. Ниже приведена реализация stack в 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 и т. д. Каждый элемент удаляется из списка, а затем помещается в стек. После того, как все элементы находятся в стеке, вы вытаскиваете элементы один за другим и добавляете их обратно в пустой список.