Двусторонняя очередь (deque) — это структура данных, позволяющая добавлять и удалять элементы с обоих концов очереди с одинаковой эффективностью. В Python deque реализуется в модуле collections. В этом примере мы рассмотрим, как использовать deque для проверки, является ли слово палиндромом.
Что такое палиндром?
Палиндром — это слово или фраза, которые читаются одинаково слева направо и справа налево, игнорируя пробелы, регистр и знаки препинания. Примеры палиндромов: "deed", "noon", "level".
Проверка на палиндром с использованием deque
Мы будем использовать двустороннюю очередь для проверки, является ли слово палиндромом. Это удобно, так как deque позволяет эффективно удалять элементы как с начала, так и с конца.
Реализация функции check_palindrome
- Импорт deque:
Импортируем deque из модуля collections. - Создание очереди:
Создаем объект deque из переданного слова. Каждый символ слова становится элементом очереди. - Цикл проверки:
Запускаем цикл, который работает до тех пор, пока длина очереди больше одного. Тем самым мы страхуемся, на случай палиндрома из нечетного количества букв (например, "наган").
Внутри цикла удаляем и сравниваем первый и последний элементы очереди, приведенные к нижнему регистру.
Если элементы не равны, выводим сообщение, что слово не является палиндромом, и завершаем выполнение функции.
Если все пары символов совпадают, значит, слово — палиндром.
Тестируем
Пояснение к коду
- Импорт и создание deque:
Мы импортируем deque и создаем очередь dq_word из символов переданного слова. - Цикл проверки:
popleft() удаляет и возвращает первый элемент очереди.
pop() удаляет и возвращает последний элемент очереди.
Оба элемента приводятся к нижнему регистру с помощью метода lower(), чтобы игнорировать регистр символов при сравнении. - Проверка совпадений:
Если в какой-то момент символы не совпадают, функция выводит сообщение о том, что слово не является палиндромом, и завершает выполнение.
Если все символы совпадают, выводится сообщение о том, что слово является палиндромом.
Вывод
Использование deque для проверки палиндромов позволяет эффективно работать с символами с обоих концов строки. Это решение является оптимальным по сравнению с использованием стандартного списка, так как операции добавления и удаления элементов с обоих концов в deque выполняются за постоянное время O(1). Такая реализация удобна и проста в понимании, а также демонстрирует один из вариантов использования двусторонней очереди в реальных задачах.
Если вы интересуетесь программированием, то напоминаю о нашем курсе по основам программирования Python [START].
В нем много анимации, примеров и разборов домашних заданий. Присоединяйтесь! Ссылка: