#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

struct NodoPila {
    char caracter;
    struct NodoPila* siguiente;
};

struct NodoCola {
    char caracter;
    struct NodoCola* siguiente;
};

void apilar(struct NodoPila** pila, char c) {
    struct NodoPila* nuevoNodo = (struct NodoPila*)malloc(sizeof(struct NodoPila));
    nuevoNodo->caracter = c;
    nuevoNodo->siguiente = *pila;
    *pila = nuevoNodo;
}

char desapilar(struct NodoPila** pila) {
    if (*pila == NULL) return '\0';
    struct NodoPila* temp = *pila;
    char c = temp->caracter;
    *pila = temp->siguiente;
    free(temp);
    return c;
}

void encolar(struct NodoCola** cola, char c) {
    struct NodoCola* nuevoNodo = (struct NodoCola*)malloc(sizeof(struct NodoCola));
    nuevoNodo->caracter = c;
    nuevoNodo->siguiente = NULL;

    if (*cola == NULL) {
        *cola = nuevoNodo;
    } else {
        struct NodoCola* temp = *cola;
        while (temp->siguiente != NULL) {
            temp = temp->siguiente;
        }
        temp->siguiente = nuevoNodo;
    }
}

char desencolar(struct NodoCola** cola) {
    if (*cola == NULL) return '\0';
    struct NodoCola* temp = *cola;
    char c = temp->caracter;
    *cola = temp->siguiente;
    free(temp);
    return c;
}

void eliminarSaltoDeLinea(char *cadena) {
    int i = 0;
    while (cadena[i] != '\0') {
        if (cadena[i] == '\n') {
            cadena[i] = '\0';
            break;
        }
        i++;
    }
}

int esPalindromo(char* frase) {
    struct NodoPila* pila = NULL;
    struct NodoCola* cola = NULL;

    int i = 0;
    while (frase[i] != '\0') {
        if (isalpha(frase[i])) {
            char c = tolower(frase[i]);
            apilar(&pila, c);
            encolar(&cola, c);
        }
        i++;
    }

    while (pila != NULL && cola != NULL) {
        char c1 = desapilar(&pila);
        char c2 = desencolar(&cola);
        if (c1 != c2) {
            while (pila != NULL) desapilar(&pila);
            while (cola != NULL) desencolar(&cola);
            return 0;
        }
    }

    return 1;
}

int main() {
    char frase[256];

    while (1) {
        printf("Introduce una frase (o '#' para terminar): ");
        fgets(frase, sizeof(frase), stdin);
        eliminarSaltoDeLinea(frase);

        if (strcmp(frase, "#") == 0) {
            break;
        }

        if (esPalindromo(frase)) {
            printf("La frase es un palindromo.\n");
        } else {
            printf("La frase NO es un palindromo.\n");
        }
    }

    return 0;
}