1、假设以I和O表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，可以操作的序列为合法序列，否则为非法序列，写出一个算法，判定所给的操作序列是否合法，如果合法，返回true，非法返回false

bool empty_stack(Seqstack &L)
{if(L.top==-1)return true;return false;
}bool full_stack(Seqstack &L)
{if(L.top==MaxSize-1) return true;return false;
}bool push_stack(Seqstack &L,char &x)
{if(full_stack(L)) return false;L.data[++L.top]=x;return true;
}bool pop_stack(Seqstack &L,char &x)
{if(empty_stack(L)) return false;x=L.data[L.top--];return true;
}
bool judgeSeqstack(Seqstack &L,string a)
{char x='1';for(int i=0;i<a.length();i++){if(a[i]=='I'&&push_stack(L,x)) return true;else return false;if(a[i]=='O'&&pop_stack(L,x)) return true;else return false;}return true;
}

比较常规，写出出入栈算法，结合起来判断即可。

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

typedef struct LNode{char data;struct LNode *next;
}LNode,*LinkList;typedef struct seqstack{char data[MaxSize];int top;
}seqstack;
bool symmetrical (LinkList &L)
{Seqstack Q;Q.top=-1;LNode *s=L->next;while(s!=NULL){push_stack(Q,s->data);s=s->next;}s=L->next;char x='1';bool aa=true;while(Q.top!=-1){pop_stack(Q,x);if(x==s->data) aa=true;else return false;s=s->next;}return true;
}

算法比较简单，就是先给出一个单链表，把里面的元素全部入栈，然后一个个出栈，挨个和链表元素比较是否相等，如果有一个不相等就直接false，一直都相等就一直true。

3、共享栈的实现

typedef struct share_stack{ElemType data[MaxSize];int top1;int top2;
}share_stack;void sharestack_inital(share_stack &L)
{L.top1=-1;L.top2=MaxSize;
}bool sharestack_empty(share_stack &L)
{if(L.top1==-1||L.top2==MaxSize) return true;return false;
}bool sharestack_full(share_stack &L)
{if(L.top1+1==L.top2) return true;return false;
}bool sharestack_push1(share_stack &L,ElemType &x)
{if(sharestack_full(L)) return false;L.data[++L.top1]=x;return true;
}bool sharestack_push2(share_stack &L,ElemType &x)
{if(sharestack_full(L)) return false;L.data[--L.top2]=x;return true;
}bool sharestack_pop1(share_stack &L,ElemType &x)
{if(sharestack_empty(L)) return false;x=L.data[L.top1--];return true;
}bool sharestack_pop2(share_stack &L,ElemType &x)
{if(sharestack_empty(L)) return false;x=L.data[L.top2++];return true;
}

共享栈栈空条件：栈底为-1或者MaxSize，栈满条件，左栈顶加一等于右栈顶，上面做法的判空最好不要写一起，栈空分开写，不过有点麻烦。