栈与队列 #

#define MaxSize 50 //定义栈中元素的最大个数
typedef struct{
Elemtype data[MaxSize]; //存放栈中元素
int top; //栈顶指针
} SqStack; //顺序栈的简写

void InitStack(&s){
    s.top=-1;
}

bool StackEmpty(SqStack S){
if(s.top==-1) return true;
else return false;
}

bool Push(SqStack &S ，ElemType x){
if(S.top==MaxSize-1) return false;
S.data[++S.top]=x; return true;
}

bool Pop(SqStack &S，ElemType &x){
if(S.top==-1) return false;
x=S.data[S.top--]; 
return true;
}

bool GetTop(SqStack S，ElemType &x){
if(S.top==-1) return false;
x=S.data[S.top]; 
return true;
}

#define MaxSize 100 //定义栈中元素的最大个数
typedef struct{
Elemtype data[MaxSize]; //存放栈中元素
int top1; //栈1栈顶指针
int top2; //栈2栈顶指针
} SqDoubleStack; //顺序共享栈的简写

bool Push(SqDoubleStack &S ，ElemType x，int stackNum){
if(S.top1+1==s.top2) return false; //栈满
if(stackNum==1) S.data[++S.top1]=x; //栈1有元素进栈
else if(stackNum==2) S.data[--S.top2]=x; //栈2有元素进栈
return true;
}

typedef struct SNode{
Elemtype data; //存放栈中元素
struct SNode *next ; //栈顶指针
} SNode，
*SLink //链栈的结点
typedef struct LinkStack{
SLink top; //栈顶指针
int count; //链栈结点数
}LinkStack //链栈

bool Push(LinkStack *S, ElemType x){
SLink p=(SLink)malloc(sizeof(SNode)); //给新元素分配空间
p->data=x; //新元素的值
p->next=S->top; //p的后继指向栈顶元素
S->top=p; //栈顶指针指向新的元素
S->count++; //栈中元素个数加1
return true; 
}

bool Pop(LinkStack *S, ElemType&x){
if(S->top==NULL) return false;
x=S->top->data; //栈顶元素值
Slink p=S->top; //辅助指针
S->top=S->top->next; //栈顶指针后移
free(p); //释放被删除数据的存储空间
S->count--; //栈中元素个数减一
return true; 
}

#define MaxSize 50 //定义队列中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //存放队列元素
int front，rear; //队头指针和队尾指针
} SqQueue;

bool EnQueue(SqQueue &Q,ElemType x){
if((Q.rear+1)%MaxSize==Q.front) return false; //队满
Q.data[Q.rear]=x;
Q.rear=(Q.rear+1)%MaxSize; 
return true;
}

bool DeQueue(SqQueue &Q,ElemType &x){
if(Q.rear==Q.front) return false; //队空，报错
x=Q.data[Q.front];
Q.front=(Q.front+1)%MaxSize;
return true;
}

typedef struct{ //链式队列结点
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{ //链式队列
LinkNode *front,*rear; //队头和队尾指针
}LinkQueue;

void EnQueue(LinkQueue &Q，ElemType x){
s=(LinkNode *)malloc(sizeof(LinkNode));
s->data=x; 
s->next=NULL; 
Q.rear->next=s;
Q.rear=s;
}

bool DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front==Q.rear) return false; //空队
p=Q.front->next;
x=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front; //若原队列中只有一个结点，删除后变空
free(p);
return true;
}

bool Check(char *str ){
stack s;
InitStack(s);
int len=strlen(str); //字符串长度为len
for(int i=0;i<len;++i)
{
char a=str[i];
switch(a){
case '(':
case '[':
Push(s,a);
break;
case ')':
if( Pop(s)!=‘(‘ ) return false; //出栈顶。如果不匹配直接返回不合法
break;
case ']':
if( Pop(s)!=‘]’ ) return false; 
break;
}
}
if(Empty(s)) return true; //匹配完所有括号最后要求栈中为空
else return false
}

int Fib (int n) { 
if(n==0) return 0; 
else if(n==1) return 1;
else return Fib(n-1)+Fib(n-2);
}