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

Очередь и стек — Основы алгоритмов и структур данных

Мы привыкли записывать математические выражения, опираясь на приоритет операций и на скобки. Именно поэтому:

Далеко не все помнят из школьной математики приоритеты сложения и умножения, поэтому в социальных сетях распространены задачи «Сколько будет

Польский математик Ян Лукасевич около ста лет назад предложил необычный способ записи выражений, в котором не нужны ни приоритеты операций, ни скобки. Сейчас этот способ называют обратной польской записью.

Обратная запись непривычна и не получила широкого распространения, но ее можно встретить в таких языках программирования, как Forth и PostScript.

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

Обычная запись — , обратная —
Обычная запись — , обратная —

Операторы в обратной записи не всегда должны быть в конце. Например,

можно записать так:

Эта запись читается слева направо и воспринимается так:

Число
Число
Операция сложения
Число
Число
Операция сложения
Операция умножения

Преимущество обратных выражений в том, что они не вызывают разночтения.

Чтобы разобраться на примере, дальше мы пошагово вычислим это выражение:

Шаг 1. Берем из стопки два верхних числа —

. Выполняем над ними первую операцию — сложение:

Шаг 2. Идем дальше по выражению — нужно взять следующие два значения и второй оператор. Берем эти значения и применяем к ним вторую операцию сложения:

Шаг 3. Вспомним изначальное выражение:

Мы провели две операции сложения. Оставим только умножение и запишем в выражение результаты первых двух вычислений:

Шаг 4. Проводим последнюю операцию и получаем результат:

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

В программировании такие стопки называются стеком — от английского stack, то есть стопка или кипа.

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

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

Реализация стека через массив

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

Разные реализации могут быть непохожи друг на друга, но мы всегда ожидаем найти основные методы — конечно, у разных структур они разные. У стека должны быть реализованы три обязательных метода:

Метод push() помещает элемент на вершину стека, как карточку наверх стопки
Метод pop() убирает элемент с вершины и возвращает его
Метод isEmpty() проверяет, пуст ли стек

В JavaScript методы push() и pop() уже присутствуют в массиве, поэтому мы можем использовать их как есть:

class Stack  items = []; push(value)  this.items.push(value); > pop()  return this.items.pop(); > isEmpty()  return this.items.length == 0; > >

class Stack: items = [] def push(self, value): self.items.append(value) def pop(self): return self.items.pop() def is_empty(self): return len(self.items) == 0

php class Stack  public $items = []; public function push($value)  array_push($this->items, $value); > public function pop()  return array_pop($this->items); > public function isEmpty()  return count($this->items) == 0; > >

class Stack  List items = new ArrayList<>(); public T> void push(T item)  items.add(item); > public T> T pop()  var lastElementIndex = items.size() - 1; var lastElement = (T) items.get(lastElementIndex); items.remove(lastElementIndex); return lastElement; > public boolean isEmpty()  return items.isEmpty(); > >

Метод isEmpty() возвращает true , потому что массив пуст — содержит

Воспользуемся нашим стеком, чтобы вычислить значение выражения

let stack = new Stack(); const expression = '3 2 + 4 5 + *'; const lexems = expression.split(' '); for (lexem of lexems)  let a; let b; switch (lexem)  case '+': b = stack.pop(); a = stack.pop(); stack.push(a + b); break; case '-': b = stack.pop(); a = stack.pop(); stack.push(a - b); break; case '*': b = stack.pop(); a = stack.pop(); stack.push(a * b); break; case '/': b = stack.pop(); a = stack.pop(); stack.push(a / b); break; default: stack.push(parseFloat(lexem)); > > console.log(stack.pop()); // 45

