stack_queue_presentation_java

1.

Стек и очередь
Базовые структуры данных и их применение в Java
STACK
LIFO
QUEUE
FIFO
Когда порядок извлечения меняет
поведение алгоритма
последний
вошёл - первый
вышел
10
20
30
40
первый вошёл первый вышел
10
20
30
40
Примеры: undo, стек вызовов, очереди задач, BFS/DFS,
обработка сообщений
Стек и очередь · Java
1/10

2.

Почему порядок извлечения важен
Одна и та же коллекция даёт разное поведение программы
Вход: A, B, C
Стек выдаст: C, B, A
Вход: A, B, C
Очередь выдаст: A, B,
C
Стек подходит, когда важен самый свежий
элемент
Очередь подходит, когда важен порядок
поступления
- undo / redo
- рекурсия и стек вызовов
- DFS, разбор скобок, парсинг
- очереди задач
- обработка сообщений и событий
- BFS и планирование работ
Стек и очередь · Java
2/10

3.

Стек: принцип LIFO
Last In, First Out - последним пришёл, первым вышел
Операции
Java: Deque как стек
push(x) - положить наверх
pop() - снять верхний
элемент
peek() - посмотреть
верхушку
isEmpty() / size()
1 Deque<Integer> stack = new ArrayDeque<>();
2
3 stack.push(10);
4 stack.push(20);
5 stack.push(30);
6
7 System.out.println(stack.peek()); // 30
8 System.out.println(stack.pop()); // 30
9 System.out.println(stack.pop()); // 20
Состояние после
push(10), push(20),
push(30)
верх
30
20
10
Стек и очередь · Java
Почему в Java чаще
не Stack?
ArrayDeque обычно
быстрее в
однопоточном коде,
не наследует
устаревший Vector и
подходит сразу для
двух сценариев: стек
и очередь.
3/10

4.

Где используют стек
Три типовых сценария, где важен последний добавленный элемент
1. Стек вызовов
2. Проверка скобок
Методы завершаются в
Открывающую скобку кладём в
обратном порядке к вызову. Это
стек, закрывающую - снимаем.
фундамент рекурсии и
В конце стек должен быть пуст.
обработки функций.
3. Undo / история действий
Последнее действие
отменяется первым: Typed C ->
Undo
Пример: валидация скобок
1 boolean isValid(String s) {
2
Deque<Character> st = new ArrayDeque<>();
3
for (char ch : s.toCharArray()) {
4
if (ch == '(') st.push(ch);
5
else if (ch == ')') {
6
if (st.isEmpty()) return false;
7
st.pop();
8
}
9
}
10
return st.isEmpty();
11 }
Стек и очередь · Java
Ключевая идея
Стек хорошо работает там, где нужна
локальность по времени: самый свежий элемент
важнее остальных. Поэтому он естественно
сочетается с рекурсией, отменой действий,
парсингом и обходом графов в глубину.
4/10

5.

Очередь: принцип FIFO
First In, First Out - первым пришёл, первым вышел
Java: Queue
Операции
offer(x) - добавить в конец
poll() - забрать из начала
peek() - посмотреть
первый элемент
isEmpty() / size()
После offer(10),
offer(20), offer(30)
начало -> 10 20
конец
Стек и очередь · Java
1 Queue<Integer> queue = new ArrayDeque<>();
2
3 queue.offer(10);
4 queue.offer(20);
5 queue.offer(30);
6
7 System.out.println(queue.peek()); // 10
8 System.out.println(queue.poll()); // 10
9 System.out.println(queue.poll()); // 20
Почему ArrayDeque
удобен и здесь
Он часто быстрее
LinkedList для
обычных очередей,
компактнее по памяти
и под капотом уже
реализует
двустороннюю
очередь.
30 <-
5/10

6.

