2020考研-王道数据结构-栈和队列-栈

心已赠人 2022-01-31 00:55 281阅读 0赞

# 第三题 #

##### 题目简述 #####

假设以I和O分别表示入栈和出栈操作，栈的初试状态和终止状态均为空，判断序列是否合法。

##### 代码 #####

#include <iostream>
    #include <string>
    
    using namespace std;
    
    bool judge(string str)
    {
        
    	int cnt = 0;
    	for (int i = 0; i < str.size(); i++)
    	{
        
    		switch (str[i])
    		{
        
    		case 'I': cnt++; break;
    		case 'O': cnt--; break;
    		default:
    			break;
    		}
    		if (cnt < 0)
    			return false;
    	}
    	return cnt == 0;
    }
    
    int main()
    {
        
    	if (judge("IOIIOIOO")) cout << "合法" << endl; else cout << "不合法" << endl;
    	if (judge("IOOIOIIO")) cout << "合法" << endl; else cout << "不合法" << endl;
    	if (judge("IIIOIOIO")) cout << "合法" << endl; else cout << "不合法" << endl;
    	if (judge("IIIOOIOO")) cout << "合法" << endl; else cout << "不合法" << endl;
    }

# 第四题 #

##### 题目简述 #####

设单链表的表头指针为L，判断链表的n个字符是否中心对称。

##### 代码 #####

// 本题说判断单链表中的元素是否中心对称
    // 为减少代码量，单链表改成字符串，和单链表的原理是一样的
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    bool judge(string str)
    {
        
    	int size = 0;
    	char* stk = new char[str.size()];
    	int mid = str.size() >> 1;
    	for (int i = 0; i < mid; i++) stk[size++] = str[i];
    	if (str.size() & 1) mid ++;
    	for (int i = mid; i < str.size(); i++)
    		if (str[i] != stk[--size])
    			return false;
    	return true;
    }
    
    int main()
    {
        
    	cout << judge("xyxyx") << endl;
    	cout << judge("xyyx") << endl;
    	cout << judge("xyx") << endl;
    	cout << judge("xxxy") << endl;
    	return 0;
    }

# 第五题 #

##### 题目简述 #####

设有两个栈s1，s2共享一个存储区，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式，设置入栈、和出栈的操作算法。

##### 代码 #####

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    #define MaxSize 100
    
    typedef int Elemtype;
    
    class SqStack
    {
        
    private:
    	Elemtype data[MaxSize];
    	int top[2];
    public:
    	SqStack(){
         top[0] = -1; top[1] = MaxSize; };
    	void push(int id, int x); // 向指定Id的栈push
    	Elemtype pop(int id);     // 弹出指定Id的栈的栈顶元素，并将值返回
    	bool isEmpty(int id); // 判断栈是不是空
    };
    
    void SqStack::push(int id, int x)
    {
        
    	if (id < 0 || id > 1) {
         cerr << "ID不合法!" << endl; return; }
    	if (top[1] - top[0] == 1) {
         cerr << "栈满, push失败!" << endl; return; }
    	if (id) data[--top[1]] = x;
    	else data[++top[0]] = x;
    }
    
    Elemtype SqStack::pop(int id)
    {
        
    	if (id < 0 || id > 1) {
         cerr << "ID不合法!" << endl; return (Elemtype)-1; }
    	if (top[id] == -1 || top[id] == MaxSize){
         cerr << "栈为空! pop失败!" << endl; return (Elemtype)-1; }
    	if (id) return data[top[1]++];
    	return data[top[0]--];
    }
    
    bool SqStack::isEmpty(int id){
        
    	if (id == 0) return top[0] == -1;
    	return top[1] == MaxSize;
    }
    
    int main()
    {
        
    	SqStack stk;
    	for (int i = 0; i < 105; i++){
        
    		if (i & 1) stk.push(0, i);
    		else stk.push(1, i);
    	}
    	// 0栈出
    	while (!stk.isEmpty(0)){
        
    		cout << stk.pop(0) << " ";
    	}
    	cout << endl;
    	while (!stk.isEmpty(1)){
        
    		cout << stk.pop(1) << " ";
    	}
    	cout << endl;
    }