【考研复习】24王道数据结构课后习题代码｜第3章栈与队列

3.1 栈

int symmetry(linklist L,int n){char s[n/2];lnode *p=L->next;int i;for(i=0;i<n/2;i++){s[i]=p->data;p=p->next;}i--;if(n%2==1) p=p->next;while(p&&s[i]==p->data){i--;p=p->next;}if(i==-1) return 1;else return 0;
}

typedef struct {int stack[Max];int top[2];
}stk;
stk s;
int push(int i, int x){if(i<0||i>1){cout<<"no stack"<<endl;return -1;}if(s.top[1]-s.top[0]==1){cout<<"full stack"<<endl;return -1;}switch (i){case 0:s.stack[++s.top[0]]=x; return 1;break;case 1:s.stack[++s.top[1]]=x; return 1;break;}
}
int pop(int i){if(i<0||i>1){cout<<"no stack"<<endl;return -1;}switch (i){case 0:if(s.top[0]==-1){cout<<"empty stack"<<endl;return -1;}else{return s.stack[s.top[0]--];}break;case 1:if(s.top[0]==Max){cout<<"empty stack"<<endl;return -1;}else{return s.stack[s.top[1]--];}break;}
}

3.2 队列

#define Maxsize 10
typedef struct{int data[Maxsize];int rear,front,tag;
}SqQueue;

int EnQueue(SqQueue &Q, int x){if(Q.front==Q.rear&&Q.tag==1) return 0; //队列满了Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%Maxsize;Q.tag=1;return 1;
}
int DeQueue(SqQueue &Q, int x){if(Q.front==Q.rear&&Q.tag==0) return 0; //队空x=Q.data[Q.front];Q.front=(Q.front+1)%Maxsize;Q.tag=0;return 1;
}

伪代码

void inverse(stack &s, queue &q){while(!queueempty(q)){x=dequeue(q);push(s,x);}while(!stackempty(s)){pop(s,x);enqueue(q,x);}
}

int enqueue(stack &s1, stack &s2, int e){if(!(stackoverflow(s1))){push(s1,e);return 1;}if(stackoverflow(s1)&&!(stackempty(s2))){cout<<" stack is overflow. "<<endl;return 0;}if(stackoverflow(s1)&&stackempty(s2)){while(!(stackempty(s1))){pop(s1,x);push(s2,x);}}push(s1,e);return 1;
}
void dequeue(stack &s1,stack &s2, int &x){if(!stackempty(s2)){pop(s2,x);}else if(stackempty(s1)){cout<<" stack is empty"<<endl;}else{while(!stackempty(s1)){pop(s1,x);push(s2,x);}pop(s2,x);}
}
int queueempty(stack s1,stack s2){if(stackempty(s1)&&stackempty(s2)){return 1;}else return 0;
}

3.3 栈和队列的应用

#include <iostream>
#include <stack>
using namespace std;
bool check(char str[]){stack <char> sck; int i=0;char temp;while(str[i]!='\0'){if(str[i]=='('||str[i]=='{'||str[i]=='[') {sck.push(str[i]);break;}else if(str[i]==']'){temp = sck.top();sck.pop();if(temp!='[') return false;}else if(str[i]==')'){temp = sck.top();sck.pop();if(temp!='(') return false;}else if(str[i]=='}'){temp = sck.top();sck.pop();if(temp!='{') return false;}}if(sck.empty()) return true;return false;
}
int main(){char *str=(char*)"()[](}{}()";cout<<str<<endl;if(!check(str)) cout<<"no !!"<<endl;else cout<<"yes!!1"<<endl;return 0;}

#include <iostream>
#include <stack>
using namespace std;
void train_arrange(char *train){stack <char> sck;char *p=train,*q=train,t;while(*p){if(*p=='H') {sck.push(*p);}else{*(q++)=*p;}p++;}while (!sck.empty()){t = sck.top();sck.pop();*(q++)=t;}}
int main()
{char str[11]="HSHSHHHSHS";train_arrange(str);cout<<str<<endl;return 0;
} // namespace std;

#include <iostream>
#define maxsize 100
using namespace std;
double p(int n, double x){struct stack{int no;double val;}st[maxsize];int top=-1,i;double fv1=1,fv2=2*x;for(i=n;i>=2;i--){top++;st[top].no=i;}while(top>0){st[top].val=2*x*fv2-2*(st[top].no-1)*fv1;fv1=fv2;fv2=st[top].val;top--;}if(n==0){return fv1;}return fv2;
}
int main(){
double ans1=p(1,1.9);cout<<ans1<<endl;
}