Очередь в Java и на практике
Безопасные методы, исключения и реальные сценарии использования
Пример обработки задач
Сценарий: очередь
задач
Методы Queue
offer / poll / peek
- безопасные методы
- возвращают false / null
- удобны в прикладном коде
add / remove / element
- методы с исключениями
- подходят, когда пустая очередь
означает ошибку
Стек и очередь · Java
1 Queue<String> tasks = new
ArrayDeque<>();
2
3 tasks.offer("Send email");
4 tasks.offer("Generate report");
5 tasks.offer("Clean temp files");
6
7 while (!tasks.isEmpty()) {
8
String task = tasks.poll();
9
System.out.println("Processing: "
+ task);
10 }
Controller -> Queue ->
Worker
Пользователь создаёт
работу, backend
складывает её в
очередь, а отдельный
Где
ещёобрабатывает
встречается
worker
очередь
позже.
- очередь печати и
сетевые пакеты
- брокеры сообщений:
RabbitMQ, Kafka, SQS
- события UI и обработка
запросов
- BFS в графах и
деревьях
6/10

7.

Deque: стек и очередь в одном интерфейсе
Можно работать и с началом, и с концом
Deque
как стек
1 Deque<Integer>
Deque умеет:
addFirst / removeFirst
addLast / removeLast
peekFirst / peekLast
Поэтому из него
получаются и стек, и
очередь.
Стек и очередь · Java
stack = new
ArrayDeque<>();
2 stack.push(1);
3 stack.push(2);
4 stack.push(3);
5
System.out.println(stack.pop());
// 3
Deque
как очередь
1 Queue<Integer>
queue = new
ArrayDeque<>();
2 queue.offer(1);
3 queue.offer(2);
4 queue.offer(3);
5
System.out.println(queue.poll())
; // 1
Практический совет
Если нужен обычный стек или
очередь в Java, начните с
ArrayDeque. Это хороший
дефолт: единый API, хорошая
производительность и понятное
поведение.
7/10

8.

Стек и очередь в алгоритмах: DFS и BFS
Одна структура ведёт в глубину, другая - по уровням
DFS использует стек
BFS использует очередь
Идём как можно глубже, затем
откатываемся назад.
Обходим граф по уровням: сначала соседи,
затем соседи соседей.
Пример порядка:
1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
Пример порядка:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
Почему так происходит
LIFO заставляет алгоритм продолжать уже
начатый путь. FIFO хранит фронт текущего
уровня и обслуживает вершины в порядке
обнаружения.
Стек и очередь · Java
Когда выбирать
DFS: рекурсия, поиск компонент,
топологические идеи, backtracking.
BFS: кратчайшие пути в невзвешенных графах,
обход по уровням, волновые алгоритмы.
8/10

9.

Сложность операций и типичные ошибки
Что нужно помнить на практике
Сложность
Стек
push
pop
peek
O(1)
O(1)
O(1)
Очередь
offer O(1)
poll O(1)
peek O(1)
Стек и очередь · Java
Для ArrayDeque это
амортизированная O(1) на
типовых операциях.
Правило выбора:
нужен самый свежий элемент ->
стек
нужен порядок поступления ->
очередь
Практика
Если нет особых требований по
потокобезопасности и
блокировкам, ArrayDeque хороший базовый выбор.
Частые ошибки
- путать LIFO и FIFO
- вызывать pop() или remove() без
проверки на пустоту
- использовать Stack и LinkedList
по привычке, не думая о Deque
- выбирать структуру по
названию, а не по поведению
алгоритма
9/10

10.

Итог и мини-практика
После этой темы студент должен уверенно различать стек, очередь и Deque
Главное запомнить
Мини-практика
- стек = LIFO
- очередь = FIFO
- в Java чаще всего используют
ArrayDeque
- выбор структуры меняет
поведение алгоритма
1. Реализовать стек строк.
2. Проверить корректность скобок: (), [], {}.
3. Написать очередь задач.
4. Реализовать BFS для графа городов.
5. Развернуть строку с помощью стека.
Шпаргалка
Контрольный вопрос
Deque<Integer> stack = new
ArrayDeque<>();
Queue<Integer> queue = new
ArrayDeque<>();
Какая структура данных нужна, если важен порядок
поступления событий?
Стек и очередь · Java
Ответ: очередь.
10/10