假设以i和o分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由i和o组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 ①下面所示的序列中哪些是合法的？ a. ioiioioo b. iooioiio c. iiioioio d. iiiooioo ②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

### 回答1：
① 合法序列为 a 和 d，非法序列为 b 和 c。

② 算法如下：

1. 初始化一个空栈。
2. 遍历操作序列中的每一个字符：
1) 如果是 i，将其入栈。
2) 如果是 o，判断栈是否为空，如果为空则返回 false，否则将栈顶元素出栈。
3. 遍历完操作序列后，如果栈为空，则返回 true，否则返回 false。

### 回答2：
①对于一个合法的操作序列，必须满足以下两个条件：
1.当进行出栈操作时，栈顶必须有元素；
2.当进行入栈操作时，栈中元素数量不得超过一定限制（此题中未给出具体限制）

根据上述条件，对于每个给定的操作序列，可以模拟栈的操作过程：
1.首先将栈设为空；
2.从左到右遍历操作序列，对于每个操作，按照入栈或出栈的方式模拟操作过程；
3.如果进行出栈操作时，栈中没有元素，则该操作序列非法，返回false；
4.如果进行入栈操作时，栈中元素数量已达到限制，则该操作序列非法，返回false；
5.遍历完操作序列后，如果栈不为空，则该操作序列非法，返回false；否则操作序列合法，返回true。

根据上述算法，可以得到如下代码实现：

bool isLegalSequence(char op[], int len, int limit) {
stack<int> s;
for (int i = 0; i < len; ++i) {
if (op[i] == 'i') {//入栈操作
if (s.size() >= limit) return false;//栈中元素数量已达到限制，非法
s.push(i);
}
else {//出栈操作
if (s.empty()) return false;//栈中没有元素，非法
s.pop();
}
}
return s.empty();//遍历完操作序列后，如果栈不为空，则非法；否则合法
}

在该实现中，limit表示栈中元素数量的限制，可以根据具体问题进行调整。

### 回答3：
① 合法序列：a和d都是合法序列，b和c都是非法序列。

a序列中，先入栈i，再入栈o，再入栈i，再入栈i，再出栈o，再入栈o，再出栈o，最终栈为空，符合栈的特点，是合法序列。

d序列中，先入栈i，再入栈i，再入栈o，再出栈o，再入栈o，再出栈o，最终栈为空，符合栈的特点，是合法序列。

b序列中，先入栈i，再出栈o，再入栈o，再入栈i，再出栈o，再出栈i，最终栈为空，但是在出栈i之前，栈中还有一个元素，不符合栈的特点，是非法序列。

c序列中，先入栈i，再入栈i，再入栈i，再入栈o，再入栈i，再出栈o，再入栈o，最终栈中还剩一个元素，不为空，不符合栈的特点，是非法序列。

② 算法实现：

1. 初始化一个空栈。
2. 遍历操作序列中的每个元素，如果是入栈i操作，则将i入栈，如果是出栈o操作，则判断栈是否为空，如果不为空，则出栈，否则返回false。
3. 遍历结束后，如果栈为空，则返回true，否则返回false。

代码实现如下：

bool isLegal(char sequence[], int len) {
stack<char> s; // 定义一个栈
for(int i=0; i<len; i++) {
if(sequence[i] == 'i') s.push('i'); // 入栈
else if(!s.empty()) s.pop(); // 出栈
else return false; // 栈为空，非法序列
}
return s.empty(); // 栈为空，合法序列
}