数据结构使用链栈或列队判断回文

判断回文可以使用链栈或队列来实现。具体实现方法如下：

1.使用链栈实现回文判断

将字符串的前一半依次入栈，然后依次出栈并与字符串的后一半进行比较，如果全部相等，则为回文。

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

#define MAXSIZE 100

typedef struct Node {
    char data;
    struct Node* next;
} Node;

typedef struct Stack {
    Node* top;
} Stack;

Stack* initStack() {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->top = NULL;
    return stack;
}

void push(Stack* stack, char data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = stack->top;
    stack->top = node;
}

char pop(Stack* stack) {
    if (stack->top == NULL) {
        return '\0';
    }
    char data = stack->top->data;
    Node* temp = stack->top;
    stack->top = stack->top->next;
    free(temp);
    return data;
}

int isPalindrome(char* str) {
    int len = strlen(str);
    Stack* stack = initStack();
    for (int i = 0; i < len / 2; i++) {
        push(stack, str[i]);
    }
    for (int i = len / 2 + len % 2; i < len; i++) {
        if (pop(stack) != str[i]) {
            return 0;
        }
    }
    return 1;
}

int main() {
    char str[MAXSIZE];
    printf("请输入字符串：");
    scanf("%s", str);
    if (isPalindrome(str)) {
        printf("是回文\n");
    } else {
        printf("不是回文\n");
    }
    return 0;
}

2.使用队列实现回文判断

将字符串的前一半依次入队，然后依次出队并与字符串的后一半进行比较，如果全部相等，则为回文。

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

#define MAXSIZE 100

typedef struct Queue {
    char* data;
    int front;
    int rear;
} Queue;

Queue* initQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->data = (char*)malloc(sizeof(char) * MAXSIZE);
    queue->front = queue->rear = 0;
    return queue;
}

void enqueue(Queue* queue, char data) {
    queue->data[queue->rear] = data;
    queue->rear = (queue->rear + 1) % MAXSIZE;
}

char dequeue(Queue* queue) {
    if (queue->front == queue->rear) {
        return '\0';
    }
    char data = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAXSIZE;
    return data;
}

int isPalindrome(char* str) {
    int len = strlen(str);
    Queue* queue = initQueue();
    for (int i = 0; i < len / 2; i++) {
        enqueue(queue, str[i]);
    }
    for (int i = len / 2 + len % 2; i < len; i++) {
        if (dequeue(queue) != str[i]) {
            return 0;
        }
    }
    return 1;
}

int main() {
    char str[MAXSIZE];
    printf("请输入字符串：");
    scanf("%s", str);
    if (isPalindrome(str)) {
        printf("是回文\n");
    } else {
        printf("不是回文\n");
    }
    return 0;
}