0Pricing
Java Academy · Урок

Операции Deque: стек и очередь

Используйте LinkedList как Deque, реализуя поведение стека (push/pop) и очереди (offer/poll).

«Операции Deque: стек и очередь» — бесплатный урок Java Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Java Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Java Academy содержит 4 уроков всего.

Двусторонняя очередь

Двусторонняя очередь позволяет добавлять и удалять элементы с обоих концов. Интерфейс Deque в Java реализуется классами LinkedList и ArrayDeque.

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

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A"); // front
deque.addLast("B");  // back
deque.addFirst("Z"); // new front

System.out.println(deque); // [Z, A, B]

ArrayDeque и LinkedList в роли двусторонней очереди

ArrayDeque обычно предпочтительнее LinkedList в роли двусторонней очереди:

  • Нет накладных расходов на отдельный узел для каждого элемента
  • Лучшее размещение данных с точки зрения кэша
  • Немного более высокая скорость операций со стеком и очередью

Выбирайте LinkedList только тогда, когда вам также нужен интерфейс List.

Операции со стеком через двустороннюю очередь

Используйте push (addFirst) и pop (removeFirst), чтобы имитировать стек LIFO. Избегайте устаревшего класса Stack — он синхронизирован и устарел.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.pop());  // 3
System.out.println(stack.peek()); // 2 (no removal)
System.out.println(stack.pop());  // 2

Операции с очередью через двустороннюю очередь

Используйте offer (addLast) и poll (removeFirst), чтобы имитировать очередь FIFO. offer возвращает false при сбое, а add выбрасывает исключение.

Deque<String> queue = new ArrayDeque<>();
queue.offer("task1");
queue.offer("task2");
queue.offer("task3");

System.out.println(queue.poll());  // task1
System.out.println(queue.poll());  // task2
System.out.println(queue.size());  // 1

Справочная таблица методов двусторонней очереди

Deque предоставляет два семейства методов: одно выбрасывает исключения, другое возвращает специальные значения:

  • addFirst/addLast и offerFirst/offerLast
  • removeFirst/removeLast и pollFirst/pollLast
  • getFirst/getLast и peekFirst/peekLast

Предпочитайте семейство offer/poll/peek, чтобы избежать исключений для пустых двусторонних очередей.

Практический пример: отмена и повтор с двумя стеками

Классический вариант использования Deque: история отмены — это стек. Повтор — еще один стек.

Deque<String> undo = new ArrayDeque<>();
Deque<String> redo = new ArrayDeque<>();

undo.push("type 'Hello'");
undo.push("type ' World'");

String action = undo.pop();
System.out.println("Undone: " + action); // type ' World'
redo.push(action);

System.out.println("Redo top: " + redo.peek()); // type ' World'

Проверка палиндрома с помощью двусторонней очереди

Двусторонние очереди делают проверку палиндрома элегантной: сравнивайте символы одновременно с обоих концов.

Deque<Character> deque = new ArrayDeque<>();
for (char c : "racecar".toCharArray()) deque.add(c);

boolean isPalindrome = true;
while (deque.size() > 1) {
    if (!deque.pollFirst().equals(deque.pollLast())) {
        isPalindrome = false;
        break;
    }
}
System.out.println(isPalindrome); // true

BFS с очередью

Поиск в ширину использует очередь. ArrayDeque — стандартный выбор для BFS в олимпиадном программировании и при обходе графов.

import java.util.*;

// BFS on a simple adjacency list
Map<Integer,List<Integer>> graph = Map.of(
    1, List.of(2,3),
    2, List.of(4),
    3, List.of(4),
    4, List.of()
);
Deque<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
queue.offer(1);
while (!queue.isEmpty()) {
    int node = queue.poll();
    if (visited.add(node)) {
        System.out.print(node + " ");
        queue.addAll(graph.get(node));
    }
}

DFS со стеком

Поиск в глубину использует стек. И здесь предпочтительнее ArrayDeque, а не устаревший класс Stack.

Deque<Integer> stack = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
stack.push(1);
while (!stack.isEmpty()) {
    int node = stack.pop();
    if (visited.add(node)) {
        System.out.print(node + " ");
        // push neighbors (will be processed in reverse order)
        List<Integer> neighbors = List.of(2, 3); // simplified
        for (int n : neighbors) if (!visited.contains(n)) stack.push(n);
    }
}

Ограниченная двусторонняя очередь с проверкой размера

ArrayDeque увеличивается динамически, но можно вручную задать ограничение вместимости, чтобы имитировать буфер ограниченного размера:

Deque<Integer> buffer = new ArrayDeque<>();
int MAX = 3;

for (int i = 1; i <= 5; i++) {
    if (buffer.size() >= MAX) {
        buffer.pollFirst(); // drop oldest
    }
    buffer.offerLast(i);
}
System.out.println(buffer); // [3, 4, 5]

Замечания о производительности

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

Быстрая проверка

Какой класс следует предпочесть устаревшему Stack для операций LIFO?

Итоги: операции с двусторонней очередью

Основные выводы:

  • Deque позволяет добавлять и удалять элементы с обоих концов за O(1)
  • ArrayDeque предпочтительнее LinkedList для использования только в качестве стека или очереди
  • push/pop → стек LIFO; offer/poll → очередь FIFO
  • Классические применения: отмена и повтор, BFS/DFS, скользящее окно, проверка палиндрома
  • Избегайте устаревших классов Stack и Queue

Часто задаваемые вопросы

Урок «Операции Deque: стек и очередь» бесплатный?

Да — полный текст урока «Операции Deque: стек и очередь» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Java Academy, подпишись на CoddyKit PRO. Курс Java Academy содержит 4 уроков всего.

Чему я научусь в уроке «Операции Deque: стек и очередь»?

Используйте LinkedList как Deque, реализуя поведение стека (push/pop) и очереди (offer/poll). Ты практикуешь Java Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Java Academy?

Предыдущий опыт не требуется. Java Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «Операции Deque: стек и очередь»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Java Academy?

Да. Каждый урок Java Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Внутреннее устройство LinkedList
  2. Операции Deque: стек и очередь
  3. Компромиссы LinkedList и ArrayList
  4. PriorityQueue для упорядоченной обработки
← Назад к Java Academy