Перейти к содержанию

5.5   Упражнения

5.5.1   Вопросы для самопроверки

1.   Что первым извлекается из стека и очереди

Подготовьте пустой стек S и пустую очередь Q, а затем выполните с каждым из них один и тот же набор операций:

шаг 1: добавить A; шаг 2: добавить B; шаг 3: удалить один элемент и записать его; шаг 4: добавить C; шаг 5: удалять и записывать элементы, пока контейнер не опустеет.

Запишите порядок удаления элементов из S и Q. Объясните различие принципами «последним пришел — первым вышел» и «первым пришел — первым вышел».

Ответ

Порядок удаления из стека S: B, C, A. После добавления A, B первым извлекается последний добавленный элемент B; затем добавляется C, после чего извлекаются C, A. Это принцип «последним пришел — первым вышел».

Порядок удаления из очереди Q: A, B, C. После добавления A, B первым удаляется самый ранний элемент A; затем добавляется C, после чего удаляются B, C. Это принцип «первым пришел — первым вышел».

2.   Что происходит, когда хвост очереди проходит конец массива

Очередь реализована с помощью кольцевого массива длины 5 с индексами 0–4. Сейчас front = 3, size = 2, а элементы очереди A, B находятся по индексам 3 и 4 соответственно.

  1. По какому индексу нужно поместить C при операции «добавить C в очередь»? Чему после этого равно size?
  2. Затем из очереди удаляется один элемент. Какой именно? Чему равны новые значения front и size?
  3. Каков теперь логический порядок элементов от головы к хвосту очереди? Нужно ли при удалении сдвигать остальные элементы массива и почему?
Ответ

  1. Позиция нового элемента равна (front + size) % 5 = (3 + 2) % 5 = 0, поэтому C помещается по индексу 0. После добавления size = 3.

  2. Из очереди удаляется текущий первый элемент A. Новый индекс головы равен (3 + 1) % 5 = 4, поэтому front = 4, size = 2.

  3. Логический порядок находящихся в очереди элементов — B, C: B находится по индексу 4, а C — по индексу 0. При удалении достаточно изменить front и size. Благодаря остатку от деления индекс в кольцевом массиве возвращается к началу, поэтому сдвигать вперед все остальные элементы не нужно.

3.   Операции с обоих концов двусторонней очереди

Здесь push_first означает добавление в голову, push_last — добавление в хвост, pop_first — извлечение из головы, а pop_last — извлечение из хвоста.

С пустой двусторонней очередью deq последовательно выполняются операции:

  1. push_last(A)
  2. push_last(B)
  3. push_first(C)
  4. pop_last()
  5. push_last(D)
  6. pop_first()
  1. Какие элементы возвращают две операции извлечения?
  2. Какие элементы остаются после всех операций в порядке от головы к хвосту?
  3. Рассмотрите все 6 шагов. Можно ли выполнить их с обычной очередью, в которую разрешено добавлять только с хвоста, а удалять только с головы? Если нет, укажите недопустимые операции. Объясните также, может ли выполнить все шаги двусторонняя очередь и почему.
Ответ

После первых трех шагов двусторонняя очередь от головы к хвосту имеет вид [C, A, B].

  1. pop_last() возвращает B. После добавления D очередь имеет вид [C, A, D], а pop_first() возвращает C.

  2. В конце остаются [A, D].

  3. Обычная очередь, допускающая добавление с хвоста и удаление с головы, не может выполнить все операции: шаг 3 push_first(C) требует добавить элемент с головы, а шаг 4 pop_last() — удалить элемент с хвоста. Обе операции выходят за рамки обычной очереди. Двусторонняя очередь позволяет добавлять и удалять элементы с обоих концов, поэтому может выполнить все 6 шагов.

5.5.2   Задачи по программированию

1.   Проверка последовательности скобок

Дана строка s, содержащая только скобки трех видов: (), [], {}. С помощью стека определите, является ли последовательность правильной.

Правильная последовательность должна удовлетворять двум условиям: каждая закрывающая скобка соответствует по виду ближайшей еще не сопоставленной открывающей скобке, а после обхода не остается несопоставленных открывающих скобок. Верните логическое значение результата проверки.

Подсказки
  1. Можно создать отображение из закрывающей скобки в соответствующую открывающую
  2. Встретив закрывающую скобку, сначала проверьте, не пуст ли стек, а затем — совпадает ли его вершина
  3. После обхода стек также должен быть пуст

LeetCode

Оставляйте свои идеи, вопросы и предложения в комментариях