一道堆栈的题
假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，可以操作的序列称为合法序列，否则称为非法序列。
1) 下面所示的序列中哪些是合法的？
a. IOIIOIOO b. IOOIOIIO c. IIIOIOIO d. IIIOOIOO
2) 通过对1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回 true，否则返回false（假定被判定的操作序列已存入一维数组中）。
解答：
1) A、D合法，而B、C不合法。在B中，先入栈1次，再连续出栈2次，错误。在 C中，入栈和出栈次数不一致，会导致最终的栈不空。A、D均为合法序列，请自行模拟。注意：在操作过程中，入栈次数一定大于或等于出栈次数；结束时，栈一定为空。
2) 设被判定的操作序列已存入一维数组A中。算法的基本设计思想：依次逐一扫描入栈出栈序列（即由"I"和"O"组成的字符串），每扫描至任一位置均需检查出栈次数（即 “O”的个数）是否小于入栈次数（"I"的个数)，若大于则为非法序列。扫描结束后，再判断入栈和出栈次数是否相等，若不相等则不合题意，为非法序列。
public class Main {public static void main(String[] args) {String str = "IIIOIOOOIOIO";char[] ch = str.toCharArray();int j = 0;for (int i=0;i另解：入栈后，栈内元素个数加1；出栈时判断栈是否为空，为空说明非法序列。所有入栈出栈都操作完后，判断栈中是否还有未出栈的数据，如果有则为非法序列，否则说明合法。
#define StackSize 10
typedef char DataType;//数组栈结构
typedef struct {DataType data[StackSize];int top;//栈顶位置
}SeqStack;//顺序表栈
//置空栈
void initStack(SeqStack * s){s->top = -1;
}
//判栈空
bool stackEmpty(SeqStack * s){return s->top < 0;
}
//判栈满
bool stackFull(SeqStack * s){return s->top == StackSize-1;
}
//入栈
void push(SeqStack * s,DataType x){if (stackFull(s)) {printf("stack overflow");} else {s->top = s->top+1;s->data[s->top] = x;}
}
//出栈
DataType pop(SeqStack * s){if (stackEmpty(s)) {printf("stack is empty");exit(0);} else {return s->data[s->top--];}
}
//取栈顶元素（不改变栈顶指针）
DataType getTop(SeqStack * s){if (stackEmpty(s)) {printf("stack is empty");exit(0);} else {return s->data[s->top];}
}int main(int argc, const char * argv[]) {char *p = "IOIIOIOO";SeqStack stack;//置空栈initStack(&stack);for (int i=0; i
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！