stack = Stack() expression = '3 2 + 4 5 + *' lexems = expression.split(' ') for lexem in lexems: # В Python версии 3.10 и выше возможно использовать конструкцию match/case, но в данном случае рассмотрим реализацию через if/else if lexem == '+': a = stack.pop() b = stack.pop() stack.push(a + b) elif lexem == '-': a = stack.pop() b = stack.pop() stack.push(a - b) elif lexem == '*': a = stack.pop() b = stack.pop() stack.push(a * b) elif lexem == '': a = stack.pop() b = stack.pop() stack.push(a / b) else: stack.push(float(lexem)) print(stack.pop()) # 45

php $stack = new Stack(); $expression = '3 2 + 4 5 + *'; $lexems = explode(' ', $expression); foreach ($lexems as $lexem)  $a; $b; switch ($lexem)  case '+': $b = $stack->pop(); $a = $stack->pop(); $stack->push($a + $b); break; case '-': $b = $stack->pop(); $a = $stack->pop(); $stack->push($a - $b); break; case '*': $b = $stack->pop(); $a = $stack->pop(); $stack->push($a * $b); break; case '/': $b = $stack->pop(); $a = $stack->pop(); $stack->push($a / $b); break; default: $stack->push(floatval($lexem)); > > print_r($stack->pop()); // 45

var stack = new Stack(); var expression = "3 2 + 4 5 + *"; String[] lexems = expression.split(" "); for (String lexem : lexems)  float a; float b; switch (lexem)  case "+": b = stack.pop(); a = stack.pop(); stack.push(a + b); break; case "-": b = stack.pop(); a = stack.pop(); stack.push(a - b); break; case "*": b = stack.pop(); a = stack.pop(); stack.push(a * b); break; case "/": b = stack.pop(); a = stack.pop(); stack.push(a / b); break; default: stack.push(Float.parseFloat(lexem)); > > stack.pop(); // 45

Как видите, решение не очень сложное. Мы разбиваем строку с выражением на лексемы и обрабатываем каждую лексему в цикле.

Если лексема — это знак операции, то мы «снимаем» с вершины стека два числа, выполняем операцию и помещаем результат обратно на стек.

При выполнении операций важно обращать внимание на порядок чисел. Числа в стеке расположены в порядке, обратном тому, в котором мы их туда помещали. Поэтому сначала мы извлекаем второй операнд b , а потом первый a .

Порядок операндов не важен для таких операций, как сложение и умножение, потому что

. Но при делении это уже не так —

Учим Java

Блог посвящен изучению Java, решению разных задач и всему связанному с программированием.

вторник, 14 июня 2016 г.

Стек в Java SE

Проще всего представить стек это представить себе стопку тетрадей. Обычно учитель работает с ней так: смотрит на верхнюю тетрадь, проверяет ее, если добавляет элемент – тетрадь — в стопку, то наверх, а не в середину.

Таким образом, первая сданная тетрадь (самого шустрого ученика) будет проверена последней, а последняя сданная – первой.

Рассмотрим базовый класс Stack и методы работы с ним.
Чтобы создать стек целых чисел воспользуемся методом:
Stack stack = new Stack<>();
Добавить элемент в стек с помощью метода stack.push();:
stack.push(123); // добавит в стек число 123
stack.push(452); // добавит в стек число 452(будет верхним элементов стека)
Проверить есть ли что то в стеке можно методом:
stack.isEmpty(); // если в стеке ничего нет то вернет true, если стек заполнен вернет false
Чтобы посмотреть последний элемент стека, т.е. доступный элемент есть метод stack.peek();
она возвращает элемент, но не удаляет его из стека. Следующий код:
stack.push(123);
stack.push(452);
System.out.println(stack.peek()); // вернет число 452

Следующай команда stack.pop(); возвращает последний элемент стека и удалят его. Рассмотрим следующий код:

Что такое стек в Java?

Стек структура данных Last In First Out (LIFO). Он поддерживает две основные операции, называемые push и pop. Операция push добавляет элемент на вершину стека, а операция pop удаляет элемент из вершины стека. Java предоставляет класс Stack, который моделирует структуру данных Stack.

