栈和队列的应用之回文数判断

今天药忘吃喽~ 2023-10-09 21:36 9阅读 0赞

### 题目： ###

采用栈和队列的方法检测并输出一个单词是否为回文。

#### 代码： ####

#include<stdio.h>
    #include<malloc.h>
    #define SIZE 20  
    using namespace std;
     
    
    //1.定义顺序栈
    typedef struct{
    	char c[SIZE];//记录字符
    	int top;//栈指针
    }Stack;
     
    //初始化栈
    void initStack(Stack &S){
    	S.top=-1;//初始化指针
    }
     
    //入栈
    void push(Stack &S,char c){
    	S.top++;//指针上移
    	S.c[S.top]=c;//存储数据
    } 
     
    //出栈
    void pop(Stack &S,char &c){
    	c=S.c[S.top];
    	S.top--;//指针下移 
    } 
     
    //2.定义循环队列
    typedef struct{
    	char *base;
    	int front;
    	int rear; 
    } Queue;
     
    //初始化队列
    void initQueue(Queue &Q){
    	Q.base=(char *)malloc(SIZE*sizeof(char));//动态分配队列存储空间 
    	Q.front=Q.rear=0;//空队列
    }
     
    //入队列
    void inQueue(Queue &Q,char c){
    	Q.base[Q.rear]=c;//存储数据
    	Q.rear=(Q.rear+1)%SIZE;//队尾指针后移
    }
     
    //出队列
    void outQueue(Queue &Q,char &c){
    	c=Q.base[Q.front];
    	Q.front=(Q.front+1)%SIZE;//队头指针后移
    }
     
    //3.偶数个字符比较 
    bool evenNumbers(Stack &S,Queue &Q,char &c){
    	while(emptyStack(S)&&emptyQueue(Q)){
    		if(S.c[S.top]!=Q.base[Q.front]){
    			printf("不是回文！\n");
    			return false;//返回false，结束循环 
    		}else{
    			pop(S,c);//出栈
    			outQueue(Q,c);//出队列
    		}
    	}
    	return true;
    }
     
    //主函数
    int main(){
    	Stack S;
    	initStack(S);
    	//定义、初始化循环队列 
    	Queue Q; 
    	initQueue(Q);
    	char c;
    	int count=0;
    	printf("请输入单词,长度小于20: ");
    	while((c=getchar())!='\n') { //循环读取字符并判断类型，以末尾换行符’\n’结束
    		push(S,c);//入顺序栈
    		inQueue(Q,c);//入队列 
    		count++;
    	}
    	if(count>2) { 
    		bool yes;  
    		if(count%2==0){ 
    			yes=evenNumbers(S,Q,c);
    		}else{  
    			yes=oddNumber(S,Q,c,count);
    		}
    		if(yes){printf("是回文单词！\n");}
    	}else{
    		printf("***单词字符个数少于3个无法判断是否为 回文***\n");
    	}
    	return 0;
    }

#### 效果图： ####

![cf5bfc1598344edba76eca2c3e053c29.png][]

### 思考： ###

中文回文如何判断呢？废话不多说，直接上代码：

#### 代码： ####

#include <iostream>
    #include <string.h>
    using namespace std;
    struct Stack{
        char data[100];
        int top;
    };
    
    int Test(Stack L,int lens,string a){
        int n;
        int x = lens/2;
        if(x%2 == 1){
            for(int i=0;i<lens/2-1;i++){
                L.data[L.top] = a[i];
                L.top++;
            }
        }else{
            for(int i=0;i<lens/2;i++){
                L.data[L.top] = a[i];
                L.top++;
            }
        }
        return 1;
    }
    
    int main(int argc, char **argv) {
        printf("请输入中文语句：\n");
        char str[100];
        gets(str);
        int lens = strlen(str);
        Stack L;
        L.top = 0;
        if(Test(L,lens,str)){
            printf("%s 是回文",str);
        }else{
            printf("%s 不是回文",str);
        }
        return 0;
    }

#### 效果图： ####

![21da8cfca38b4feb9ee16bd40f638c63.png][]

### 提高篇： ###

采用栈和队列方法编程实现统计一篇文档中的所有出现的回文单词。（这里小编建议采用文件的形式读入）

#### 代码： ####

#include <cstdlib>
    #include <cstring>
    #include <cstdio>
    #include <iostream>
    
    //队列
    typedef char QElemType;
    typedef struct {
        QElemType *base;    //指向动态分配的数组中的元素
        int front;
        int rear;
    }SqQueue;
    
    //栈
    #define MaxSize 200
    typedef struct {
        char data[MaxSize];
        int top;
    }Stack;
    
    //队列
    void InitQueue(SqQueue &Q){
        //构造一个空队列Q
        Q.base = (QElemType *)malloc(sizeof(QElemType)*MaxSize); 
        if(!Q.base) exit(1);   //验证，Q不为空，返回1
        Q.front = Q.rear = 0;
    }
    
    void EnQueue(SqQueue &Q, QElemType e){
        //插入的元素e为Q的新的队尾元素
        if((Q.rear+1) % MaxSize == Q.front) exit(1);
        Q.base[Q.rear] = e;
        Q.rear = (Q.rear + 1) % MaxSize;
    }
    
    int DeQueue(SqQueue &Q, char &i) {
        //若队列不空，则删除Q的队头元素,并用i接收队头元素
        if(Q.front == Q.rear)
            exit(1);
        i = Q.base[Q.front];
        Q.front = (Q.front+1) % MaxSize;
    }
    
    //栈
    void InitStack(Stack &stack){
        stack.top = -1;
    }
    
    int push(Stack &S, char x) /*将x置入S栈新栈顶*/
    {
        if(S.top == MaxSize -1)
            return false;
        else{
            S.top++;
            S.data[S.top]=x;
            return true;
        }
    }
    
    int pop(Stack &S, char &x)  /*将栈S的栈顶元素弹出，放到x中*/
    {
        if(S.top==-1)
            return false;
        else{
            x = S.data[S.top];
            S.top--;
            return true;
        }
    }
    
    int compare(char a, char b){
        if (a == b) return 0;
        else return 1;
    }

#### 效果图： ####

![470f22240c3c4c60870857d4470551aa.png][]

**有问题也可以和小编一起交流！**

[cf5bfc1598344edba76eca2c3e053c29.png]: https://img-blog.csdnimg.cn/cf5bfc1598344edba76eca2c3e053c29.png
[21da8cfca38b4feb9ee16bd40f638c63.png]: https://img-blog.csdnimg.cn/21da8cfca38b4feb9ee16bd40f638c63.png
[470f22240c3c4c60870857d4470551aa.png]: https://img-blog.csdnimg.cn/470f22240c3c4c60870857d4470551aa.png