数据结构：链栈

实验目标：

提示

（1）将e入栈

（2）用e返回出栈元素

（3）返回栈顶元素

（4）清空栈，变为空栈

（5）遍历栈元素（从栈顶到栈底）

（6）回文是指正读反读均相同的字符序列，如"acdca"、"dceecd"均是回文，但"book"不是回文。试写一个算法判定输入的字符串是否为回文，并将结果输出，例如："acdca"是回文

提示

这里发现，链栈可以直接用链表修改获得，甚至链表的头插法就是天然的入栈过程

---

实验代码

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

#define TRUE         1
#define FALSE        0
#define OK           1
#define ERROR        0
#define INFEASIBLE  -1
#define OVERFLOW    -2

typedef int Status;
typedef int SElemType;

typedef struct StackNode{//定义
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStack;

Status InitStack(LinkStack &S){//初始化栈
    S=(struct StackNode*)malloc(sizeof(struct StackNode));//分配空间以创建链表
    if(!S->data) return FALSE;

    S->data=0;
    S->next=NULL;
    return OK;
}

Status Push(LinkStack &S,char e){//入栈，这里发现链表的头插法就是一个天然的入栈过程，直接拿过来用
    struct StackNode* newNode=(struct StackNode*)malloc(sizeof(struct StackNode));
    if(!newNode->data) return FALSE;

    newNode->data=e;
    newNode->next=S->next;
    S->next=newNode;
}

Status Pop(LinkStack &S,SElemType &e){//出栈
    struct StackNode* posNode=S->next;
    if(posNode==NULL) return FALSE;//判断栈是否为空

    S->next=posNode->next;
    posNode=S->next;
    e=posNode->data;
    return e;
}

Status GetTop(LinkStack &S,SElemType &e){//获得栈顶元素
    struct StackNode* posNode=S->next;
    if(posNode==NULL) return FALSE;//判断栈是否为空

    e=posNode->data;
    cout<<e<<endl;
    return e;
}

void Clear(LinkStack &S){//清空栈
    struct StackNode* p=S->next;
    struct StackNode* q;
    if(p==NULL) cout<<"该链表为空，不需删除！"<<endl;//判断栈是否为空

    while(p != NULL){//逐一删除
        q=p->next;
        free(p);
        p=q;
    }
    S->next==NULL;
    cout<<"清空成功！"<<endl;
}

void Traverse(LinkStack &S){//遍历栈
    struct StackNode* pmove=S->next;
    if(pmove==NULL) cout<<"遍历失败该链表为空"<<endl;

    while(pmove){
        int x;
        x=pmove->data;
        cout<<x<<' ';
        pmove=pmove->next;
    }
    cout<<endl;
}

void HuiWen(){//测试回文序列
    LinkStack S;
    InitStack(S);

    int n;
    char WenZi;
    int flag=1;

    cout<<"请输入本次要输入的字符的个数：";
    cin>>n;
    cout<<endl<<"请输入要检查的数列：";
    for(int i=1;i<=n;i++){//入栈
        cin>>WenZi;
        Push(S,WenZi);
    }
    cout<<endl;

    for(int i=1;i<=n;i++){//判断操作
        struct StackNode* p=S->next;
        struct StackNode* q=S->next;

        for(int j=1;j<n-i+1;j++){
            p=p->next;
        }

        if(p->data!=q->data){
            cout<<"不是回文数列！"<<endl;
            flag=0;
            break;
        }

        q=q->next;
    }

    if(flag==1) cout<<"是回文数列!"<<endl;
    
}

int main()
{
    LinkStack S;
    int e;

    while(1){
		cout<<endl;
		cout<<"**1,初始化栈"<<endl;
		cout<<"**2,将元素e入栈"<<endl;
	    cout<<"**3,出栈，用e返回出栈元素"<<endl;
	    cout<<"**4,返回栈顶元素"<<endl;
		cout<<"**5,清空栈"<<endl;
		cout<<"**6,遍历栈元素（从栈底到栈顶）"<<endl;
        cout<<"**7,测试回文列"<<endl;
		cout<<"**0,退出系统"<<endl;

		int choice;
		cout<<"请输入要进行的操作：";
		cin>>choice;
		cout<<endl;

		switch(choice){
			case 1:InitStack(S);break;
			case 2:{
				int n;
				cout<<"请输入本次入栈的元素个数：";
				cin>>n;

				cout<<endl<<"请输入要插入的元素：";
				for(int i=1;i<=n;i++){
					cin>>e;
					Push(S,e);
				}
				cout<<"入栈成功！";
				cout<<endl<<"本次插入的元素如下：";
				Traverse(S);
				break;
			}
			case 3:{
				int n;
				cout<<"请输入本次出栈的元素个数：";
				cin>>n;

				cout<<endl;
				for(int i=n;i>0;i--) Pop(S,e);
				cout<<"出栈成功！"<<endl;
				cout<<"剩下的元素为：";
				Traverse(S);
				break;
			}
			case 4:GetTop(S,e);break;
			case 5:Clear(S);break;
			case 6:Traverse(S);break;
			case 7:HuiWen();break;
			case 0:exit(0);

		}
	}
    system("pause");
    return 0;
}