Deque.addFirst: примеры (JAVA)

Короткие примеры использования

Пример 1. ArrayDeque - простая вставка в начало:

import java.util.ArrayDeque;
public class Demo1 {
    public static void main(String[] args) {
        ArrayDeque dq = new ArrayDeque<>();
        dq.addFirst("b");
        dq.addFirst("a");
        System.out.println(dq); // печать содержимого
    }
}

[a, b]

Пример 2. LinkedList допускает null:

import java.util.Deque;
import java.util.LinkedList;
public class Demo2 {
    public static void main(String[] args) {
        Deque dq = new LinkedList<>();
        dq.addFirst(null);
        dq.addFirst("x");
        System.out.println(dq);
    }
}

[x, null]

Пример 3. Емкостно ограниченная очередь (LinkedBlockingDeque) - переполнение приводит к исключению при addFirst, но не при offerFirst:

import java.util.concurrent.LinkedBlockingDeque;
public class Demo3 {
    public static void main(String[] args) {
        LinkedBlockingDeque dq = new LinkedBlockingDeque<>(1); // capacity = 1
        dq.addFirst(1);
        // следующая строка бросит IllegalStateException
        dq.addFirst(2);
    }
}

Exception in thread "main" java.lang.IllegalStateException: Deque full
    at java.base/java.util.concurrent.LinkedBlockingDeque.checkNotNull(LinkedBlockingDeque.java:...)
    ...

Альтернатива без исключения:

// вместо addFirst
boolean ok = dq.offerFirst(2); // вернет false, если нет места
System.out.println(ok);

false

Похожие методы в Java и их отличие

• offerFirst(E e) - вставляет в начало, но возвращает boolean вместо бросания исключения при переполнении; предпочтительнее в емкостно ограниченных структурах, когда важна явная проверка успеха.
• push(E e) - синоним addFirst для семантики стека; удобен при работе со стекоподобным API.
• addLast(E e), offerLast(E e) - вставка в хвост; используются при очередной семантике FIFO.
• removeFirst() / pollFirst() / peekFirst() - операции извлечения/просмотра из головы; выбирать следует по требованию на выбрасывание исключений (removeFirst) или безопасное завершение (pollFirst, peekFirst).

Общий выбор зависит от желаемой политики обработки ошибок: если требуется исключение при невозможности вставки, применяется addFirst / push; если важна немодифицируемая ошибка, используется offerFirst или блокирующие методы у BlockingDeque.

Аналоги в других языках и отличия

Ниже приведены параллели для популярных языков с примерами и результатами.

Python (collections.deque)

from collections import deque
dq = deque()
dq.appendleft('a')
dq.appendleft('b')
print(dq)

deque(['b', 'a'])

appendleft возвращает None, поддерживает None-подобные значения, ограничение размера задается при создании и при переполнении новая вставка вызовет автоматическое поведение или исключение в зависимости от метода.

JavaScript (Array)

const arr = [];
arr.unshift('a');
arr.unshift('b');
console.log(arr);

[ 'b', 'a' ]

Unshift возвращает новую длину массива; массивы в JS динамические, переполнение не возникает.

PHP (array_unshift)

$arr = [];
array_unshift($arr, 'a');
array_unshift($arr, 'b');
var_export($arr);

array (
  0 => 'b',
  1 => 'a',
)

C# (LinkedList<T>)

using System;
using System.Collections.Generic;
class P {
  static void Main(){
    var ll = new LinkedList();
    ll.AddFirst("a");
    ll.AddFirst("b");
    foreach(var x in ll) Console.WriteLine(x);
  }
}

b
a

AddFirst в C# возвращает void; null допустим для ссылочных типов.

Go (container/list)

package main
import (
    "container/list"
    "fmt"
)
func main() {
    l := list.New()
    l.PushFront("a")
    l.PushFront("b")
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value)
    }
}

b
a

Kotlin

val dq = ArrayDeque()
dq.addFirst("b")
dq.addFirst("a")
println(dq)

[a, b]

Kotlin использует схожие реализации с Java; поведение addFirst как в Java.

Lua

t = {}
table.insert(t, 1, 'a')
table.insert(t, 1, 'b')
for i,v in ipairs(t) do print(v) end

b
a

SQL

В SQL нет структуры deque на уровне языка. Для имитации порядка вставки можно использовать столбец с порядковым номером или временную метку и сортировать по нему при выборке.

Типичные ошибки при использовании

• NullPointerException при добавлении null в реализации, не допускающие null (пример для ArrayDeque):

import java.util.ArrayDeque;
public class Err1 {
    public static void main(String[] args) {
        ArrayDeque dq = new ArrayDeque<>();
        dq.addFirst(null); // ArrayDeque не поддерживает null
    }
}

Exception in thread "main" java.lang.NullPointerException
    at java.base/java.util.ArrayDeque.addFirst(ArrayDeque.java:...)
    ...

• IllegalStateException при добавлении в полную емкостно ограниченную реализацию (пример с LinkedBlockingDeque):

