3.18. Verificado de Palíndromos

Um problema interessante que pode ser facilmente resolvido usando a estrutura de dados deque (fila dupla) é o problema clássico do palíndromo. Um palíndromo é uma string que é lida da mesma forma do início para o fim e do fim para o início, por exemplo, radar, toot e madam são palídromos. Gostaríamos de construir um algoritmo para inserir se uma string é um palíndromo.

A solução para este problema usará um deque para armazenar os caracteres da string. Vamos processar a string da esquerda para a direita e inserir cada caractere no fim do deque. Neste ponto, o deque estará atuando agindo de maneira muito parecida com uma fila normal. No entanto, agora podemos fazer uso da a dupla funcionalidade do deque. O início da deque amazenará o primeiro caractere da string e o fim da deque manterá o último caractere (veja Figura 2).

../_images/palindromesetup.png

Figure 2: Uma Deque

Como podemos remover os ambos diretamente, podemos compará-los e continuar apenas se esses caracteres forem iguais. Se pudermos manter a correspondência entre os itens do início e do fim, ao final ficaremos sem caracteres na deque ou ficar com uma deque de tamanho 1, dependendo se o comprimento da string original era par ou ímpar. Em ambos os casos, a string deve ser um palíndromo. a função completa para verificação de palíndromos pode ser vista em ActiveCode 1.

Next Section - 3.19. Listas