Аналогично Является ли очередь ADT? Stack & Queue — пример ADT. • Массив не является ADT.

Что такое LinkedList Java? Класс LinkedList коллекция, которая может содержать множество объектов одного типа, как ArrayList . Класс LinkedList имеет все те же методы, что и класс ArrayList, поскольку оба они реализуют интерфейс List.

Кроме того, что такое push() в Java?

В Java толчок метод, который добавляет элементы в стек, массив, LinkedList и т. д.. Элемент можно добавить в стек с помощью метода Java. утилиз. Куча. push(E el), и он будет добавлен наверх.

Что такое LIFO и FIFO в Java?

FIFO — это аббревиатура от «первым пришел — первым вышел». Это метод обработки структур данных, при котором первый элемент обрабатывается первым, а самый новый элемент обрабатывается последним. Пример из реальной жизни: LIFO — это аббревиатура от «последним пришел — первым ушел» — то же самое, что «кулак пришел — ушел последним» (FILO)..

Что такое очередь в Java? Java-очередь интерфейс, доступный в java. util и расширяет java. утилита Интерфейс коллекции. Как и Java List, Java Queue представляет собой набор упорядоченных элементов (или объектов), но он выполняет операции вставки и удаления по-разному.

Почему хвост ADT? Очередь структурирована, как описано выше, как упорядоченный набор элементов, которые добавляются с одного конца, называемого «задним», и удаляются с другого конца, называемого «передним». Очереди поддерживают свойство порядка FIFO. Операции с очередью приведены ниже.

Очередь — это ADT, оправдывающий ваш ответ? Очередь — это абстрактная структура данных., чем-то похожие на стеки. В отличие от стеков, очередь открыта с обоих концов. Один конец всегда используется для вставки данных (постановка в очередь), а другой — для удаления данных (удаление из очереди). Очередь следует методологии First-In-First-Out, т. е. сначала будет осуществляться доступ к элементу данных, сохраненному первым.

Как пройти по связанному списку?

Как пройти по связному списку?

Создайте временную переменную для обхода. Назначьте ему ссылку на головной узел, скажем, temp = head .
Повторяйте шаг ниже до temp != NULL .
temp->data содержит текущие данные узла. …
После этого перейдите к следующему узлу, используя temp = temp->next; .
Вернитесь ко 2-му шагу.

Что лучше ArrayList или LinkedList? ArrayList быстрее хранит и получает доступ к данным. LinkedList быстрее обрабатывает данные.

Что делает опрос LinkedList?

опрос(): этот метод извлекает и удаляет голову (первый элемент) из этого списка. Объявление: public E poll() Возвращаемое значение: Этот метод возвращает первый элемент этого списка или null, если этот список пуст.

Что делает Pop в Java? Что делает метод pop() в java? Метод pop() используется для удалить объект в верхней части этого стека и вернуть этот объект как значение этой функции.

Что такое dequeue и enqueue?

enqueue — это операция с очередью, когда вы добавляете элемент в конец очереди. dequeue — это операция с очередью, при которой вы удаляете элемент из начала очереди.

Что такое просмотр в Java?

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

Стек Java

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

Идея в том, что во многих приложениях есть множества объектов для обработки. Это простые операции. Нужно добавлять элементы к коллекции, удалять элементы из неё, проходить по всем объектам, проводя над ними какие-либо операции, проверять, не пуста ли она. Намерения вполне понятные. Ключевой момент: когда нужно удалить элемент коллекции, какой именно удалять? Есть две классические структуры данных: стек и очередь. Они различаются выбором элемента для удаления. В стеке мы удаляем последний добавленный элемент.

Термины, которые мы используем: push для вставки элемента и pop для удаления последнего добавленного элемента. Подход называется LIFO (last in first out)— последний зашел — первый вышел. Для очереди мы берем добавленный раньше всех элемент. Чтобы не путаться в операциях, добавление элемента назовем NQ, а удаление — DQ. Этот способ называется FIFO (first in first out) — первый пришел — первый вышел. Посмотрим, как всё это реализовать.

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

