Проверка палиндрома¶

Интересная задача, которая может быть легко решена с использованием структуры данных “дек” - это классическая задача палиндрома. Палиндромом называют строку, которая одинаково читается справа налево и слева направо. Например, radar, toot или madam. Мы хотим создать алгоритм, принимающий на вход строку символов и проверяющий, является ли она палиндромом.

Для решения данной задачи используем дек в качестве хранилища строковых символов. Мы будем обрабатывать строку слева направо и добавлять каждый её элемент в хвост дека. В этот момент он будет работать очень схоже с обычной очередью. Однако, теперь мы можем использовать дуальную функциональность дека. Его голова будет хранить первый символ строки, а хвост - последний (see рисунок 2).

Рисунок 2: Дек

Поскольку мы способны удалять оба элемента сразу, то можно производить сравнение и продолжать только в случае, если символы совпадают. Если соответствие первого и последнего элементов будет сохраняться, то в конечном итоге мы придём или к отсутствию символов, или останемся с деком размером 1 - в зависимости от того, была ли длина исходной строки чётным или нечётным числом. Но обоих случаях входная последовательность будет палиндромом. Полностью функция проверки представлена в ActiveCode 1.