Когда испольщовал Dequeue?

Использование Deque в Java

Deque (Double Ended Queue) — двусторонняя очередь, которая позволяет добавлять и удалять элементы с обоих концов. Это одна из самых полезных структур данных, которые я регулярно использую в реальных проектах.

Что такое Deque

public interface Deque<E> extends Collection<E> {
    // Добавление
    void addFirst(E e);      // в начало
    void addLast(E e);       // в конец
    boolean offerFirst(E e); // в начало (для очередей с ограничением)
    boolean offerLast(E e);  // в конец
    
    // Удаление
    E removeFirst();    // из начала
    E removeLast();     // из конца
    E pollFirst();      // из начала (null если пусто)
    E pollLast();       // из конца
    
    // Получение
    E getFirst();
    E getLast();
    E peekFirst();
    E peekLast();
}

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

1. Реализация LRU кеша

Это одна из самых частых задач на собеседованиях. Deque идеально подходит для отслеживания порядка использования элементов:

class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, V> cache;
    private final Deque<K> lru; // порядок доступа
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.lru = new LinkedList<>();
    }
    
    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null;
        }
        // Переместим в конец (самый свежий)
        lru.remove(key);
        lru.addLast(key);
        return cache.get(key);
    }
    
    public void put(K key, V value) {
        if (cache.containsKey(key)) {
            lru.remove(key);
        } else if (cache.size() >= capacity) {
            // Удалим самый старый (первый)
            K oldest = lru.removeFirst();
            cache.remove(oldest);
        }
        cache.put(key, value);
        lru.addLast(key);
    }
}

2. Реализация скользящего окна (sliding window)

Для поиска максимума в подмассиве размером k:

class SlidingWindowMax {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>(); // индексы
        int[] result = new int[nums.length - k + 1];
        
        for (int i = 0; i < nums.length; i++) {
            // Удалим индексы, вышедшие из окна
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            
            // Удалим элементы, меньшие текущего
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            
            deque.addLast(i);
            
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}

3. Обработка документов в формате Markdown (паллиндромная проверка)

class PalindromeChecker {
    public boolean isPalindrome(String s) {
        Deque<Character> deque = new ArrayDeque<>();
        
        for (char c : s.toLowerCase().toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                deque.addLast(c);
            }
        }
        
        while (!deque.isEmpty() && deque.size() > 1) {
            if (!deque.pollFirst().equals(deque.pollLast())) {
                return false;
            }
        }
        return true;
    }
}

4. Обработка обратной польской нотации (RPN)

class RPNCalculator {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (String token : tokens) {
            if (isOperator(token)) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(calculate(a, b, token));
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
    
    private boolean isOperator(String s) {
        return s.equals("+") || s.equals("-") || 
               s.equals("*") || s.equals("/");
    }
    
    private int calculate(int a, int b, String op) {
        return switch(op) {
            case "+" -> a + b;
            case "-" -> a - b;
            case "*" -> a * b;
            case "/" -> a / b;
            default -> 0;
        };
    }
}

Deque vs Queue vs Stack

Реализации Deque в Java

• LinkedList — рекомендуется для большинства случаев, O(1) для добавления/удаления с обоих концов
• ArrayDeque — более эффективна по памяти, но не потокобезопасна
• ConcurrentLinkedDeque — для многопоточных приложений

Когда я использовал Deque в проектах

1. Кеширование: реализация LRU кешей для оптимизации запросов к БД
2. Обработка задач: очереди с приоритетом и скользящие окна для аналитики
3. Алгоритмы графов: BFS/DFS при обходе больших графов
4. Интеграция с сообщениями: обработка event streaming данных

Deque — это фундаментальная структура данных, которая решает множество реальных проблем эффективно и элегантно.