Очередь в вычислениях представляет собой структуру данных списка «первым поступил — первым обслужен» (FIFO). Это означает, что для добавления нового элемента элемент ставится в очередь в конце списка; а чтобы удалить элемент, он удаляется из очереди из начала списка. Передний элемент также можно просмотреть, то есть прочитать его, но не удалить.
Стек в вычислительной технике представляет собой структуру данных списка «последний пришел — первый ушел» (LIFO). Это означает, что для добавления нового элемента элемент помещается в начало списка; а чтобы удалить элемент, он выдвигается из начала списка. Передний элемент также можно просмотреть, то есть прочитать его, но не удалить.
Название «дека» — это краткая форма от «двухсторонняя очередь», произносимая как «колода». Deque представляет собой структуру данных FIFO и списка LIFO в Java. Ну и еще в Java deque — это Интерфейс, из которого можно реализовать классы. В Java уже реализованы следующие классы: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList. Для изучения в этой статье был выбран класс ArrayDeque.
Ниже приведены соответствующие методы Java ArrayDeque для очереди:
| Queue | ArrayDeque |
|---|---|
| enqueue | add |
| dequeue | remove |
| peek | peek |
Ниже приведены соответствующие методы Java ArrayDeque для стека:
| Stack | ArrayDeque |
|---|---|
| push | push |
| pop | pop |
| peek | peek |
Примечание. Метод peek() одинаков для обоих вариантов поведения. Кроме того, remove() и pop() очень похожи; они объясняются ниже.
Создание ArrayDeque
Класс ArrayDeque находится в пакете java.util.*, который необходимо импортировать. Он имеет три конструктора, два из которых описаны здесь.
public ArrayDeque()
Создает пустую очередь, как показано в следующем фрагменте кода:
ArrayDeque<Character> dq = new ArrayDeque<Character>();
dq.add(‘F’); dq.add(‘G’); dq.add(‘H’); dq.add(‘I’); dq.add(‘J’);
Добавлено пять элементов. Здесь дек называется dq.
public ArrayDeque(Collection<? extends E> c)
Этот перегруженный конструктор создает очередь из другой очереди. Следующий сегмент кода иллюстрирует это:
ArrayDeque<Character> dq = new ArrayDeque<Character>();
dq.add(‘F’); dq.add(‘G’); dq.add(‘H’); dq.add(‘I’); dq.add(‘J’);ArrayDeque<Character> dq1 = new ArrayDeque<Character>(dq);
dq1 был создан из dq.
Методы класса ArrayDeque
public boolean add(E e)
Это эквивалент постановки в очередь. Он добавляет элемент в конец двухсторонней очереди. Следующая программа иллюстрирует это:
import java.util.*;
public class TheClass {
public static void main(String[] args) {
ArrayDeque<Character> dq = new ArrayDeque<Character>();
dq.add(‘F’); dq.add(‘G’); dq.add(‘H’); dq.add(‘I’); dq.add(‘J’);
}
}
public int size()
Возвращает размер (длину) очереди. Следующая программа иллюстрирует это:
import java.util.*;
public class TheClass {
public static void main(String[] args) {
ArrayDeque<Character> dq = new ArrayDeque<Character>();
dq.add(‘F’); dq.add(‘G’); dq.add(‘H’); dq.add(‘I’); dq.add(‘J’);int sz = dq.size();
System.out.println(sz);
}
}
Выход 5.
public E remove()
Это эквивалент исключения из очереди. Удаляет элемент из начала списка. Следующая программа иллюстрирует это:
import java.util.*;
public class TheClass {
public static void main(String[] args) {
ArrayDeque<Character> dq = new ArrayDeque<Character>();
dq.add(‘F’); dq.add(‘G’); dq.add(‘H’); dq.add(‘I’); dq.add(‘J’);char ch1 = dq.remove(); char ch2 = dq.remove(); char ch3 = dq.remove();
char ch4 = dq.remove(); char ch5 = dq.remove();System.out.print(ch1); System.out.print(‘ ‘); System.out.print(ch2); System.out.print(‘ ‘);
System.out.print(ch3); System.out.print(‘ ‘); System.out.print(ch4); System.out.print(‘ ‘);
System.out.print(ch5); System.out.print(‘ ‘);
System.out.println();
}
}
Результат:
F G H I J
демонстрируя поведение FIFO.
public E peek()
Считывает элемент в начале двухсторонней очереди, не удаляя его. Следующая программа иллюстрирует это:
import java.util.*;
public class TheClass {
public static void main(String[] args) {
ArrayDeque<Character> dq = new ArrayDeque<Character>();
dq.add(‘F’); dq.add(‘G’); dq.add(‘H’); dq.add(‘I’); dq.add(‘J’);char ch1 = dq.peek(); char ch2 = dq.peek(); char ch3 = dq.peek();
char ch4 = dq.peek(); char ch5 = dq.peek();System.out.print(ch1); System.out.print(‘ ‘); System.out.print(ch2); System.out.print(‘ ‘);
System.out.print(ch3); System.out.print(‘ ‘); System.out.print(ch4); System.out.print(‘ ‘);
System.out.print(ch5); System.out.print(‘ ‘);
System.out.println();
}
}
Результат:
F F F F F
что указывает на то, что ничего не было удалено, а первый элемент только что был прочитан пять раз.
public void push(E e)
Добавляет элемент в начало очереди. Следующая программа иллюстрирует это:
import java.util.*;
public class TheClass {
public static void main(String[] args) {
ArrayDeque<Character> dq = new ArrayDeque<Character>();
dq.push(‘F’); dq.push(‘G’); dq.push(‘H’); dq.push(‘I’); dq.push(‘J’);char ch1 = dq.remove(); char ch2 = dq.remove(); char ch3 = dq.remove();
char ch4 = dq.remove(); char ch5 = dq.remove();System.out.print(ch1); System.out.print(‘ ‘); System.out.print(ch2); System.out.print(‘ ‘);
System.out.print(ch3); System.out.print(‘ ‘); System.out.print(ch4); System.out.print(‘ ‘);
System.out.print(ch5); System.out.print(‘ ‘);
System.out.println();
}
}
Результат:
J I H G F
показывает поведение LIFO.
public E pop()
Удаляет и возвращает первый элемент очереди. Следующая программа иллюстрирует это:
import java.util.*;
public class TheClass {
public static void main(String[] args) {
ArrayDeque<Character> dq = new ArrayDeque<Character>();
dq.push(‘F’); dq.push(‘G’); dq.push(‘H’); dq.push(‘I’); dq.push(‘J’);char ch1 = dq.pop(); char ch2 = dq.pop(); char ch3 = dq.pop();
char ch4 = dq.pop(); char ch5 = dq.pop();System.out.print(ch1); System.out.print(‘ ‘); System.out.print(ch2); System.out.print(‘ ‘);
System.out.print(ch3); System.out.print(‘ ‘); System.out.print(ch4); System.out.print(‘ ‘);
System.out.print(ch5); System.out.print(‘ ‘);
System.out.println();
}
}
Результат:
J I H G F
показывает поведение LIFO.
public void forEach(Consumer<? super E> action)
Этот метод forEach можно использовать для доступа к каждому элементу в двухсторонней очереди. Следующая программа использует его для печати всех элементов очереди:
import java.util.*;
public class TheClass {
public static void main(String[] args) {
ArrayDeque<Character> dq = new ArrayDeque<Character>();
dq.push(‘F’); dq.push(‘G’); dq.push(‘H’); dq.push(‘I’); dq.push(‘J’);dq.forEach((item) -> System.out.print(item + » «));
System.out.println();
}
}
Результат:
J I H G F
item — это фиктивная переменная, представляющая каждый элемент очереди. Обратите внимание на то, как он использовался. Обратите внимание на использование оператора стрелки ->. Итерация производилась в обратном порядке.
Iterator<E> iterator()
Возвращает итератор, который можно использовать для удаления элемента внутри двухсторонней очереди. Однако это действие занимает больше времени, чем удаление элемента в начале или в конце очереди. Следующий оператор вернет итератор для символов двухсторонней очереди.
Iterator<Character> iter = dq.iterator();
где iter — объект итератора, а dq — объект очереди.
Итератор имеет следующие методы:
boolean hasNext(): возвращает true, если итерация содержит больше элементов.
E next(): возвращает следующий элемент в итерации.
по умолчанию void remove(): удаляет из списка последний элемент, возвращенный этим итератором (следующий).
Обратите внимание, что у него нет метода для вставки элемента в очередь.
Удаление элемента внутри Deque
Следующая программа удаляет ’H’ из середины списка очереди: F, G, H, I, J:
import java.util.*;
public class TheClass {
public static void main(String[] args) {
ArrayDeque<Character> dq = new ArrayDeque<Character>();
dq.push(‘F’); dq.push(‘G’); dq.push(‘H’); dq.push(‘I’); dq.push(‘J’);Iterator<Character> iter = dq.iterator();
iter.next(); iter.next(); iter.next();
iter.remove();dq.forEach((item) -> System.out.print(item + » «));
System.out.println();
}
}
Результат:
J I G F
Обратите внимание, что next() пришлось вызывать три раза.
Заключение
В Java deque является коллекцией как FIFO, так и LIFO. Deque в Java на самом деле представляет собой интерфейс, из которого должен быть реализован класс, прежде чем можно будет использовать deque. К счастью, в Java уже есть следующие реализованные классы Deque: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList. Операция для ArrayDeque была объяснена выше.
