Что выбрать, Stack или Queue?
Queue – один из основных интерфейсов Java Collections Framework. В общем случае (но не обязательно) представляет FIFO-коллекцию – элементы можно добавлять в хвост, брать или удалять из головы. Его наследник, интерфейс Deque (double ended queue, двусторонняя очередь), позволяет манипулировать элементами на обеих сторонах.
Stack – LIFO коллекция. То есть добавлять и удалять элементы можно только с одного конца. Кроме того, стек наследуется от Vector, и тоже является пересинхронизированным и устаревшим. Его документация явно рекомендует предпочесть использовать Deque .
В чем разница между queue и deque и stack
Очереди представляют структуру данных, работающую по принципу FIFO (first in — first out). То есть чем раньше был добавлен элемент в коллекцию, тем раньше он из нее удаляется. Это стандартная модель однонаправленной очереди. Однако бывают и двунаправленные — то есть такие, в которых мы можем добавить элемент не только в начала, но и в конец. И соответственно удалить элемент не только из конца, но и из начала.
Особенностью классов очередей является то, что они реализуют специальные интерфейсы Queue или Deque .
Интерфейс Queue
Обобщенный интерфейс Queue расширяет базовый интерфейс Collection и определяет поведение класса в качестве однонаправленной очереди. Свою функциональность он раскрывает через следующие методы:
- E element() : возвращает, но не удаляет, элемент из начала очереди. Если очередь пуста, генерирует исключение NoSuchElementException
- boolean offer(E obj) : добавляет элемент obj в конец очереди. Если элемент удачно добавлен, возвращает true, иначе — false
- E peek() : возвращает без удаления элемент из начала очереди. Если очередь пуста, возвращает значение null
- E poll() : возвращает с удалением элемент из начала очереди. Если очередь пуста, возвращает значение null
- E remove() : возвращает с удалением элемент из начала очереди. Если очередь пуста, генерирует исключение NoSuchElementException
Таким образом, у всех классов, которые реализуют данный интерфейс, будет метод offer для добавления в очередь, метод poll для извлечения элемента из головы очереди, и методы peek и element , позволяющие просто получить элемент из головы очереди.
Интерфейс Deque
Интерфейс Deque расширяет вышеописанный интерфейс Queue и определяет поведение двунаправленной очереди, которая работает как обычная однонаправленная очередь, либо как стек, действующий по принципу LIFO (последний вошел — первый вышел).
Интерфейс Deque определяет следующие методы:
- void addFirst(E obj) : добавляет элемент в начало очереди
- void addLast(E obj) : добавляет элемент obj в конец очереди
- E getFirst() : возвращает без удаления элемент из головы очереди. Если очередь пуста, генерирует исключение NoSuchElementException
- E getLast() : возвращает без удаления последний элемент очереди. Если очередь пуста, генерирует исключение NoSuchElementException
- boolean offerFirst(E obj) : добавляет элемент obj в самое начало очереди. Если элемент удачно добавлен, возвращает true, иначе — false
- boolean offerLast(E obj) : добавляет элемент obj в конец очереди. Если элемент удачно добавлен, возвращает true, иначе — false
- E peekFirst() : возвращает без удаления элемент из начала очереди. Если очередь пуста, возвращает значение null
- E peekLast() : возвращает без удаления последний элемент очереди. Если очередь пуста, возвращает значение null
- E pollFirst() : возвращает с удалением элемент из начала очереди. Если очередь пуста, возвращает значение null
- E pollLast() : возвращает с удалением последний элемент очереди. Если очередь пуста, возвращает значение null
- E pop() : возвращает с удалением элемент из начала очереди. Если очередь пуста, генерирует исключение NoSuchElementException
- void push(E element) : добавляет элемент в самое начало очереди
- E removeFirst() : возвращает с удалением элемент из начала очереди. Если очередь пуста, генерирует исключение NoSuchElementException
- E removeLast() : возвращает с удалением элемент из конца очереди. Если очередь пуста, генерирует исключение NoSuchElementException
- boolean removeFirstOccurrence(Object obj) : удаляет первый встреченный элемент obj из очереди. Если удаление произшло, то возвращает true, иначе возвращает false.
- boolean removeLastOccurrence(Object obj) : удаляет последний встреченный элемент obj из очереди. Если удаление произшло, то возвращает true, иначе возвращает false.
Таким образом, наличие методов pop и push позволяет классам, реализующим этот элемент, действовать в качестве стека. В тоже время имеющийся функционал также позволяет создавать двунаправленные очереди, что делает классы, применяющие данный интерфейс, довольно гибкими.
Класс ArrayDeque
В Java очереди представлены рядом классов. Одни из низ — класс ArrayDeque . Этот класс представляют обобщенную двунаправленную очередь, наследуя функционал от класса AbstractCollection и применяя интерфейс Deque .
В классе ArrayDeque определены следующие конструкторы:
- ArrayDeque() : создает пустую очередь
- ArrayDeque(Collection col) : создает очередь, наполненную элементами из коллекции col
- ArrayDeque(int capacity) : создает очередь с начальной емкостью capacity. Если мы явно не указываем начальную емкость, то емкость по умолчанию будет равна 16
Пример использования класса:
import java.util.ArrayDeque; public class Program < public static void main(String[] args) < ArrayDequestates = new ArrayDeque(); // стандартное добавление элементов states.add("Germany"); states.addFirst("France"); // добавляем элемент в самое начало states.push("Great Britain"); // добавляем элемент в самое начало states.addLast("Spain"); // добавляем элемент в конец коллекции states.add("Italy"); // получаем первый элемент без удаления String sFirst = states.getFirst(); System.out.println(sFirst); // Great Britain // получаем последний элемент без удаления String sLast = states.getLast(); System.out.println(sLast); // Italy System.out.printf("Queue size: %d \n", states.size()); // 5 // перебор коллекции while(states.peek()!=null) < // извлечение c начала System.out.println(states.pop()); >// очередь из объектов Person ArrayDeque people = new ArrayDeque(); people.addFirst(new Person("Tom")); people.addLast(new Person("Nick")); // перебор без извлечения for(Person p : people) < System.out.println(p.getName()); >> > class Person < private String name; public Person(String value)< name=value; >String getName() >
Структуры данных
(англ. ) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Стек должен поддерживать следующие операции:
push Добавить (положить) в конец стека новый элемент
pop Извлечь из стека последний элемент
back Узнать значение последнего элемента (не удаляя его)
size Узнать количество элементов в стеке
clear Очистить стек (удалить из него все элементы)
Хранить элементы стека мы будем в массиве. Для начала будем считать, что максимальное количество элементов в стеке не может превосходить константы MAX_SIZE , тогда для хранения элементов массива необходимо создать массив размера MAX_SIZE .
Объявим структуру данных типа stack .
const int MAX_SIZE=1000;
struct stack int m_size; // Количество элементов в стеке
int m_elems[MAX_SIZE]; // Массив для хранения элементов
stack(); // Конструктор
~stack(); // Деструктор
void push(int d); // Добавить в стек новый элемент
int pop(); // Удалить из стека последний элемент
// и вернуть его значение
int back(); // Вернуть значение последнего элемента
int size(); // Вернуть количество элементов в стеке
void clear(); // Очистить стек
>;
Объявленная здесь структура данных stack реализует стек целых чисел. Поле структуры m_size хранит количество элементов в стеке в настоящее время, сами элементы хранятся в элементах массива m_elems с индексами 0.. m_size-1 . Элементы, добавленные позже, получают большие номера.
Упражнение A — простой стек
Реализуйте структуру данных «стек», реализовав все указанные здесь методы. Напишите программу (функцию main ), содержащую описание стека и моделирующую работу стека. Функция main считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения одной команды программа должна вывести одну строчку. Возможные команды для программы:
push n Добавить в стек число n (значение n задается после команды). Программа должна вывести ok .
pop Удалить из стека последний элемент. Программа должна вывести его значение.
back Программа должна вывести значение последнего элемента, не удаляя его из стека.
size Программа должна вывести количество элементов в стеке.
clear Программа должна очистить стек и вывести ok .
exit Программа должна вывести bye и завершить работу.
Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop_back и back корректны, то есть при их исполнении в стеке содержится хотя бы один элемент.
Пример протокола работы программы
Ввод Вывод
push 2 ok
push 3 ok
push 5 ok
back 5
size 3
pop 5
size 2
push 7 ok
pop 7
clear ok
size 0
exit bye
Упражнение B — стек с обработкой ошибок
Аналогично предыдущему заданию, только снимается ограничение на корректность вызовов методов back и pop . Данные операции должны перед исполнением проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop , при этом стек пуст, то программа должна вместо числового значения вывести строку error .
При этом должна быть реализована двойная защита: вызов методов forward и pop для пустого стека не должен приводить к обращению к несуществующим элементам массива m_elems , а функция main должна выводить сообщение error , при считывании некорректной операции.
Пример протокола работы программы
Ввод Вывод
push 2 ok
back 2
pop 2
size 0
pop error
push 1 ok
size 1
exit bye
Упражнение C — стек без ограничения на размер
Реализуйте стек динамического размера, то есть ограниченный только объемом свободной оперативной памяти. Для этого используйте указатели и динамически распределяемую память. Если для полностью заполненного стека вызывается метод push размер динамического массива, отведенного для хранения стека, должен увеличиваться.
Очередь
Очередью (aнгл. )) называется структура данных, в которой элементы кладутся в конец, а извлекаются из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других.
Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый элемент, и, чтобы не сдвигать все элементы очереди, будем в отдельном поле m_start хранить индекс элемента массива, с которого начинается очередь. При удалении элементов, очередь будет «ползти» дальше от начала массива. Чтобы при этом не происходил выход за границы массива, замкнем массив в кольцо: будем считать, что за последним элементом массива следует первый.
Описание структуры очередь:
const int MAX_SIZE=1000;
struct queue int m_size; // Количество элементов в очереди
int m_start; // Номер элемента, с которого начинается очередь
int m_elems[MAX_SIZE]; // Массив для хранения элементов
queue(); // Конструктор
~queue(); // Деструктор
void push(int d); // Добавить в очередь новый элемент
int pop(); // Удалить из очереди первый элемент
// и вернуть его значение
int front(); // Вернуть значение первого элемента
int size(); // Вернуть количество элементов в очереди
void clear(); // Очистить очередь
>;
Упражнение D — простая очередь
Реализуйте простейшую очередь, размер которой не превосходит 100 элементов. Очередь поддерживает те же операции, что и стек, за исключением операции back , которая заменена операцией front . Операции front и pop всегда корректны.
Упражнение E — очередь с обработкой ошибок
Аналогично заданию B, но для очереди. Операции front и pop могут быть некорректными, в этом случае необходимо вывести error .
Программа должна содержать «двойную защиту» от некорректных операций: как в функции main , так и в самих методах pop и front .
Упражнение F — очередь без ограничений на размер
Аналогично заданию C, но для очереди. Необходимо реализовать очередь, память для которой динамически выделяется при увеличении количества элементов в ней.
Дек
Деком (англ. – аббревиатура от double-ended queue , двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека:
push_front Добавить (положить) в начало дека новый элемент
push_back Добавить (положить) в конец дека новый элемент
pop_front Извлечь из дека первый элемент
pop_back Извлечь из дека последний элемент
front Узнать значение первого элемента (не удаляя его)
back Узнать значение последнего элемента (не удаляя его)
size Узнать количество элементов в деке
clear Очистить дек (удалить из него все элементы)
Упражнение G — простой дек
Аналогично заданиям A и D, но для дека. Количество элементов в деке в любой момент не превосходит 100. Все операции pop_front , pop_back , front , back всегда корректны.
Упражнение H — дек с обработкой ошибок
Аналогично заданиям B и E, но для дека. Количество элементов в деке в любой момент не превосходит 100. При выполнении некорректных операций необходимо вывести error .
Упражнение I — дек неограниченного размера
Аналогично заданиям C и F, но для дека. Необходимо увеличивать размер дека при увеличении числа элементов в нем. При выполнении некорректных операций необходимо вывести error .
В чем разница между queue и deque и stack
Продолжение ответов на вопросы.
Другое
1. Сравните интерфейсы java.util.Queue и java.util.Deque .
Согласно документации Deque («дек», Double Ended Queue) — это линейная коллекция, поддерживающая вставку/извлечение элементов с обоих концов. Помимо этого реализации интерфейса Deque могут строится по принципу FIFO, либо LIFO.
Queue — это очередь, обычно (но необязательно) строится по принципу FIFO (First-In-First-Out) — соответственно извлечение элемента осуществляется с начала очереди, вставка элемента — в конец очереди. Этот принцип нарушает, к примеру, приоритетная очередь (PriorityQueue), использующая переданный comparator при вставке нового элемента, либо расстановка элементов осуществляется согласно естественному упорядочиванию (natural ordering).
Deque расширяет Queue .
Реализации и Deque , и Queue обычно не переопределяют методы equals() и hashCode() , основанные на сравнении хранящихся элементов. Вместо этого используются унаследованные методы класса Object , основанные на сравнении ссылок.
2. Кто кого расширяет: Queue расширяет Deque, или Deque расширяет Queue ?
Deque расширяет Queue .
3. Почему LinkedList реализует и List , и Deque ?
LinkedList позволяет добавлять элементы в начало и конец списка за константное время, что хорошо подходит для реализации интерфейса Deque (в отличие, например, от ArrayList ).
4. В чем разница между классами java.util.Arrays и java.lang.reflect.Array ?
java.util.Arrays — класс, содержащий статические методы для работы с массивами, таких как, например, поиск по массиву и его сортировка.
java.lang.reflect.Array — класс для работы с массивами при использовании рефлексии. Рефлексия — это механизм, позволяющий исследовать данные о программе во время её выполнения.
5. В чем разница между классами java.util.Collection и java.util.Collections ?
Класс java.util.Collections содержит исключительно статические методы для работы с коллекциями. В них входят методы, реализующие полиморфные алгоритмы (такие алгоритмы, использование которых возможно с разными видами структур данных), «оболочки», возвращающие новую коллекцию с инкапсулированной указанной структурой данных и некоторые другие методы.
java.util.Collection — это корневой интерфейс Java Collections Framework. Этот интерфейс в основном применяется там, где требуется высокий уровень абстракции, например, в классе java.util.Collections.
6. Напишите НЕмногопоточную программу, которая заставляет коллекцию выбросить ConcurrentModificationException
List stringList = new ArrayList<>(); stringList.add("1"); stringList.add("2"); stringList.add("3"); Iterator listIterator = stringList.iterator(); stringList.remove("2"); while (listIterator.hasNext())
7. Что такое « fail-fast поведение»?
Fail-fast поведение означает, что при возникновении ошибки или состояния, которое может привести к ошибке, система немедленно прекращает дальнейшую работу и уведомляет об этом.
В Java Collections API итераторы могут использовать либо fail-fast , либо fail-safe поведение, либо быть weakly consistent . Итератор с fail-fast поведением выбросит исключение ConcurrentModificationException, если после его создания была произведена модификация коллекции, т.е. добавлен или удален элемент (без использования метода remove() итератора). Реализация такого поведения осуществляется за счет подсчета количества модификаций коллекции (modification count):
- при изменении коллекции (удаление/добавление элемента) счетчик увеличивается;
- при создании итератора ему передается текущее значение счетчика;
- при каждом обращении к итератору сохраненное значение счетчика сравнивается с текущим, и, если они не совпадают, возникает исключение.
Использование fail-fast подхода позволяет избежать недетерминированного поведения программы в течение времени. Также стоит отметить, что fail-fast поведение не может быть абсолютно гарантировано.
8. Для множеств еnum-ов есть специальный класс java.util.EnumSet ? Зачем? Чем авторов не устраивал HashSet или TreeSet ?
EnumSet — это одна из разновидностей реализации интерфейса Set для использования с перечислениями ( Enum ). EnumSet использует массив битов для хранения значений (bit vector), что позволяет получить высокую компактность и эффективность. В структуре данных хранятся объекты только одного типа Enum , который указывается при создании экземпляра EnumSet . Все основные операции выполняются за константное время ( O(1) ) и в основном несколько быстрее (хотя и негарантированно), чем их аналоги в реализации HashSet . Пакетные операции (bulk operations, например, containsAll() и retainAll() ) выполняются очень быстро, если их аргументом является экземпляр типа Enum .
Помимо этого класс EnumSet предоставляет множество статических методов инициализации для упрощенного и удобного создания экземпляров.
Итерация по EnumSet осуществляется согласно порядку объявления элементов перечисления.
9. java.util.Stack — считается «устаревшим». Чем его рекомендуют заменять? Почему?
Рекомендуется использовать интерфейс Deque («дек», Double Ended Queue) и его реализации. Например:
Deque stack = new ArrayDeque();Стек — это структура данных, построенная на принципе LIFO (Last-In-First-Out, либо по-другому FILO). Каждое новое значение добавляется на «вершину» стека, а извлекается последний добавленный элемент (с «вершины» стека). При извлечении элемента он удаляется из структуры данных.
Класс Stack появился в JDK 1.0 и расширяет класс Vector, наследуя его функционал, что несколько нарушает понятие стека (например, класс Vector предоставляет возможность обращаться к любому элементу по индексу). Также использование Deque позволяет следовать принципу программирования на уровне интерфейсов, а не конкретных реализаций, что облегчает дальнейшую поддержку разрабатываемого класса и повышает его гибкость, позволяя при необходимости менять реализацию дека на нужную.
10. Какая коллекция реализует дисциплину обслуживания FIFO?
FIFO — First-In-First-Out (первый пришел, первым ушел). По этому принципу обычно построена такая структура данных как очередь (java.util.Queue).
11. Какая коллекция реализует дисциплину обслуживания FILO?
FILO — First-In-Last-Out (первый пришел, последним ушел). По этому принципу построена такая структура данных как стек (java.util.Stack).
12. Приведите пример, когда какая-либо коллекция выбрасывает UnsupportedOperationException .
List fixedList = Arrays.asList("1", "2", "3"); Iterator listIterator = fixedList.iterator(); while (iterator.hasNext()) < String currentElement = iterator.next(); if ("2".equals(currentElement)) < iterator.remove(); >>В данном примере возникнет исключение UnsupportedOperationException , поскольку метод asList() возвращает список фиксированной длины, т.е. удаление/добавление элементов в такой список не поддерживается.
13. Почему нельзя написать ArrayList numbers = new ArrayList() , но можно List numbers = new ArrayList() ?
Это связано с ограничениями использования generic types (обобщенных типов). ArrayList не является подтипом ArrayList , соответственно использование такой записи запрещено.
14. LinkedHashMap — что это еще за «зверь»? Что в нем от LinkedList , а что от HashMap ?
Реализация LinkedHashMap отличается от HashMap поддержкой двухсвязанного списка, определяющего порядок итерации по элементам структуры данных. По умолчанию элементы списка упорядочены согласно их порядку добавления в LinkedHashMap (insertion-order). Однако порядок итерации можно изменить, установив параметр конструктора accessOrder в значение true . В этом случае доступ осуществляется по порядку последнего обращения к элементу (access-order). Это означает, что при вызове методов get() или put() элемент, к которому обращаемся, перемещается в конец списка.
При добавлении элемента, который уже присутствует в LinkedHashMap (т.е. с одинаковым ключом), порядок итерации по элементам не изменяется.
15. LinkedHashSet — что это еще за «зверь»? Что в нем от LinkedList , а что от HashSet ?
Реализация LinkedHashSet отличается от HashSet поддержкой двухсвязанного списка, определяющего порядок итерации по элементам структуры данных. Элементы списка упорядочены согласно их порядку добавления в LinkedHashSet (insertion-order).
При добавлении элемента, который уже присутствует в LinkedHashSet (т.е. с одинаковым ключом), порядок итерации по элементам не изменяется.
16. Говорят, на LinkedHashMap легко сделать простенький кэш c «invalidation policy», знаете как?
Необходимо использовать LRU-алгоритм (Least Recently Used algorithm) и LinkedHashMap с access-order. В этом случае при обращении к элементу он будет перемещаться в конец списка, а наименее используемые элементы будут постепенно группироваться в начале списка.
Для этого в стандартной реализации LinkedHashMap (source) есть метод removeEldestEntries() , который возвращает true , если текущий объект LinkedHashMap должен удалить наименее используемый элемент из коллекции. Метод вызывается при использовании методов put() и putAll() :
void addEntry(int hash, K key, V value, int bucketIndex) < createEntry(hash, key, value, bucketIndex); // Remove eldest entry if instructed, else grow capacity if appropriate Entryeldest = header.after; if (removeEldestEntry(eldest)) < removeEntryForKey(eldest.key); >else < if (size >= threshold) resize(2 * table.length); > >Простой пример реализации кэша с очисткой старых значений при превышении указанного порога:
public class LRUCache extends LinkedHashMap < private static final int MAX_ENTRIES = 10; public LRUCache(int initialCapacity) < // Изменяем порядок итерации на access order. super(initialCapacity, 0.85f, true); >@Override protected boolean removeEldestEntry(Map.Entry eldest) < return size() >MAX_ENTRIES; > >Стоит заметить, что LinkedHashMap не позволяет полностью реализовать LRU-алгоритм, поскольку при вставке уже имеющегося в коллекции элемента порядок итерации не меняется.
17. Что позволяет сделать PriorityQueue ?
PriorityQueue — это структура данных, располагающая элементы в порядке натурального упорядочивания, либо используя переданный конструктору Comparator .
Используя PriorityQueue , можно, например, реализовать алгоритм Дейкстры для поиска кратчайшего пути от одной вершины графа к другой. Либо применять для хранения объектов согласно их приоритету: например, сортировка пациентов врача — экстренные пациенты перемещаются в начало очереди, менее срочные пациенты — ближе к концу очереди.