第三题

题目简述

假设以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;
}