王道第三章栈和队列

栈 判断栈的输入输出操作是否合法 //判断栈的输入输出操作是否合法 typedef struct { ElementType data[maxsize]; int top; }stack; bool is_legal(char opea[]){ int i=0; int j=0,k=0;//j表示入栈的操作次数,k表示出栈的次数 while(opea[i]!='\0'){ switch (opea[i]) { case 'I': j++; break; case 'O': k++; if(k>j) return false; } i++; } if(j!=k) return false; else return true; } 判断单链表中的n个字符是否中心对称 //判断单链表中的n个字符是否中心对称 #define maxsize 50 #define ElementType char typedef struct node{ ElementType data; struct node* next; }LinkNode,*Linklist; bool is_symmetry(Linklist L,int n){ int i; char s[n/2]; LinkNode *p=L->next; for(i=0;i<n/2;i++){ s[i]=p->data; p=p->next; } i--; if(n%2!=0) p=p->next; while(p!= nullptr&&s[i]==p->data){ i--; p=p->next; } if(i==-1) return true; else return false; } 共享栈入栈和出栈 #define maxn 100 #define ElemenType int typedef struct { ElemenType stack[maxn]; int top[2]; }stk; stk s; int push(int i,ElemenType x){ if(i!=0&&i!=1) exit(0); if(s.top[1]-s.top[0]==1) return 0; switch (i) { case 0:s.stack[++s.top[0]]=x;return 1; case 1:s.stack[--s.top[1]]=x;return 1; } } int pop(int i){ if(i!=0&&i!=1) exit(0); switch (i) { case 0: if(s.top[0]==-1) return -1; return s.stack[s.top[0]--]; case 1: if(s.top[1]==maxn) return -1; return s.stack[s.top[1]++]; } } 3.4栈的括号匹配 #define maxsize 30 //判断三类括号是否匹配 typedef struct{ char data[maxsize]; int top; }Sqstack; bool bracketCheck(char str[]){ Sqstack S; S.top=-1; int i=0; while(str[i]!='\0'){ if(str[i]=='('||str[i]=='['||str[i]=='{'){ S.data[++S.top]=str[i]; }else{ if(S.top==-1){ return false; } char topelem; topelem=S.data[S.top--]; if(str[i]==')'&&topelem!='(') return false; if(str[i]==']'&&topelem!='[') return false; if(str[i]=='}'&&topelem!='{') return false; } i++; } if(S.top==-1) return true; else return false; } 队列 #define maxsize 50 #define ElementType int //设置Tag来区分队满还是队空，写出出队入队算法 typedef struct { ElementType data[maxsize]; int front,rear,tag; }Sqqueue1; bool enqueue(Sqqueue1 &Q,ElementType x){ if(Q.rear==Q.front&&Q.tag==1) return false; Q.data[Q.rear]=x; Q.rear=(Q.rear+1)%maxsize; Q.tag=1; return true; } bool dequeue(Sqqueue1 &Q,ElementType &x){ if(Q.rear==Q.front&&Q.tag==0) return false; x=Q.data[Q.front]; Q.front=(Q.front+1)%maxsize; Q.tag=0; return true; } //队列和空栈实现将队列中的元素逆转(front指向队首元素，rear指向队尾元素的后一个元素） typedef struct { ElementType data[maxsize]; int front,rear; }Sqqueue; typedef struct { ElementType data[maxsize]; int top; }stack; Sqqueue reverse(Sqqueue &Q,stack &S){ while(Q.front!=Q.rear){ int x=Q.data[Q.front]; Q.front=(Q.front+1)%maxsize; S.data[++S.top]=x; } while(S.top!=-1){ int x=S.data[S.top--]; Q.data[Q.rear]=x; Q.rear=(Q.rear+1)%maxsize; } return Q; } //两个栈实现队列入队出队是否为空 void Push(stack &S,ElementType x){}; void Pop(stack &S,ElementType &x){}; bool StackEmpty(stack S){}; bool StackOverflow(stack S){}; int enque(stack &S1,stack &S2,ElementType e){ if(!StackOverflow(S1)){ Push(S1,e); return 1; } if(StackOverflow(S1)&&!StackEmpty(S2)){ printf("队列已满"); return 0; } ElementType x; if(StackOverflow(S1)&& StackEmpty(S2)){ while(!StackEmpty(S1)){ Pop(S1,x); Push(S2,x); } } Push(S1,e); return 1; } void deque(stack &S1,stack &S2,ElementType &x){ if(!StackEmpty(S2)){ Pop(S2,x); }else if(StackEmpty(S1)){ printf("队列为空"); }else{ while(!StackEmpty(S1)){ ElementType temp; Pop(S1,temp); Push(S2,temp); } Pop(S2,x); } } bool is_empty(stack S1,stack S2){ return StackEmpty(S1)&& StackEmpty(S2); } //循环链式队列实现 typedef struct node{ ElementType data; struct node* next; }CLqueueNode; typedef struct { CLqueueNode *front,*rear; }CLqueue; bool enCLqueue(CLqueue &C,ElementType x){ if(C.rear->next==C.front){ CLqueueNode *p=(CLqueueNode *) malloc(sizeof (CLqueueNode)); p->data=x; p->next=C.front; C.rear->next=p; C.rear=p; }else{ C.rear->data=x; C.rear=C.rear->next; } return true; } bool deCLqueue(CLqueue &C,ElementType &x){ if(C.rear==C.front) return false; x=C.front->data; C.front=C.front->next; return true; }