Реализация 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
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 , объявим нужные для работы поля, а далее инициализируем их в конструкторе.