1. Какие операции со стеком разрешены?
Push — добавление элемента на верхушку стека. Pop — удаление элемента с верхушки стека. Peek (или Top) — получение значения элемента на верхушке стека без удаления. IsEmpty — проверка, пуст ли стек. Size — получение количества элементов в стеке.
2. Какие ошибки могут возникнуть при использовании стека?
Переполнение стека — попытка добавить элемент в полный стек (если размер стека ограничен). Недостаточно элементов для извлечения — попытка удалить элемент из пустого стека.
3. Какие операции допускает очередь?
Enqueue — добавление элемента в конец очереди. Dequeue — удаление элемента с начала очереди. Front (или Peek) — получение значения первого элемента в очереди без удаления. IsEmpty — проверка, пуста ли очередь. Size — получение количества элементов в очереди.
4. Как построить очередь на основе массива с неизменяемым размером?
Для реализации очереди на основе массива с фиксированным размером можно использовать два индекса: один для обозначения начала очереди (front), другой для конца очереди (rear). При добавлении элемента в очередь (enqueue) индекс rear увеличивается, при удалении элемента (dequeue) увеличивается индекс front. Если очередь становится пустой, индексы возвращаются к началу массива, что позволяет эффективно использовать все доступные элементы.
5. Приведите примеры задач, в которых можно использовать очередь.
Обработка задач в многозадачных операционных системах — процессы обрабатываются по очереди. Очереди на кассах в супермаркетах — обслуживаются в порядке очереди. Алгоритмы поиска в ширину (BFS) — использование очереди для обхода графов. Буферизация данных — передача данных между производителем и потребителем с использованием очереди.
6. Что такое дек? Чем он отличается от стека и очереди? Какая из этих структур данных наиболее общая (может выполнять функции других)?
Дек — это структура данных, которая позволяет добавлять и удалять элементы с обоих концов (спереди и сзади). Он сочетает функции стека и очереди. Стек позволяет работать только с одним концом, а очередь — только с другим. Дек более универсален, так как может выполнять функции как очереди, так и стека.