3.18. Verificador de palíndromos¶
Un problema interesante que se puede resolver fácilmente usando la estructura de datos Cola Doble es el clásico problema de los palíndromos. Un palíndromo es una cadena que se lee igual hacia adelante y hacia atrás, por ejemplo, radar, oso y madam. Nos gustaría construir un algoritmo al cual se le introduzca una cadena de caracteres y compruebe si es un palíndromo.
La solución a este problema utilizará un cola doble para almacenar los caracteres de la cadena. Vamos a procesar la cadena de izquierda a derecha y a agregar cada carácter al final de la cola doble. En este punto, la cola doble estará actuando de forma muy parecida a una cola ordinaria. Sin embargo, ahora podemos hacer uso de la doble funcionalidad de la cola doble. El frente de la cola doble tendrá el primer carácter de la cadena y el final de la cola doble tendrá el último carácter (ver la Figura 2).
Figura 2: Una cola doble¶
Figura 2: Una cola doble
Ya que podemos eliminar ambos directamente, podemos compararlos y continuar solo si coinciden. Si podemos mantener la coincidencia de los ítems primero y último, eventualmente o nos quedaremos sin caracteres o nos quedará una cola doble de tamaño 1 dependiendo de si la longitud de la cadena original era par o impar. En ambos casos, la cadena debe ser un palíndromo. La función completa para la verificación de palíndromos se muestra en el ActiveCode 1.