Java Deque

объектно-ориентированного программирования Java Программирование и разработка

Очередь в вычислениях представляет собой структуру данных списка «первым поступил — первым обслужен» (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()

Читайте также:  Привязка ввода формы Vue.js с опцией выбора

Это эквивалент исключения из очереди. Удаляет элемент из начала списка. Следующая программа иллюстрирует это:

    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.

Читайте также:  Как объявить функцию, которая принимает один параметр в PHP?

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 была объяснена выше.

Оцените статью
bestprogrammer.ru
Добавить комментарий

Adblock
detector