//首先是栈的模板
#define Maxsize 100
#define ElemType int

typedef struct{
    ElemType data[Maxsize];
    int top;
}Stack;

bool InitStack(Stack& s){
    s.top = 0;//初始化top指针指向栈顶的下一个元素，也可以设为-1那样的话就是指向栈顶元素了
    return true;
}

bool push(Stack & s,ElemType x){
    if(s.top==Maxsize) return false;
    s.data[s.top++]= x;
    return true;
}

#define ElemType int

typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

bool InitLinkStack()

03.栈的初态和终态均为空，以I和0分别表示入栈和出栈，则出入栈的操作序列可表示为由I 和O组成的序列，可以操作的序列称为合法序列，否则称为非法序列。
1)下面所示的序列中哪些是合法的?
A. IOIIOIOO
B. IOOIOIIO
C. IIIOIOIO
D.IHIOOI00
2)通过对1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false (假定被判定的操作序列已存入一维数组中)。

//题目意思就是看哪些存取序列会发生栈下溢的情况，就是栈空了还要出栈。
//所以（1）的答案是B
（2）直接写代码
bool judge(string s){
    int temp = 0;
    for(int i = 0;i<s.size();i++){
        if(s[i]=='I') temp++;
        else temp--;
        if(temp<0) return false;
    }
    return true;
}

04.设单链表的表头指针为L，结点结构由data和next两个域构成，其中data域为字符型。试设计算法判断该链表的全部n个字符是否中心对称。例如xyx、xyyx 都是中心对称。

//这是提供两种做法：
//第一种做法是用快慢指针找到链表的中点，然后反转链表，再用两个指针对链表一一比较，不过需要考虑链表的长度是奇数还是偶数的情况（也可以不考虑，只要最后的判断条件是其中一个指针的下一个位置是NULL）
typedef struct Node{
    char data;
    Node * next;
}Node;

void solution(Node* h){
    Node * i = h;
    Node * j = h;
    while(j!=NULL||j->next!=NULL){
        j = j->next->next;
        if(j!=NULL)
        i = i->next;
    }
    Node* p = i->next;
    i->next = NULL;
    //这时反转i节点以及之后的节点就好
    Node * pre = NULL;
    while(p){
        Node * temp = p->next;
        p->next = pre;
        pre = p;
        p = temp;
    }
    Node * new_head = pre;
    while(new_head!=NULL&&h!=NULL){
        if(new_head->data!=head->data){
            return false;
        }
        new_head = new_head->next;
        h = h->next;
    }
    return true;
}

//也可以用栈的方式，把链表的全部元素按顺序读入到一个栈中，并记录入栈序列，读完之后再按顺序出栈，记录出栈序列，最后比较这两个序列是否相等。
//王道答案是只入栈一半的元素，然后用另一半元素与栈中弹出的元素相比较

05. 设有两个栈S1、S2都采用顺序栈方式，并共享一个存储区[0… maxsize-1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式。试设计S1、S2有关入栈和出栈的操作算法。

#define maxsize 100
typedef struct {
    int data[maxsize];
    int top1 = -1;//这里用指向当前栈顶部的指针表示
    int top2 = max_size;
}Stack;

bool push_s1(Stack* s,int x){
    if(s->top2-s->top1==1) return fasle;//如果栈满，不能入栈了
    s->data[++s->top1] = x;
    return true;
}
bool push_s2(Stack* s,int x){
    if(s->top2-s->top1==1) return fasle;//如果栈满，不能入栈了
    s->data[--s->top2] = x;
    return true;
}
bool pop_s2(Stack*s){
    if(s->top2==maxsize) return fasle;//如果栈空，不能出栈
    s->top2++;
}
bool pop_s1(Stack*s){
    if(s->top1==-1) return fasle;//如果栈空，不能出栈
    s->top1--;
}