24考研王道408数据结构-第三章“栈、队列、数组”课后算法题(P70--栈的模拟)

第三题

#include
using namespace std;

bool solution(char s[]){
	int n=8;
	int numI=0;
	for(int i=0;i<n;i++){
		if(s[i]=='I'){
			numI++;
		}
		if(s[i]=='O'){
			if(numI==0){
				return false;
			}
			numI--;
		}
	}
	return true;
}

int main(){
	//char s[8]={'I','O','I','I','O','I','O','O'};
	char s[8]={'I','O','O','I','O','I','I','O'};
	if(solution(s)){
		cout<<"true";
	}else{
		cout<<"false";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

第四题

#include
#include
using namespace std;
struct listNode{
	char val;
	struct listNode*next;
};

bool reList(listNode* &head,int n){
	int i;
	char s[n/2];//s字符栈 
	listNode *p=head;
	for(i=0;i<n/2;i++){
		s[i]=p->val;
		p=p->next;
	}
	i--;//恢复最后的i值，使其指向字符数栈的最后一个元素 
	if(n%2==1){//若n是奇数，后移过中心结点 
		p=p->next;
	}
	while(p!=NULL&&s[i]==p->val){//与链表后一半元素比较，检测是否中心对称 
		i--;//i充当栈顶指针 
		p=p->next;
	}
	if(i==-1){//栈为空 
		return true;
	}else{
		return false;
	}
}

int main(){
	listNode node5={'x',nullptr};
	listNode node4={'y',&node5};
	listNode node3={'y',&node4};
	listNode node2={'y',&node3};
	listNode node1={'x',&node2};
	
	listNode *L=&node1;
	if(reList(L,5)){
		cout<<"true";
	}else{
		cout<<"false";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

第五题

#include
using namespace std;
#define Max 50
typedef struct{
	int data[Max];//栈空间 
	int top[2];//top为两个栈顶指针 
} stack1;
stack1 s;
int push(int i,int x){
	//入栈操作。i为栈号, i=0表示左边的s1栈，i=1表示右边的s2栈，x是入栈元素 
	if(i!=0&&i!=1){
		cout<<"栈号不对"<<endl;
		return -1;
	}
	if(s.top[1]-s.top[0]==1){
		cout<<"栈满"<<endl;
		return -1; 
	}
	if(i==0){
		s.data[++s.top[0]]=x;//s1栈向右增加元素 
	}
	else{
		s.data[--s.top[1]]=x;//s2栈向左增加元素 
	}
	return 1;
}
int pop(int i){
	if(i!=0&&i!=1){
		cout<<"栈号不对"; 
	}
	if(i==0){
		if(s.top[0]==-1){
			cout<<"0号栈为空"<<endl;
			return -1;
		}
		return s.data[s.top[0]--];//先用后减 
	}else{
		if(s.top[1]==Max){
			cout<<"1号栈栈空";
			return -1; 
		} 
		return s.data[s.top[0]++];
	}
} 


int main(){
	s.top[0]=-1,s.top[1]=Max;
	if(push(0,1)!=-1){
		cout<<"0号栈进栈成功"<<endl;
	}
	int x=pop(0);
	if(x!=-1){
		cout<<"0号栈出栈成功";
		cout<<"0号栈出栈元素为："<<x<<endl;
	}
	int y=pop(0);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59