1. Обзор
Класс Java Stack реализует структуру данных стека. Java 1.6 представила интерфейс Deque , предназначенный для реализации “двусторонней очереди”, которая поддерживает вставку и удаление элементов на обоих концах.
Теперь мы также можем использовать интерфейс Deque в качестве стека LIFO (Last-In-First-Out). Более того, если мы посмотрим на Javadoc Стека класса , мы увидим:
Более полный и согласованный набор операций стека LIFO обеспечивается интерфейсом Deque и его реализациями, которые следует использовать в предпочтении к этому классу.
В этом уроке мы сравним класс Java Stack и интерфейс Deque . Далее мы обсудим почему мы должны использовать Deque over Stack для стеков LIFO .
2. Класс против Интерфейс
Java Stack является классом :
public class Stackextends Vector { ... }
То есть, если мы хотим создать свой собственный тип Stack , мы должны унаследовать java.util.Стек класс.
Поскольку Java не поддерживает множественное наследование, иногда может быть трудно расширить класс Stack , если наш класс уже является подклассом другого типа :
public class UserActivityStack extends ActivityCollection { ... }В приведенном выше примере класс User Activity Stack является подклассом класса Activity Collection . Поэтому он также не может расширить java.util.Стек класс. Чтобы использовать класс Java Stack , нам может потребоваться перепроектировать наши модели данных.
С другой стороны, Java Deque – это интерфейс:
public interface Dequeextends Queue { ... }
Мы знаем, что класс может реализовать несколько интерфейсов в Java. Поэтому реализация интерфейса является более гибкой, чем расширение класса для наследования.
Например, мы можем легко сделать наш Стек активности пользователя реализовать интерфейс Deque :
public class UserActivityStack extends ActivityCollection implements Deque{ ... }
Таким образом, с точки зрения объектно-ориентированного проектирования интерфейс Deque обеспечивает нам большую гибкость, чем Stack class .
3. синхронизированные методы и производительность
Мы видели, что класс Stack является подклассом java.util.Vector . Класс Vector синхронизируется. Он использует традиционный способ достижения потокобезопасности: делает свои методы ” синхронизированными. “
В качестве подкласса/| класс Stack также синхронизирован .
С другой стороны, интерфейс Deque не является потокобезопасным .
Таким образом, если потокобезопасность не является обязательным требованием, Deque может обеспечить нам лучшую производительность, чем Stack .
4. Порядок итераций
Поскольку оба Stack и Deque являются подтипами java.util.Коллекция интерфейс, они также итерируемы .
Однако интересно то, что если мы помещаем одни и те же элементы в одном и том же порядке в объект Stack и экземпляр Deque , их порядки итераций различны.
Давайте подробнее рассмотрим их на примерах.
Во-первых, давайте поместим некоторые элементы в объект Stack и проверим, каков порядок его итераций:
@Test
void givenAStack_whenIterate_thenFromBottomToTop() {
Stack 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 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 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 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 имеет возможность доступа к элементам по индексам:
@Test
void givenAStack_whenAccessByIndex_thenElementCanBeRead() {
Stack 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 . После этого мы хотим получить доступ к элементу, расположенному в нижней части стека.
Следуя правилу ЛИФО, мы должны открыть все элементы выше, чтобы получить доступ к нижнему элементу.
Однако здесь, с объектом Stack , мы можем просто получить доступ к элементу по его индексу .
Более того, с помощью объекта Stack мы можем даже вставлять и удалять элемент по его индексу . Давайте создадим тестовый метод, чтобы доказать это:
@Test
void givenAStack_whenAddOrRemoveByIndex_thenElementCanBeAddedOrRemoved() {
Stack 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 , мы можем манипулировать элементами в нем так же, как при работе с массивом. Это нарушило контракт ЛИФО.
5.2. java.util.Интерфейс Deque
Deque не позволяет нам получать доступ, вставлять или удалять элемент по его индексу. Это звучит лучше, чем класс Stack .
Однако, поскольку Deque является “двусторонней очередью”, мы можем вставить или удалить элемент с обоих концов.
Другими словами, когда мы используем Deque в качестве стека LIFO, мы можем вставить/удалить элемент в/из нижней части стека напрямую .
Давайте построим метод тестирования, чтобы увидеть, как это происходит. Опять же, мы продолжим использовать класс ArrayDeque в нашем тесте:
@Test
void givenADeque_whenAddOrRemoveLastElement_thenTheLastElementCanBeAddedOrRemoved() {
Deque 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. Реализация стека Lifo на основе Deque
Мы можем создать простой Lifo Stack интерфейс для выполнения контракта LIFO:
public interface LifoStackextends Collection { E peek(); E pop(); void push(E item); }
Когда мы создаем реализации нашего интерфейса Lifo Stack , мы можем обернуть стандартные реализации Java Deque .
Давайте создадим класс Array Lifo Stack в качестве примера, чтобы быстро понять его:
public class ArrayLifoStackimplements LifoStack { private final Deque 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(); } ... }
Как показывает класс Array Lifo Stack , он поддерживает только операции, определенные в нашем интерфейсе Lifo Stack и java.util.Коллекция Интерфейс.
Таким образом, это не нарушит правило ЛИФО.
6. Заключение
Начиная с Java 1.6, оба java.util.Стек и java.util.Deque может использоваться в качестве стеков ЛИФО. В этой статье рассматривается разница между этими двумя типами.
Мы также проанализировали, почему мы должны использовать интерфейс Deque над классом Stack для работы со стеками LIFO.
Кроме того, как мы уже обсуждали в примерах, и Stack , и Deque более или менее нарушают правило ЛИФО.
Наконец, мы показали один из способов создания интерфейса стека, подчиняющегося контракту LIFO.
Как всегда, полный исходный код доступен на GitHub .