回文(字符)

//2022.9.28 回文的实现(字符)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//定义单链表节点类型
typedef struct qlink {
	int data;  //数据域
	struct qlink* next;//指针域
}qlink;


//定义链队列的类型
typedef struct linkqueue {
	qlink* front;//队头指针
	qlink* rear;//队尾指针
}linkq;

linkq q;//定义一个链队列

//初始化链队列
void initqlink() {
	q.front = (qlink*)malloc(sizeof(qlink));
	if (!q.front)
		exit(0);
	q.front->next = NULL;
	q.rear = q.front;//空队列
}

//入队(插入)
void enqlink(char e) {
	qlink* p;
	p = (qlink*)malloc(sizeof(qlink));
	if (!p)
		exit(0);
	p->data = e;
	p->next = NULL;
	q.rear->next = p;//连接作用
	q.rear = p;//修改队尾指针
}

//出队(删除)
char deqlink() {
	qlink* p;
	char x;
	if (q.rear == q.front) {
		printf("空队列,不进行删除\n");
		exit(0);
	}
	p = q.front->next;
	x = p->data;
	q.front->next = p->next;
	if (p == q.rear)//如果队尾指针没有,空队列
		q.rear = q.front;
	free(p);
	return x;

}
#define N 20

//定义顺序栈的类型
typedef struct sqstack {
	int* base;  //栈底指针
	int* top;  //栈顶指针
	int stacksize; //存储空间大小
}sqs;

sqs s; 	//定义一个顺序栈

//初始化
void initstack() {
	s.base = (int*)malloc(N * sizeof(int));
	if (!s.base)
		exit(0);
	s.top = s.base;  	//空栈
	s.stacksize = N;
}

//入栈(插入元素)
void push(char e) {
	if (s.top - s.base >= s.stacksize) {
		printf("栈满\n");
		exit(0);
		/*s.base=(int *)realloc(s.base,(N+M)*sizeof(int))
		if(!s.base) exit(0);
		s.top=s.base+s.stacksize;
		s.stacksize+=M;
		*/
	}
	*s.top = e;	//插入
	s.top++;	//修改栈顶指针
}

//出栈(删除)
char pop() {
	char e;
	if (s.top == s.base) {
		printf("空栈\n");
		exit(0);
	}
	s.top--;//修改栈顶指针
	e = *s.top;//赋值
	return e;
}
//判断是否为回文
void judge() {
	char e;
	int n;
	initstack();
	initqlink();
	printf("请输入第一个字符串长度和元素:");//直接输入不要有空格
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		e = getchar();
		push(e);
		enqlink(e);
	}
	printf("是否为回文:");
	while (s.top != s.base&& q.rear != q.front)//判断是否为回文,因为长度都相同所以要存在都存在,要不存在都不存在
	{
		if (pop() != deqlink())
			printf("NO");
		else
		{
			printf("YES");
			break;
		}
	}
	
}
void main() {
	judge();
}