lesson-09-stack-queue

Урок 9. Стек и очередь

Цель

Познакомиться с двумя базовыми структурами данных, которые определяют порядок доступа к элементам: LIFO и FIFO.

Что это такое?

Стек (Stack) — работает по принципу LIFO (Last In, First Out). Последним пришёл — первым вышел. Как стопка тарелок.

Очередь (Queue) — работает по принципу FIFO (First In, First Out). Первым пришёл — первым вышел. Как очередь в магазине.

Основные операции

Операция	Стек	Очередь
Добавить	push(x)	push(x)
Удалить	pop() (верхний)	pop() (первый)
Посмотреть	top()	front() / back()
Проверить пустоту	empty()	empty()
Размер	size()	size()

1. Стек (std::stack)

#include <stack>

stack<int> s;
s.push(10);
s.push(20);
s.push(30); // верхний = 30

cout << s.top(); // 30
s.pop();         // удалили 30
cout << s.top(); // 20

2. Очередь (std::queue)

#include <queue>

queue<int> q;
q.push(10);
q.push(20);
q.push(30); // первый = 10, последний = 30

cout << q.front(); // 10
cout << q.back();  // 30
q.pop();           // удалили 10
cout << q.front(); // 20

3. Где применяется?

Стек:

• Проверка скобок в выражениях.
• Отмена действий (Ctrl+Z).
• Стек вызовов функций.

Очередь:

• Очередь задач (печать документов).
• Обработка сообщений.
• Потоки данных.

4. Как проверить скобки (идея)

1. Встретили ( → добавили в стек.
2. Встретили ) → проверили, есть ли ( в стеке (и удалили).
3. Если стек пуст, а встретили ) — ошибка.
4. В конце стек должен быть пуст.

Примеры

• stack_queue.cpp — все примеры из урока

Что дальше

Урок 10 — связные списки.