Стек с использованием связанного списка на Java
Javist
Свежие записи
Связанный список основан стек реализация
В компьютерной науке, стек временного абстрактных типов данных и их структуры, основанной на принципе Последний In First Out (LIFO). Стеки очень широко и широко используется в современных компьютерных системах, и, как правило, осуществляется через сочетание аппаратных и программных функций.
Следующий код показывает, как реализовать стек с помощью связанных списков:
// CONSTRUCTION: with no initializer
// void push( x ) –> Insert x
// void pop( ) –> Remove most recently inserted item
// Object top( ) –> Return most recently inserted item
// Object topAndPop( ) –> Return and remove most recent item
// boolean isEmpty( ) –> Return true if empty; else false
// void makeEmpty( ) –> Remove all items
// top, pop, or topAndPop on empty stack
* List-based implementation of the stack.
* @author Mark Allen Weiss
public class ListStack implements Stack <
* Construct the stack.
* Test if the stack is logically empty.
* @return true if empty, false otherwise.
public boolean isEmpty ( ) <
return topOfStack == null ;
* Make the stack logically empty.
* Insert a new item into the stack.
* @param x the item to insert.
public void push ( Object x ) <
topOfStack = new ListNode ( x, topOfStack ) ;
* Remove the most recently inserted item from the stack.
* @throws UnderflowException if the stack is empty.
throw new UnderflowException ( “ListStack pop” ) ;
* Get the most recently inserted item in the stack.
* Does not alter the stack.
* @return the most recently inserted item in the stack.
* @throws UnderflowException if the stack is empty.
public Object top ( ) <
throw new UnderflowException ( “ListStack top” ) ;
* Return and remove the most recently inserted item
* @return the most recently inserted item in the stack.
* @throws UnderflowException if the stack is empty.
public Object topAndPop ( ) <
throw new UnderflowException ( “ListStack topAndPop” ) ;
Object topItem = topOfStack.element;
private ListNode topOfStack;
* Exception class for access in empty containers
* such as stacks, queues, and priority queues.
* @author Mark Allen Weiss
public class UnderflowException extends RuntimeException <
* Construct this exception object.
* @param message the error message.
public UnderflowException ( String message ) <
// void push( x ) –> Insert x
// void pop( ) –> Remove most recently inserted item
// Object top( ) –> Return most recently inserted item
// Object topAndPop( ) –> Return and remove most recent item
// boolean isEmpty( ) –> Return true if empty; else false
// void makeEmpty( ) –> Remove all items
// top, pop, or topAndPop on empty stack
* Protocol for stacks.
* @author Mark Allen Weiss
public interface Stack <
* Insert a new item into the stack.
* @param x the item to insert.
void push ( Object x ) ;
* Remove the most recently inserted item from the stack.
* @exception UnderflowException if the stack is empty.
* Get the most recently inserted item in the stack.
* Does not alter the stack.
* @return the most recently inserted item in the stack.
* @exception UnderflowException if the stack is empty.
* Return and remove the most recently inserted item
* @return the most recently inserted item in the stack.
* @exception UnderflowException if the stack is empty.
* Test if the stack is logically empty.
* @return true if empty, false otherwise.
* Make the stack logically empty.
// Basic node stored in a linked list
// Note that this class is not accessible outside
// of package weiss.nonstandard
public ListNode ( Object theElement ) <
public ListNode ( Object theElement, ListNode n ) <
Класс Stack в Java
Класс стека в Java является частью платформы Collection, которая упрощает различные операции, такие как push, pop и т. д.
Что такое класс Stack в Java?
Класс Stack в Java — это структура данных, которая следует за LIFO (Last In First Out). Java Stack Class подпадает под базовую платформу Collection Hierarchy Framework, в которой вы можете выполнять базовые операции, такие как push, pop и т. д.
Мы знаем, что инфраструктура Java collection включает в себя интерфейсы и классы. Теперь давайте разберемся, как этот класс организован в иерархии инфраструктуры коллекций Java.
В приведенной выше иерархии синий прямоугольник относится к различным интерфейсам, а желтый прямоугольник определяет класс. Стек в Java расширяет векторный класс, который дополнительно реализует интерфейс List. Всякий раз, когда вы создаете стек, изначально он не содержит какого-либо элемента, т. е. Стек пуст.
Методы
В Java в основном существует 5 методов класса стека.
Давайте разберемся с каждым из этих методов на программном примере:
Empty stack: []
push(4)
Current Stack: [4]
push(8)
Current Stack: [4, 8]
push(9)
Current Stack: [4, 8, 9]
Element on stack top: 9
Element not found
Element is found at position 3
pop = 9
Remaining stack: [4, 8]
pop = 8
Remaining stack: [4]
pop = 4
Remaining stack: []
pop = empty stack
Объяснение: В приведенной выше Java-программе я сначала напечатал пустой стек и добавил несколько элементов, используя метод Push. Как только элементы присутствуют в стеке, я отобразил элементы сверху стека, используя метод Peek.
После этого я выполнил поиск с использованием метода Search и, наконец, удалил элементы в классе Java Stack с помощью метода Pop.
Размер стека
Вывод: Is the Java Stack empty? false
Size of Stack : 3
Перебор элементов стека на Java
- Итерация по стеку с использованием iterator()
- Перебор стека с использованием Java 8 forEach()
- Перебор стека с использованием listIterator() сверху вниз
Давайте начнем перебирать элементы с помощью iterator().
Точно так же вы можете выполнить итерацию другими методами.
Вывод: итерация стека с помощью forEach():
Итерация с использованием listIterator() сверху вниз:
Объяснение: В приведенном выше коде вы можете увидеть итерацию с помощью метода forEach(), а затем повернуть ее с помощью listIterator() сверху вниз в стеке.
Средняя оценка / 5. Количество голосов:
Спасибо, помогите другим – напишите комментарий, добавьте информации к статье.
Или поделись статьей
Видим, что вы не нашли ответ на свой вопрос.
Стек 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 и т. д. Каждый элемент удаляется из списка, а затем помещается в стек. После того, как все элементы находятся в стеке, вы вытаскиваете элементы один за другим и добавляете их обратно в пустой список.
