Как реализовать свой stack java
Перейти к содержимому

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

  • автор:

Реализация stack в Java

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

Stack поддерживает следующие операции:

  • push вставляет элемент на вершину stack (т. е. над его текущим верхним элементом).
  • pop удаляет объект из вершины stack и возвращает этот объект из функции. Размер stack будет уменьшен на единицу.
  • isEmpty проверяет, пуст stack или нет.
  • isFull проверяет, заполнен ли stack или нет.
  • peek возвращает объект наверху stack, не удаляя его из stack и не изменяя стек каким-либо образом.
  • size возвращает общее количество элементов, присутствующих в stack.

Реализация stack с использованием массива

Стек может быть легко реализован в виде массива. Ниже приведена реализация stack в Java с использованием массива:

30.4. Java – Класс Stack

Класс Stack – это подкласс Vector, который реализует стандартный стек last-in, first-out.

В Java Stack только определяет стандартный конструктор, который создает пустой стек. Stack включает все методы, определённые Vector, и самостоятельно добавляет несколько своих собственных.

Stack() 

Методы

Кроме методов, унаследованных от его родительского класса Vector, Stack в Java определяет следующие методы.

Метод и описание
1 boolean empty()
Проверяет, является ли стек пустым. Возвращает true, если стек пустой. Возвращает false, если стек содержит элементы.
2 Object peek()
Возвращает элемент, находящийся в верхней части стэка, но не удаляет его.
3 Object pop()
Возвращает элемент, находящийся в верхней части стэка, удаляя его в процессе.
4 Object push(Object element)
Вталкивает элемент в стек. Элемент также возвращается.
5 int search(Object element)
Ищет элемент в стеке. Если найден, возвращается его смещение от вершины стека. В противном случае возвращается 1.

Пример

Следующая программа показывает несколько методов, поддерживаемых коллекцией Stack в Java:

import java.util.*; public class StackDemo < static void showpush(Stack st, int a) < st.push(new Integer(a)); System.out.println("Втолкнуть(" + a + ")"); System.out.println("Стек: " + st); >static void showpop(Stack st) < System.out.print("Выстрелить ->"); Integer a = (Integer) st.pop(); System.out.println(a); System.out.println("Стек: " + st); > public static void main(String args[]) < Stack st = new Stack(); System.out.println("Стек: " + st); showpush(st, 42); showpush(st, 66); showpush(st, 99); showpop(st); showpop(st); showpop(st); try < showpop(st); >catch (EmptyStackException e) < System.out.println("Пустой стек"); >> > 
Стек: [ ] Втолкнуть (42) Стек: [42] Втолкнуть (66) Стек: [42, 66] Втолкнуть (99) Стек: [42, 66, 99] Выстрелить -> 99 Стек: [42, 66] Выстрелить -> 66 Стек: [42] Выстрелить -> 42 Стек: [ ] Выстрелить -> Пустой стек 

