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

101 阅读 0 评论 67 点赞

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

问题描述

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

解决方法

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

代码实现

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*栈和队列实现 回文序列判断*/
#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;
}