import java.util.concurrent.LinkedBlockingDeque;
class Err2 {
    public static void main(String[] args) {
        LinkedBlockingDeque dq = new LinkedBlockingDeque<>(1);
        dq.addFirst(1);
        dq.addFirst(2); // бросает IllegalStateException
    }
}

Exception in thread "main" java.lang.IllegalStateException: Deque full
    at java.base/java.util.concurrent.LinkedBlockingDeque.addFirst(LinkedBlockingDeque.java:...)
    ...

• ConcurrentModificationException при модификации deque во время итерации с помощью несправляемого итератора (негарантированное поведение у некоторых реализаций):

import java.util.Deque;
import java.util.LinkedList;
public class Err3 {
    public static void main(String[] args) {
        Deque dq = new LinkedList<>();
        dq.addFirst(1);
        for (Integer x : dq) {
            dq.addFirst(2); // может привести к ConcurrentModificationException
        }
    }
}

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:...)
    ...

Рекомендация по обработке: выбирать метод (addFirst, offerFirst, блокирующие варианты) в зависимости от желаемой модели ошибок и учитывать поддержку null у конкретной реализации.

Изменения и заметки по версиям

Сигнатура addFirst(E) и поведение интерфейса Deque оставались стабильными в основных версиях Java. Изменения главным образом касались добавления новых реализаций коллекций и улучшений параллельных структур в стандартной библиотеке, а не самого метода. Среди появившихся реализаций и утилит выделяются конкурентные и блокирующие очереди, которые расширяют сценарии использования:

• появление конкурентных реализаций с ненадёжными/ненаправленными итераторами для многопоточного доступа;
• блокирующие реализации с поддержкой ограниченной емкости и методов ожидания/таймаута.

Таким образом, ключевые изменения - не в методе, а в разнообразии реализаций и их семантике (поддержка null, поведение при переполнении, многопоточность).

Расширенные и нестандартные примеры

Пример 1. Использование как стек (push/pop) с синтаксической альтернативой:

import java.util.ArrayDeque;
public class Adv1 {
    public static void main(String[] args) {
        ArrayDeque stack = new ArrayDeque<>();
        stack.push(1);          // эквивалент addFirst(1)
        stack.addFirst(2);
        System.out.println(stack.pop()); // 2
        System.out.println(stack.pop()); // 1
    }
}

2
1

Пример 2. Двусторонняя очередь для BFS с приоритетной вставкой новых соседей в начало:

import java.util.ArrayDeque;
import java.util.Deque;
public class Adv2 {
    public static void main(String[] args) {
        Deque dq = new ArrayDeque<>();
        dq.addLast("start");
        // при обработке некоторых узлов новые элементы добавляются в начало
        String cur = dq.pollFirst();
        if ("start".equals(cur)) dq.addFirst("urgent");
        System.out.println(dq); // urgent находится в голове
    }
}

[urgent]

Пример 3. Кэш LRU с удалением последнего при переполнении:

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

public class LRUExample {
    public static void main(String[] args) {
        int capacity = 3;
        Deque dq = new ArrayDeque<>();
        HashSet set = new HashSet<>();
        int[] access = {1,2,3,1,4};
        for (int k : access) {
            if (set.contains(k)) {
                dq.remove(k);
                dq.addFirst(k);
            } else {
                if (dq.size() == capacity) {
                    int removed = dq.removeLast();
                    set.remove(removed);
                }
                dq.addFirst(k);
                set.add(k);
            }
            System.out.println(dq);
        }
    }
}

[1]
[2, 1]
[3, 2, 1]
[1, 3, 2]
[4, 1, 3]

Пример 4. Многопоточная очередь: ConcurrentLinkedDeque не блокирует и подходит для высокой конкурентности:

import java.util.concurrent.ConcurrentLinkedDeque;
public class Adv4 {
    public static void main(String[] args) {
        ConcurrentLinkedDeque dq = new ConcurrentLinkedDeque<>();
        dq.addFirst(1); // потокобезопасно
        dq.addFirst(2);
        System.out.println(dq);
    }
}

[2, 1]

Пример 5. Комбинация блокирующей вставки с тайм-аутом (BlockingDeque):

import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.TimeUnit;

public class Adv5 {
    public static void main(String[] args) throws Exception {
        LinkedBlockingDeque dq = new LinkedBlockingDeque<>(1);
        dq.putFirst(1); // блокирует при необходимости
        // следующий вызов будет ждать указанное время и вернет false если не удалось
        boolean added = dq.offerFirst(2, 500, TimeUnit.MILLISECONDS);
        System.out.println(added);
    }
}

false

Пояснения: в расширенных сценариях addFirst полезен при реализации LRU-кэшей, гибридных алгоритмов обхода графа, а также как базовая операция для стековой семантики. Для многопоточного кода обычно применяются специальные реализации (ConcurrentLinkedDeque, LinkedBlockingDeque), а для управления поведением при переполнении - offerFirst или блокирующие методы.