Question

Você pode dar um exemplo de um algoritmo que verifica se um número é um palíndromo usando pilha?

Answer 1

Uma possível solução é mostrada no código abaixo em C++. Ele utiliza a classe padrão stack da STL:

http://www.cplusplus.com/reference/stack/stack/

#include <iostream>
#include <sstream>
#include <string>
#include <stack>

using namespace std;

string convertNumToString(const int number) {
    ostringstream os;

    os << number;

    return os.str();
}

int convertStringToNum(const string numberAsString) {
    istringstream buffer(numberAsString);

    int value;

    buffer >> value;

    return value;
}

bool palindromo(int number) {

    string numberAsString = convertNumToString(number);

    stack<int> st;

    unsigned int i = 0, totalOfDigits = numberAsString.size();

    while (i < totalOfDigits) {
        int digit = convertStringToNum(numberAsString.substr(i,1));

        if (i < totalOfDigits/2) {
            st.push(digit);
        }
        else if ((totalOfDigits%2 == 0) || ((totalOfDigits%2 == 1) && (i > totalOfDigits/2))) {
            if (st.top() != digit) {
                return false;
            }
            st.pop();
        }
        i++;
    }

    return true;
}

int main(int argc, char* argv[])
{
    // 1) Use uma pilha para reverter uma sequencia de
    // numeros e testar se um determinado nuumero eh um palindromo.

    cout << "1001: Palindromo? " << palindromo(1001) << endl;

    cout << "10101: Palindromo? " << palindromo(10101) << endl;

    cout << "123: Palindromo? " << palindromo(123) << endl;
}

Answer 2

A solução abaixo, em Python, utiliza as estruturas de fila e de pilha, com polimorfismo referente ao método para retirada de elemento da estrutura. No loop principal, os elementos da pilha e da fila são comparados para verificar se o número é um palíndromo.

class Lista:
    def __init__(self):           # genérico
        self.vetor=[]
    def adiciona(self,element):   # genérico
        self.vetor.append(element)

class Pilha(Lista):   
    def retira(self):     
        return self.vetor.pop()   # retira o último

class Fila(Lista):    
    def retira(self):
        return self.vetor.pop(0)  # retira o primeiro

def testePalindromo(numero):
    strTeste = str(numero)
    nMetadeDigitos = int(len(strTeste)/2)

    myStack=Pilha()   # Empilha a primeira parte (left)
    for numero in strTeste[:nMetadeDigitos]:
        myStack.adiciona(numero)    

    myQueue=Fila()    # Enfileira a segunda parte (right)
    for numero in strTeste[-nMetadeDigitos:]:
        myQueue.adiciona(numero)

    # Compara a pilha com a fila
    i,lEhPalindromo=1,True    
    while(lEhPalindromo and i <= nMetadeDigitos):
        if (myStack.retira() != myQueue.retira()):
            lEhPalindromo=False
        else:
            i += 1

    return lEhPalindromo    

if __name__ == '__main__':

    print testePalindromo(123454321) # True
    print testePalindromo( 765567)   # True
    print testePalindromo(1765567)   # False

Comments

Olá! Segue sugestão de melhoria em seu método para testar se é palíndromo. Você não precisa colocar os número na fila, para depois comparar com os a pilha. A ideia é exatamente a mesma do que você já fez, mas você vai desempilhando e comparando. Se for diferente, seu método já retorna falso, pois sabe que não é palíndromo. Enfim, é só uma sugestão de melhoria para seu código.


def testePalindromo(numero):
    strTeste = str(numero)
    nMetadeDigitos = int(len(strTeste)/2)

    myStack=Pilha()   # Empilha a primeira parte (left)
    for numero in strTeste[:nMetadeDigitos]:
        myStack.adiciona(numero)    

    for numero in strTeste[-nMetadeDigitos:]:
        if (myStack.retira() != numero):
            return False

    return True

---

Saulo, não ficou claro no meu comentário, mas a ideia era mesmo adicionar o conceito de fila ao problema, já que você bem havia respondido a questão original, com o uso de pilha, conforme proposto.  Obrigado. Paulo