1. Обзор
Класс Java Stack реализует структуру данных стека . В Java 1.6 появился интерфейс Deque , предназначенный для реализации «двусторонней очереди», которая поддерживает вставку и удаление элементов на обоих концах.
Теперь мы также можем использовать интерфейс Deque в качестве стека LIFO (последним пришел — первым вышел). Более того, если мы посмотрим на Javadoc класса Stack , то увидим:
Более полный и непротиворечивый набор операций стека LIFO предоставляется интерфейсом
Dequeи его реализациями, которые следует использовать вместо этого класса.
В этом руководстве мы собираемся сравнить класс Java Stack и интерфейс Deque . Далее мы обсудим, почему мы должны использовать Deque over Stack для стеков LIFO .
2. Класс против интерфейса
Стек Java - это класс :
public class Stack<E> extends Vector<E> { ... }
То есть, если мы хотим создать свой собственный тип стека , мы должны наследовать класс java.util.Stack .
Поскольку Java не поддерживает множественное наследование, иногда бывает сложно расширить класс Stack , если наш класс уже является подклассом другого типа :
public class UserActivityStack extends ActivityCollection { ... }
В приведенном выше примере класс UserActivityStack является подклассом класса ActivityCollection . Следовательно, он также не может расширять класс java.util.Stack . Чтобы использовать класс Java Stack , нам может потребоваться перепроектировать наши модели данных.
С другой стороны, Deque в Java — это интерфейс:
public interface Deque<E> extends Queue<E> { ... }
Мы знаем, что класс может реализовать несколько интерфейсов в Java. Поэтому реализация интерфейса более гибкая, чем расширение класса для наследования.
Например, мы можем легко заставить наш UserActivityStack реализовать интерфейс Deque :
public class UserActivityStack extends ActivityCollection implements Deque<UserActivity> { ... }
Поэтому с точки зрения объектно-ориентированного проектирования интерфейс Deque обеспечивает большую гибкость, чем класс Stack .
3. синхронизированные методы и производительность
Мы видели, что класс Stack является подклассом java.util.Vector . Класс Vector синхронизирован. Он использует традиционный способ достижения потокобезопасности: делает свои методы « синхронизированными». ”
Как его подкласс, класс Stack также является синхронизированным .
С другой стороны, интерфейс Deque не является потокобезопасным .
Таким образом, если потокобезопасность не является обязательным требованием, Deque может обеспечить лучшую производительность, чем Stack .
4. Порядок итерации
Поскольку и Stack , и Deque являются подтипами интерфейса java.util.Collection , они также являются Iterable .
Однако интересно то, что если мы поместим одни и те же элементы в одном и том же порядке в объект Stack и экземпляр Deque , их порядок итерации будет другим.
Рассмотрим их подробнее на примерах.
Во-первых, давайте поместим некоторые элементы в объект Stack и проверим, каков его порядок итерации:
@Test
void givenAStack_whenIterate_thenFromBottomToTop() {
Stack<String> myStack = new Stack<>();
myStack.push("I am at the bottom.");
myStack.push("I am in the middle.");
myStack.push("I am at the top.");
Iterator<String> it = myStack.iterator();
assertThat(it).toIterable().containsExactly(
"I am at the bottom.",
"I am in the middle.",
"I am at the top.");
}
Если мы выполним тестовый метод выше, он пройдет. Это означает, что когда мы перебираем элементы в объекте Stack , порядок от основания стека к вершине стека .
Затем давайте проведем тот же тест на экземпляре Deque . Мы возьмем класс ArrayDeque в качестве реализации Deque в нашем тесте.
Кроме того, мы будем использовать ArrayDeque в качестве стека LIFO:
@Test
void givenADeque_whenIterate_thenFromTopToBottom() {
Deque<String> myStack = new ArrayDeque<>();
myStack.push("I am at the bottom.");
myStack.push("I am in the middle.");
myStack.push("I am at the top.");
Iterator<String> it = myStack.iterator();
assertThat(it).toIterable().containsExactly(
"I am at the top.",
"I am in the middle.",
"I am at the bottom.");
}
Этот тест тоже пройдет, если мы его прогоним.
Следовательно, порядок итераций Deque — сверху вниз .
Когда мы говорим о структуре данных стека LIFO, правильная последовательность перебора элементов в стеке должна быть сверху вниз.
То есть итератор Deque работает так, как мы ожидаем для стека.
5. Недопустимые операции стека LIFO
Классическая структура данных стека LIFO поддерживает только операции push() , pop() и peek() . И класс Stack , и интерфейс Deque поддерживают их. Все идет нормально.
Однако доступ к элементам или манипулирование ими по индексам в стеке LIFO запрещен, поскольку это нарушает правило LIFO.
В этом разделе давайте посмотрим, можем ли мы вызывать недопустимые операции со стеком с помощью Stack и Deque.
5.1. Класс java.util.Stack _
Поскольку его родительский объект Vector представляет собой структуру данных на основе массива, класс Stack имеет возможность доступа к элементам по индексам:
@Test
void givenAStack_whenAccessByIndex_thenElementCanBeRead() {
Stack<String> myStack = new Stack<>();
myStack.push("I am the 1st element."); //index 0
myStack.push("I am the 2nd element."); //index 1
myStack.push("I am the 3rd element."); //index 2
assertThat(myStack.get(0)).isEqualTo("I am the 1st element.");
}
Тест пройдет, если мы его запустим.
В тесте мы помещаем три элемента в объект Stack . После этого мы хотим получить доступ к элементу, находящемуся внизу стека.
Следуя правилу LIFO, мы должны извлечь все элементы выше, чтобы получить доступ к нижнему элементу.
Однако здесь, с объектом Stack , мы можем просто получить доступ к элементу по его индексу .
Более того, с помощью объекта Stack мы можем даже вставлять и удалять элемент по его индексу . Давайте создадим тестовый метод, чтобы доказать это:
@Test
void givenAStack_whenAddOrRemoveByIndex_thenElementCanBeAddedOrRemoved() {
Stack<String> myStack = new Stack<>();
myStack.push("I am the 1st element.");
myStack.push("I am the 3rd element.");
assertThat(myStack.size()).isEqualTo(2);
myStack.add(1, "I am the 2nd element.");
assertThat(myStack.size()).isEqualTo(3);
assertThat(myStack.get(1)).isEqualTo("I am the 2nd element.");
myStack.remove(1);
assertThat(myStack.size()).isEqualTo(2);
}
Тест также пройдет, если мы дадим ему прогон.
Поэтому, используя класс Stack , мы можем манипулировать элементами в нем так же, как работая с массивом. Это нарушило контракт LIFO.
5.2. Интерфейс java.util.Deque _
Deque не позволяет нам получить доступ, вставить или удалить элемент по его индексу. Звучит лучше, чем класс Stack .
Однако, поскольку Deque — это «двусторонняя очередь», мы можем вставлять или удалять элементы с обоих концов.
Другими словами, когда мы используем Deque в качестве стека LIFO, мы можем напрямую вставлять/удалять элемент в/из нижней части стека .
Давайте создадим тестовый метод, чтобы увидеть, как это происходит. Опять же, мы продолжим использовать класс ArrayDeque в нашем тесте:
@Test
void givenADeque_whenAddOrRemoveLastElement_thenTheLastElementCanBeAddedOrRemoved() {
Deque<String> myStack = new ArrayDeque<>();
myStack.push("I am the 1st element.");
myStack.push("I am the 2nd element.");
myStack.push("I am the 3rd element.");
assertThat(myStack.size()).isEqualTo(3);
//insert element to the bottom of the stack
myStack.addLast("I am the NEW element.");
assertThat(myStack.size()).isEqualTo(4);
assertThat(myStack.peek()).isEqualTo("I am the 3rd element.");
//remove element from the bottom of the stack
String removedStr = myStack.removeLast();
assertThat(myStack.size()).isEqualTo(3);
assertThat(removedStr).isEqualTo("I am the NEW element.");
}
В тесте сначала мы вставляем новый элемент в конец стека с помощью метода addLast() . Если вставка прошла успешно, мы попытаемся удалить ее с помощью метода removeLast() .
Если мы выполняем тест, он проходит.
Следовательно, Deque также не подчиняется контракту LIFO .
5.3. Реализация LifoStack на основе Deque
Мы можем создать простой интерфейс LifoStack для выполнения контракта LIFO:
public interface LifoStack<E> extends Collection<E> {
E peek();
E pop();
void push(E item);
}
Когда мы создаем реализации нашего интерфейса LifoStack , мы можем обернуть стандартные реализации Deque Java .
Давайте создадим класс ArrayLifoStack в качестве примера, чтобы быстро понять его:
public class ArrayLifoStack<E> implements LifoStack<E> {
private final Deque<E> deque = new ArrayDeque<>();
@Override
public void push(E item) {
deque.addFirst(item);
}
@Override
public E pop() {
return deque.removeFirst();
}
@Override
public E peek() {
return deque.peekFirst();
}
// forward methods in Collection interface
// to the deque object
@Override
public int size() {
return deque.size();
}
...
}
Как показывает класс ArrayLifoStack , он поддерживает только операции, определенные в нашем интерфейсе LifoStack и интерфейсе java.util.Collection .
Таким образом, это не нарушит правило LIFO.
6. Заключение
Начиная с Java 1.6, как java.util.Stack , так и java.util.Deque можно использовать в качестве стеков LIFO. В этой статье рассматривалась разница между этими двумя типами.
Мы также проанализировали, почему мы должны использовать интерфейс Deque вместо класса Stack для работы со стеками LIFO.
Кроме того, как мы обсуждали на примерах, и Stack , и Deque более или менее нарушают правило LIFO.
Наконец, мы показали один из способов создания интерфейса стека, подчиняющегося контракту LIFO.
Как всегда, полный исходный код доступен на GitHub .