Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / Java

Deque — kolejka dwustronna i stos

java.util.Deque<E> opisuje kolejkę dwustronną: elementy można dodawać i usuwać na obu końcach. Ten sam interfejs obsługuje kolejkę FIFO oraz stos LIFO; o zachowaniu decyduje wybór metod.

Wersja: Java SE 21; repository runtime, production runtime not attested

Składnia

Deque<E> deque = new ArrayDeque<>();
boolean accepted = deque.offerLast(element);
deque.push(element);
E first = deque.pop();
boolean empty = deque.isEmpty();

java.util.Deque<E> jest interfejsem kolekcji z początkiem i końcem. Kolejka FIFO dodaje elementy na końcu i usuwa z początku; stos LIFO dodaje i usuwa na początku. ArrayDeque<E> jest konkretną implementacją używaną w przykładzie.

Deque.offerLast(e) dodaje na końcu i zwraca true po dodaniu, a false, gdy ograniczenie pojemności uniemożliwia dodanie. Nie oznacza to braku wyjątków dla nieprawidłowych elementów. Deque.push(e) dodaje na początku jak addFirst(e), zwraca void i przy braku miejsca zgłasza IllegalStateException.

Deque.pop() usuwa i zwraca pierwszy element jak removeFirst(); dla pustej kolekcji zgłasza NoSuchElementException. pollFirst() zamiast tego zwraca null. Deque.isEmpty() zwraca true, gdy nie ma elementów. Sprawdzenie pustki przed usunięciem nie jest operacją atomową.

ArrayDeque rośnie w razie potrzeby, nie dopuszcza null i nie jest bezpieczna wątkowo bez zewnętrznej synchronizacji. W przykładzie po dodaniu A, B i wykonaniu push("C") kolejność od początku to C, A, B. Łączenie obu sposobów dodawania nie daje czystego stosu LIFO dla wszystkich elementów.

Przykłady

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        System.out.println(deque.offerLast("A"));
        deque.offerLast("B");
        deque.push("C");
        while (!deque.isEmpty()) {
            System.out.println(deque.pop());
        }
        System.out.println(deque.isEmpty());
    }
}

Wynik

true
C
A
B
true

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła