判断字符串是否为回文----使用栈和队列

前言

回文自然都懂，不多说

本文基于：

队列—先进先出

栈 —后入先出

这一结构来实现判断

算法分析

将字符串分别存储到栈和队列中之后分别输出判断是否相等

代码实现

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

#include"Seqstack.h"
#include"Seqqueue.h"
//相应的实现栈和队列的头文件


int huiwen_fun(char str[])
{
	int n=strlen(str);
	PSeqStack S;
	PSeqQueue Q;
	S=Init_SeqStack();
	Q=Init_SeqQueue();
	if(!S)
	{
		printf("栈初始化错误！");
		return 0;
	}//创建栈
	if(!Q)
	{
		printf("队列初始化错误！");
		return 0;
	}//创建队列
	int i;
	for(i=0;i<n;i++)    //入栈（队列）
	{
		In_SeqQueue(Q,str[i]);
		Push_SeqStack(S,str[i]);
	}
	DataType q,s;
	for(i=0;i<n;i++)//出栈（队列）
	{
		Pop_SeqStack(S,&s);
		Out_SeqQueue(Q,&q);   
		if(s!=q)  //判断是否相等
		{	printf("%s不是回文",str);
			return 0;
		}
	}
	printf("%s是回文",str);	
	Destroy_SeqQueue(&Q);
	Destroy_Seqstack(&S); 
	return 0;
}

//主函数

int main()
{
	char str[100];
	printf("输入字符串：");
	scanf("%s",str);
	huiwen_fun(str);
	return 0;
}

栈的头文件

//栈的头文件  ---  顺序存储
#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 100

//typedef int DataType;
//typedef struct
//{
//	int x, y, d;		//横纵坐标及方向
//}DataType;

//typedef int DataType;
typedef char DataType;


typedef struct
{
	DataType data[MAXSIZE];
	int top;
}SeqStack,*PSeqStack;


//初始化栈
PSeqStack Init_SeqStack(void)
{
	/*创建一个顺序栈，入口参数无，返回指向顺序栈的指针*/
	PSeqStack S;
	S = (PSeqStack)malloc(sizeof(SeqStack));
	if (S)
		S->top = -1;
	return S;
}

//判断栈空
int Empty_SeqStack(PSeqStack S)
{
	/*判断栈是否为空  入口参数：顺序栈 返回值1为空 0非空*/
	if (S->top == -1)

		return 1;
	else
		return 0;
}

//入栈
int Push_SeqStack(PSeqStack S, DataType x)
{
	/*在栈顶插入一个新元素，入口参数：顺序栈 返回1表示成功   0表示失败*/
	if (S->top == MAXSIZE - 1)
		return 0;
	else
	{
		S->top++;
		S->data[S->top] = x;
		return 1;
	}
}

//出栈
int Pop_SeqStack(PSeqStack s, DataType* x)
{
	/*删除栈顶元素 并保存在*x中   入口参数 顺序栈 返回值 1表示成功  0表示失败*/
	if (Empty_SeqStack(s))
		return 0;				//栈空不能出栈
	else {
		*x = s->data[s->top];
		s->top--;
		return 1;
	}
}

//取栈顶元素
int GetTop_SeqStack(PSeqStack s, DataType *x)
{
	/*取出栈顶元素  入口参数:顺序栈 返回值 1表示成功  0表示失败*/
	if (Empty_SeqStack(s))
		return 0;
	else
		*x = s->data[s->top];
	return 1;
}

//销毁栈
void Destroy_Seqstack(PSeqStack* s)
{
	/*入口参数：要销毁的顺序栈指针地址  无返回值*/
	if (*s)
		free(*s);
	*s = NULL;
	return;
}

队列的头文件

#pragma once
/*队列的顺序存储  采用头尾相连循环结构*/
/*入队  Q->rear = (Q->rear+1)%MAXSIZE */
/*出队  Q->front =(Q->front+1)%MAXSIZE */

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

//typedef int DataType;
typedef char DataType;

#define MAXSIZE 100 /*队列最大容量*/

/*定义队列类型*/
typedef struct
{
	DataType data[MAXSIZE]; /*队列存储空间*/
	int front, rear;   /*队头和队尾指针*/
}SeqQueue,*PSeqQueue;

/*初始化队列*/
PSeqQueue Init_SeqQueue()
{
	PSeqQueue Q;
	Q = (PSeqQueue)malloc(sizeof(SeqQueue));
	if (Q)
	{
		Q->rear = 0;
		Q->front = 0;
	}
	return Q;
}

/*判断队列为空*/
int Empty_SeqQueue(PSeqQueue Q)
{
	/*入口参数 数顺序队列 
	  出口参数 1表示空  0表示非空 -1表示队列不存在 */
	if (Q && Q->front == Q->rear)
		return 1;
	else
		if (!Q)return -1;
		else return 0;
}

/*入队*/
int In_SeqQueue(PSeqQueue Q, DataType x)
{
	/*入口参数 顺序队列 入队元素 返回值 1表示成功 -1表示队满*/
	if ((Q->rear + 1) % MAXSIZE == Q->front)
	{
		printf("队满");
		return -1;
	}
	else
	{
		Q->rear = (Q->rear + 1) % MAXSIZE;
		Q->data[Q->rear] = x;
		return 1;
	}
}

/*出队*/
int Out_SeqQueue(PSeqQueue Q, DataType* x)
{
	/*入口参数  顺序队列 出对元素保存于*x中 返回-1表示队列为空 返回1表示出队成功*/
	if (Empty_SeqQueue(Q))
	{
		printf("队空");
		return -1;
	}
	else
	{
		Q->front = (Q->front + 1) % MAXSIZE;
		*x = Q->data[Q->front];
		return 1;
	}
}

/*读队头元素*/
int Front_SeqQueue(PSeqQueue Q, DataType* x)
{
	/*入口参数   顺序队列 元素取出存放地址 返回值1表示成功 -1表示队空*/
	if (Empty_SeqQueue(Q))
	{
		printf("队空");
		return -1;
	}
	else
	{
		*x = Q->data[(Q->front + 1) % MAXSIZE];    //循环队列队头无元素
		return 1;
	}
}

/*销毁队列*/
void Destroy_SeqQueue(PSeqQueue* Q)
{
	if (*Q)
		free(*Q);
	*Q = NULL;
	return;
}


/*在其余资料中也有将rear指针所指向的队列元素为空则 
 入队Q.data[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE
 出队亦然更改*/