判断回文序列通过栈和队列实现（思路+代码）

66 阅读 0 评论 44 点赞

我是靠谱客的博主热情荷花，最近开发中收集的这篇文章主要介绍判断回文序列通过栈和队列实现（思路+代码），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述

回文序列判断：输入一个字符串，判断它是否是回文序列(即左右对称，如abccba或abcdcba)

解决方法

利用栈先进后出、队列先进先出的特点，将字符串前半部分入栈，后半部分入队列（若字符串有奇数个字符，则最中间的字符不加入栈和队列）；分别逐个取出栈顶、队首的元素，即为字符串中两个对称的字符，一一对比，若不同则说明不是回文串；直到最后，若栈与队列均为空，说明完全对称，字符串为回文序列。

代码实现

/*栈和队列实现 回文序列判断*/
#include <iostream>
#include <queue>
#include <stack>
#include <string.h>
using namespace std;
int main()
{
    char chsq[255];
    cout<<"请输入一个长度不大于255的字符序列"<<endl;
    cin>>chsq;
    cout<<"字符串为："<<chsq<<endl;
    stack <char> s;
    queue <char> q;
    for(int i=0; i<strlen(chsq); i++)
    {
        if(strlen(chsq)%2==0&&i<strlen(chsq)/2)
            s.push(chsq[i]);//前二分之一入栈
        if(strlen(chsq)%2==0&&i>=strlen(chsq)/2)
            q.push(chsq[i]);//后二分之一入队
        if(strlen(chsq)%2!=0&&i<(strlen(chsq)-1)/2)
            s.push(chsq[i]);//设2m+1=strlen(chsq),前m个一入栈
        if(strlen(chsq)%2!=0&&i>(strlen(chsq)-1)/2)
            q.push(chsq[i]);//设2m+1=strlen(chsq),后m个入队
    }
    for(; !s.empty(); )
    {
        if (s.top() == q.front())
        {
            s.pop();
            q.pop();
        }
        else break;
    }
    if(s.empty()&&q.empty())
        cout<<"是回文串"<<endl;
    else
        cout<<"不是回文串"<<endl;
    return 0;
}