С другой стороны, реализация не может знать детально потребности клиента. Код должен лишь реализовать операции. В этом случае, многие клиенты могут использовать одну реализацию. Мы можем создавать модульные, многократно используемые библиотеки алгоритмов и структур данных, из которых строятся более сложные алгоритмы и структуры данных. Это позволяет при необходимости сосредоточиться на быстродействии. Это модульный стиль программирования, который возможен благодаря объектно-ориентированным языкам, как Java. Будем придерживаться этого стиля. Начнем разговор со стеков.

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

Так вот наше API, конструктор для создания пустого стека. Для вставки используется метод push, аргумент которого — строка, для удаления — метод pop, который выводит строку, добавленную последней. Метод isEmpty возвращает логическое значение. В некоторых приложениях, мы будет включать метод Size.

Как обычно, сначала напишем клиент, а затем разберем реализацию.

public static void main(String[] args) < StackOfStrings stack = new StackOfStrings(); while (!StdIn.isEmpty()) < String s = StdIn.readString(); if (s.equals("-")) StdOut.print(stack.pop()); else stack.push(s); >>

Наш клиент читает строки из стандартного ввода и использует команду pop, которую обозначим дефисом. Итак, этот клиент читает строки из стандартного ввода. Если строка равна знаку дефис, берем строку сверху стека и печатаем её. В противном случае, если строка не равна дефису, она добавляется наверх стека.

% more tobe.txt to be or not to - be - - that - - - is % java StackOfStrings < tobe.txt to be not that or be

Есть файл 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" указывает на начало списка. Элементы списка расположены в обратном порядке относительно их добавления в стек.

private class Node

Эти 4 строки реализуют стековую операцию push(). А вот полная реализация на базе связного списка всего кода для реализации стека строк в Java. В этом классе конструктор ничего не делает, поэтому его нет.

public class LinkedStackOfStrings < private Node first = null; private class Node < String item; Node next; >public boolean isEmpty() < return first == null; >public void push(String item) < Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; >public String pop()

Вот внутренний класс, который мы используем для элементов списка. Делаем его внутренним, чтобы ссылаться напрямую на него. И тогда единственной переменной стека является ссылка на первый узел в списке, и она на старте равна 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, которая представляет собой как размер стека, так и индекс следующей свободной позиции.

public class FixedCapacityStackOfStrings < private String[] s; private int N = 0; public FixedCapacityStackOfStrings(int capacity) < s = new String[capacity]; >public boolean isEmpty() < return N == 0; >public void push(String item) < s[N++] = item; >public String pop() < return s[--N]; >>

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

Клиент не знает размеров стека. Ему может потребоваться множество стеков одновременно. Они могут достичь максимальной вместимости в разное время. Нужно избавиться от такого требования, и мы это сделаем. Но, код становится почти тривиальным, если мы явно используем вместимость. Для проверки на пустоту мы проверяем, равен ли N нулю.

Для размещения элемента используем N как индекс массива, помещаем туда элемент и увеличиваем N. Вот это, N++, используется во многих языках программирования как сокращение для "используй индекс и увеличь его на 1". А для pop() мы уменьшаем индекс, затем используем его для возврата элемента массива. Таким образом, каждая из операций является однострочной. Это прекрасная реализация для некоторых клиентов. Это реализация стека с помощью массива, но она ломает API, требуя от клиента указания вместимости стека.

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

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

Для более эффективного использования памяти нужно устанавливать удаленные элементы в Null. Так, чтобы не оставалось ссылок на старые элементы, и сборщик мусора мог освободить память, так как на неё больше никто не ссылается. Это деталь, но для максимально эффективного использования памяти необходимо это учесть.

public String pop()

Автор этого материала - я - Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML - то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.

статьи IT, алгоритмы, стек, java, теория программирования