用类模板实现的队列和栈 + 判断回文

代码链接:https://paste.ubuntu.com/p/V3G95h5bG2/
`

#include<bits/stdc++.h>
using namespace std;

/*
    用类模板使得代码变得简单 
*/

const int add_length=10;
const int init_length=100;
template<typename ElemType>`
struct Qnode{
    Qnode * next;
    ElemType data;
};
template<typename ElemType>
struct MyQueue{
    Qnode<ElemType>* base;
    Qnode<ElemType>* top;
    int len;
    MyQueue(){
        len=0;
        base=new Qnode<ElemType>;
        base->next=NULL;
    }
    void push_back(ElemType x){
        len++;
        Qnode<ElemType>* temp=new Qnode<ElemType>;
        temp->data=x;
        temp->next=base->next;
        if(len==1) top=temp;
        base->next=temp;
    }

    bool empty()
    {
        return base==top;
    }

    void pop(){
        Qnode<ElemType>* temp=base;
        while(temp->next!=top) temp=temp->next;
        top=temp;
    }

    ElemType front(){
        return top->data;
    }

    int size(){
        return len;
    }
};

/*
    用类模板使得代码变得简单 
*/

template<typename ElemType>
struct MyStack{
    int length;
    int size;
    ElemType *base;
    ElemType *top;
    MyStack(){

        size=init_length;
        length=0;
        top=base=(ElemType*) malloc (size * sizeof(ElemType));
    }
    void push(ElemType x){
        ElemType *head;
        if(this->length==this->size)
        {
            head=(ElemType*) realloc(this->base,(this->size+add_length)*sizeof(ElemType));
            this->base=head;
            this->top=head+this->length;
            this->size+=add_length;
        }
        *(this->top++)=x;
        this->length++;
    }
    ElemType gettop(){
        if(this->top!=this->base) return *(this->top-1);
        else return -1;
    }
    ElemType pop(){
        if(top==base) return -1;
        this->top--;
        this->length--;
    }
    bool empty(){
        return this->length==0;
    }
};

void init()
{
    string s;
    cin>>s;
    int n=s.size();
    MyQueue<char> q;
    MyStack<char> st;
    for(int i=0;i<n/2;i++)
    {
        q.push_back(s[i]);
    }
    if(n%2==0)
    for(int i=n/2;i<n;i++)
    {
        st.push(s[i]);
    }else
    for(int i=n/2+1;i<n;i++)
    {
        st.push(s[i]);
    }   

    while(!st.empty())
    {
        cout<<st.gettop()<<" "<<q.front()<<endl;
        if(st.gettop()!=q.front()){
            cout<<"NO"<<endl;
            return;
        }
        st.pop();
        q.pop();
    }
    cout<<"YES"<<endl;
}

int main()
{
    /*MyQueue<int> Q;
    for(int i=1;i<=10;i++)
        Q.push_back(i);
    while(!Q.empty())
    {
        cout<<Q.front()<<" ";
        Q.pop();
    }*/
    init();

}

您可能还喜欢...

发表评论

电子邮件地址不会被公开。 必填项已用*标注