【数据结构】判断回文序列 自定义栈和队列实现（思路+代码）

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

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

本文使用自定义的栈和队列实现

使用C++自带的栈和队列实现 请见博客--> 判断回文序列 通过栈和队列实现（思路+代码）

#include 
#include 
using namespace std;
typedef struct SNode{
    char data;
    SNode *next;
}SNode,*linkStack;
typedef struct QNode {
    char data;
    struct QNode *next;
}QNode,*QueuePtr;//结点
typedef struct linkQueue {
    QNode* pfront;//头指针
    QNode* prear;//尾指针
}linkQueue;


void InitStack(linkStack &S)
{
    //初始化---建立头结点
    S=(SNode*)malloc(sizeof(SNode));
    if(!S)
    {
        cout<<"初始化分配内存失败！";
        return;
    }
    S->next=NULL;
}

void Push(linkStack &S,char e)
{
    //建立结点
    SNode* p=(SNode*)malloc(sizeof(SNode));
    p->data=e;
    //入栈---链表头插法插入结点
    p->next=S->next;
    S->next=p;
}

char Pop(linkStack &S)
{
    char e;
    //判断栈是否为空 栈空则不进行出栈
    if(S->next==NULL) return ' ';
    //保存出栈元素数据
    SNode* p=S->next;//出栈元素
    e=p->data;
    //出栈
    S->next=p->next;
    free(p);
    return e;
}

bool Empty(linkStack S)
{
    if(S->next==NULL) return true;
    else return false;
}

char Top(linkStack S)
{
    return S->next->data;
}

void StackTraverse(linkStack S)//以visit方法访问链表每个结点
{
    cout<<"栈：";
    SNode *p=S->next;
    while(p)
    {
        cout<data<<" ";
        p=p->next;
    }
    cout<next=NULL;
}

void QPush(linkQueue &Q,char e)
{
    //创建新结点并赋值
    QNode* p=(QNode*)malloc(sizeof(QNode));
    if(!p)
    {
        cout<<"入队分配内存失败！n";
        return;
    }
    p->data=e;
    p->next=NULL;
    //入队---队尾入队
    Q.prear->next=p;
    Q.prear=p;//尾指针移到最后
}

char QPop(linkQueue &Q)
{
    char e;
    //判断队列是否为空 为空则不进行出队
    if(Q.pfront==Q.prear) return ' ';
    //找到出队结点 即队首第一个结点
    QNode* p=Q.pfront->next;
    e=p->data;
    //出队---队首元素出队
    Q.pfront->next=p->next;
    //Q.prear==p此时为队列仅有一个元素，出队后队列为空
    //将Q.prear置为Q.prear=Q.pfront 否则Q.prear指向p,free后变为野指针
    if(Q.prear==p) Q.prear=Q.pfront;
    free(p);
    return e;
}

bool QEmpty(linkQueue Q)
{
    if(Q.pfront==Q.prear) return true;
    else return false;
}

char QTop(linkQueue Q)
{
    return Q.pfront->next->data;
}

void QueueTraverse(linkQueue Q)//以visit方法访问链表每个结点
{
    cout<<"队列：";
    QNode *p=Q.pfront->next;
    while(p)
    {
        cout<data<<" ";
        p=p->next;
    }
    cout<>chsq;
    cout<<"字符串为："< s;
//    queue  q;
    for(int i=0; i=strlen(chsq)/2)
            QPush(q,chsq[i]);//后二分之一入队
        if(strlen(chsq)%2!=0&&i<(strlen(chsq)-1)/2)
            Push(s,chsq[i]);//设2m+1=strlen(chsq),前m个一入栈
        if(strlen(chsq)%2!=0&&i>(strlen(chsq)-1)/2)
            QPush(q,chsq[i]);//设2m+1=strlen(chsq),后m个入队
    }
    StackTraverse(s);
    QueueTraverse(q);
    for(; !Empty(s); )
    {
        if (Top(s) == QTop(q))
        {
            Pop(s);
            QPop(q);
        }
        else break;
    }
    if(Empty(s)&&QEmpty(q))
        cout<<"是回文串"<