Как реализовать свой stack java

Как создать стэк в Java, не используя стандартный класс Stack?

Например, залезть в исходники, просмотреть реализацию и переписать под себя. Пример:

import java.util.ArrayList; public class CustomStack extends ArrayList  < public void push(T o) < add(o); >public T pop() < return remove(size() - 1); >> 

Отслеживать
ответ дан 12 мар 2012 в 13:33
1,550 13 13 серебряных знаков 18 18 бронзовых знаков

@Привет, очень интересный ответ (ссылка исходники). Поглядел и понял, что возможная эффективность реализации (коллекций основанных на массиве объектов (реально там много копирования в новый объект)) может обуславливаться только нетривиальной реализацией public static native void arraycopy() (определен в docjar.com/html/api/java/lang/System.java.html). Ссылки на исходники native у Вас случайно нет ? Очень интересно.

12 мар 2012 в 20:34

имхо так было бы лучше: public class CustomStack < private ArrayList= new ArrayList(); public void push(T o) < l.add(o); >public T pop() < return l.remove(l.size() - 1) ; >>

13 мар 2012 в 13:00
@jmu чем?) тем что ты ArrayList юзаешь не по назначению? кстати, пропустил l
13 мар 2012 в 13:09

А почему бы не сделать через LinkedList и не сравнить на разных режимах как со стандартной реализацией (через Vector), так и с предлагаемой на ArrayList (по сути Vector, но без syncronized методов) ? Если и в самом деле обычное университетское задание (комментарий @Angry Bird), то получилось бы неплохое исследование. И студенту плюс и обществу ХэшКода (если результаты опубликует) польза.

13 мар 2012 в 13:16

2Gorets во первых это не я. во вторых «не по назначению» это еще под сомнением, — если оставить методы листа тогда стек перестанет быть стеком. хотя конечно-же лучше было бы linked list использовать p.s. пропущеная буква при отсутсвии IDE это не ошибка 🙂

Стек с использованием связанного списка на Java

Ранее мы уже писали свой стек с помощью одномерного массива. Однако в этой статье мы напишем реализацию стека с помощью связанного списка и напишем для него несколько юнит-тестов.

Своя реализация стека на Java

С теорией можно ознакомиться в нашей предыдущей реализации стека.

«А зачем переизобретать колесо?» — спросите вы, ведь все уже написано до нас и нужно просто уметь использовать. Абсолютно согласен с такой позицией, но для более глубокого понимания работы стека и как он устроен, часто следует писать свою реализацию. В этой реализации стека мы воспользуемся связанным списком.

Лучшие практики написания стека

Для начала хотелось бы выделить основные правила и подходы, которым я буду следовать при написании стека на Java. Естественно, это касается не только реализации на Java, ведь подходы к реализации структуры данных должны быть универсальны. Однако некоторые моменты будут в контексте Java-реализации.

Операции push, pop за постоянное время

Временная сложность для операций вставки ( push ) и получения ( pop ) должны быть O(1) . Не имеет значения сколько элементов в стеке у нас будет , эти операции должны проводиться за постоянное время. Например, если мы вызываем операцию pop , то она должна вернуть последний добавленный элемент — O(1) .

Избегаем печати в консоль

Методы, которые отвечают за отображение элементов списка также должны быть тестируемые. А тестирование метода, который просто печатает что-то в консоль, не совсем правильно. Вместо этого в Java-реализации можно переопределить метод toString() и работать с ним.

Универсальный стек

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

Изобретение колеса

Когда мы пишем свою реализацию какой-то устоявшейся структуры данных, алгоритмов или шаблонов, желательно наследовать существующий подход (будь-то способ именования методов, обработки ошибок и т.д.). Для этого в Java хорошим примером является известный нам класс java.util.LinkedList .

Пишем стек с использованием связанного списка на Java

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

Как реализовать свой stack java

Мега-статья, потому что про очереди я так и не врубался на многочасовых лекциях и примерах, прочитав за 15 минут эту обычную статью все разложилось по полочкам, Большое спасибо!

Магсумова Диана Уровень 108 Expert
14 августа 2022
Прекрасная статья! )))) Благодарю))))
Евгений Т. Уровень 39
19 мая 2022
Ошибка в тексте «И со многими ИХ них «.
Жора Нет Уровень 39
30 апреля 2022

Из лекций ничего нового не почерпнул, кроме определения сложности алгоритмов. Все эти Стэки и Очереди приходилось самому находить и изучать при решении некоторых задач. Так вот в чем суть этих лекций? Я понимаю, если бы углублялись в изучении этих структур. А так получается я уже о них знаю больше, чем мне только что поверхностно рассказали.

Bulkin Уровень 40
10 ноября 2021
откуда столько времени найти такие книги читать?
Anonymous #2491313 Уровень 35
25 апреля 2021
Почему доставание элемента из очереди называется pull, а не pop?
Арман Уровень 37
14 апреля 2021
а на ее основе нередко строятся более сложныХ структуры данных.
5 апреля 2021

Я не понял откуда взялись эти классы и что они делают в примере про стек: game.setDeck(deck); game.setGraveyard(graveyard);

Иван Уровень 41
28 декабря 2020
Дайте несколько задач на очереди!
�� Виктор Уровень 20 Expert
6 ноября 2020

For the Alliance! Спасибо за статью, достаточно доступно, понятно и с хорошими примерами. Можно на эту тему ещё почитать следующие статьи: Стек-трейс Java. Stack Trace и с чем его едят. p.s. Если нужна, упомянутая в статье, книга Роберта Лафоре на русском языке в PDF формате с интерактивным оглавлением, то пишите, поделюсь ; )

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

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

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

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

Обратная запись непривычна и не получила широкого распространения, но ее можно встретить в таких языках программирования, как 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 .

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

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