Оглавление

  • 1. Java – Самоучитель для начинающих
  • 2. Java – Обзор языка
  • 3. Java – Установка и настройка
  • 4. Java – Синтаксис
  • 5. Java – Классы и объекты
  • 6. Java – Конструкторы
  • 7. Java – Типы данных и литералы
  • 8. Java – Типы переменных
  • 9. Java – Модификаторы
  • 10. Java – Операторы
  • 11. Java – Циклы и операторы цикла
  • 11.1. Java – Цикл while
  • 11.2. Java – Цикл for
  • 11.3. Java – Улучшенный цикл for
  • 11.4. Java – Цикл do..while
  • 11.5. Java – Оператор break
  • 11.6. Java – Оператор continue
  • 12. Java – Операторы принятия решений
  • 12.1. Java – Оператор if
  • 12.2. Java – Оператор if..else
  • 12.3. Java – Вложенный оператор if
  • 12.4. Java – Оператор switch..case
  • 12.5. Java – Условный оператор (? 🙂
  • 13. Java – Числа
  • 13.1. Java – Методы byteValue(), shortValue(), intValue(), longValue(), floatValue(), doubleValue()
  • 13.2. Java – Метод compareTo()
  • 13.3. Java – Метод equals()
  • 13.4. Java – Метод valueOf()
  • 13.5. Java – Метод toString()
  • 13.6. Java – Метод parseInt()
  • 13.7. Java – Метод Math.abs()
  • 13.8. Java – Метод Math.ceil()
  • 13.9. Java – Метод Math.floor()
  • 13.10. Java – Метод Math.rint()
  • 13.11. Java – Метод Math.round()
  • 13.12. Java – Метод Math.min()
  • 13.13. Java – Метод Math.max()
  • 13.14. Java – Метод Math.exp()
  • 13.15. Java – Метод Math.log()
  • 13.16. Java – Метод Math.pow()
  • 13.17. Java – Метод Math.sqrt()
  • 13.18. Java – Метод Math.sin()
  • 13.19. Java – Метод Math.cos()
  • 13.20. Java – Метод Math.tan()
  • 13.21. Java – Метод Math.asin()
  • 13.22. Java – Метод Math.acos()
  • 13.23. Java – Метод Math.atan()
  • 13.24. Java – Метод Math.atan2()
  • 13.25. Java – Метод Math.toDegrees()
  • 13.26. Java – Метод Math.toRadians()
  • 13.27. Java – Метод Math.random()
  • 14. Java – Символы
  • 14.1. Java – Метод Character.isLetter()
  • 14.2. Java – Метод Character.isDigit()
  • 14.3. Java – Метод Character.isWhitespace()
  • 14.4. Java – Метод Character.isUpperCase()
  • 14.5. Java – Метод Character.isLowerCase()
  • 14.6. Java – Метод Character.toUpperCase()
  • 14.7. Java – Метод Character.toLowerCase()
  • 14.8. Java – Метод Character.toString()
  • 15. Java – Строки
  • 15.1. Java – Метод charAt()
  • 15.2. Java – Метод compareTo()
  • 15.3. Java – Метод compareToIgnoreCase()
  • 15.4. Java – Метод concat()
  • 15.5. Java – Метод contentEquals()
  • 15.6. Java – Метод copyValueOf()
  • 15.7. Java – Метод endsWith()
  • 15.8. Java – Метод equals()
  • 15.9. Java – Метод equalsIgnoreCase()
  • 15.10. Java – Метод getBytes()
  • 15.11. Java – Метод getChars()
  • 15.12. Java – Метод hashCode()
  • 15.13. Java – Метод indexOf()
  • 15.14. Java – Метод intern()
  • 15.15. Java – Метод lastIndexOf()
  • 15.16. Java – Метод length()
  • 15.17. Java – Метод matches()
  • 15.18. Java – Метод regionMatches()
  • 15.19. Java – Метод replace()
  • 15.20. Java – Метод replaceAll()
  • 15.21. Java – Метод replaceFirst()
  • 15.22. Java – Метод split()
  • 15.23. Java – Метод startsWith()
  • 15.24. Java – Метод subSequence()
  • 15.25. Java – Метод substring()
  • 15.26. Java – Метод toCharArray()
  • 15.27. Java – Метод toLowerCase()
  • 15.28. Java – Метод toString()
  • 15.29. Java – Метод toUpperCase()
  • 15.30. Java – Метод trim()
  • 15.31. Java – Метод valueOf()
  • 15.32. Java – Классы StringBuilder и StringBuffer
  • 15.32.1. Java – Метод append()
  • 15.32.2. Java – Метод reverse()
  • 15.32.3. Java – Метод delete()
  • 15.32.4. Java – Метод insert()
  • 15.32.5. Java – Метод replace()
  • 16. Java – Массивы
  • 17. Java – Дата и время
  • 18. Java – Регулярные выражения
  • 19. Java – Методы
  • 20. Java – Потоки ввода/вывода, файлы и каталоги
  • 20.1. Java – Класс ByteArrayInputStream
  • 20.2. Java – Класс DataInputStream
  • 20.3. Java – Класс ByteArrayOutputStream
  • 20.4. Java – Класс DataOutputStream
  • 20.5. Java – Класс File
  • 20.6. Java – Класс FileReader
  • 20.7. Java – Класс FileWriter
  • 21. Java – Исключения
  • 21.1. Java – Встроенные исключения
  • 22. Java – Вложенные и внутренние классы
  • 23. Java – Наследование
  • 24. Java – Переопределение
  • 25. Java – Полиморфизм
  • 26. Java – Абстракция
  • 27. Java – Инкапсуляция
  • 28. Java – Интерфейсы
  • 29. Java – Пакеты
  • 30. Java – Структуры данных
  • 30.1. Java – Интерфейс Enumeration
  • 30.2. Java – Класс BitSet
  • 30.3. Java – Класс Vector
  • 30.4. Java – Класс Stack
  • 30.5. Java – Класс Dictionary
  • 30.6. Java – Класс Hashtable
  • 30.7. Java – Класс Properties
  • 31. Java – Коллекции
  • 31.1. Java – Интерфейс Collection
  • 31.2. Java – Интерфейс List
  • 31.3. Java – Интерфейс Set
  • 31.4. Java – Интерфейс SortedSet
  • 31.5. Java – Интерфейс Map
  • 31.6. Java – Интерфейс Map.Entry
  • 31.7. Java – Интерфейс SortedMap
  • 31.8. Java – Класс LinkedList
  • 31.9. Java – Класс ArrayList
  • 31.10. Java – Класс HashSet
  • 31.11. Java – Класс LinkedHashSet
  • 31.12. Java – Класс TreeSet
  • 31.13. Java – Класс HashMap
  • 31.14. Java – Класс TreeMap
  • 31.15. Java – Класс WeakHashMap
  • 31.16. Java – Класс LinkedHashMap
  • 31.17. Java – Класс IdentityHashMap
  • 31.18. Java – Алгоритмы Collection
  • 31.19. Java – Iterator и ListIterator
  • 31.20. Java – Comparator
  • 32. Java – Дженерики
  • 33. Java – Сериализация
  • 34. Java – Сеть
  • 34.1. Java – Обработка URL
  • 35. Java – Отправка Email
  • 36. Java – Многопоточность
  • 36.1. Java – Синхронизация потоков
  • 36.2. Java – Межпоточная связь
  • 36.3. Java – Взаимная блокировка потоков
  • 36.4. Java – Управление потоками
  • 37. Java – Основы работы с апплетами
  • 38. Java – Javadoc

Как создать стэк в 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

Сегодня рассмотрю такую ​​простую, но нужную структуру, как Стек (Stack). Эта структура данных имеет несколько реализаций (простейшая — реализация на базе одномерного массива или односвязного списка). Остановлюсь на первом варианте.

Теория. Стек в java

Для начала ознакомимся с небольшой теоретической базой. При использовании стека, есть доступ только к последнему добавленного элемента. Удалив этот элемент, пользователь получает доступ к предпоследнему элемента и тд. Таким образом эта структура данных реализует принцип LIFO (Last In First Out). Для удобства можно провести аналогию со стопкой тарелок или магазином пистолета (последний заряженный патрон, будет подан в патронник первым). Многие микропроцессоров имеют стековую архитектуру. Когда происходит вызов метода, адрес возврата и аргументы заносятся в стек, а при выходе изымаются из него.

Пример стека

Здесь 5 — элемент на вершине стека (назовем последний элемент — top) — рисунок 1.

Рисунок 1 — Пример стека, который будет реализован на java

Таким образом, чтобы получить из стека элемент «3», для начала нам нужно удалить «5» и «4». На этом небольшая теоретическая часть заканчивается. Добавлю, что элемент TOP, иногда еще называют «головой» (head).

Реализация стека в java

Итак, я предлагаю реализовать следующие методы для нашего стека:

1) addElement — метод, который обеспечит добавление элемента (в top позиции)

2) deleteElement — метод, которых обеспечит удаление элемента (с top позиции)

3) readTop — метод, который вернет значение элемента, который находится в позиции top

4) isEmpty — метод, который будет проверять стек на пустоту

5) isFull — метод, который будет проверять, не переполнен наш массив, в котором мы сохраняем стек

Для начала создадим в нашем проекте, класс Stack , объявим нужные для работы поля, а далее инициализируем их в конструкторе.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *