判断栈的 push 和 pop 序列是否正确
有两个队列分别是 push 队列和 pop 队列
判断其入栈出栈序列是否正确
利用一个辅助栈 tmp
扫描 pop 队列
对 pop 队列的首元素进行检测，首先检测 tmp 栈顶元素是否与 pop 队首元素一样，如果一样则将则将 tmp 栈顶元素删除。
如果不一样，则遍历整个 push 队列，将不一样的压入到 tmp 中，直到遇到一样的。
http://www.cppblog.com/jake1036/archive/2011/05/19/146731.html
1 #include <iostream>
2 #include <queue>
3 #include <stack>
4 using namespace std;
5
6 bool foo(queue<int>& in, queue<int>& out)
7 {
8 stack<int> tmp;
9 int t;
10 while (!out.empty())
11 {
12 t = out.front();
13 out.pop();
14 if (!tmp.empty() && t == tmp.top())
15 {
16 cout << "出栈：" << tmp.top() << endl;
17 tmp.pop();
18 }
19 else
20 {
21 int find = false;
22 while (!in.empty())
23 {
24 if (t != in.front())
25 {
26 cout << "入栈：" << in.front() << endl;
27 tmp.push(in.front());
28 in.pop();
29 }
30 else
31 {
32 cout << "入栈：" << in.front() << endl;
33 tmp.push(in.front());
34 in.pop();
35 cout << "出栈：" << tmp.top() << endl;
36 tmp.pop();
37 find = true;
38 break;
39 }
40 }
41 if (!find)
42 {
43 return false;
44 }
45 }
46 }
47 return true;
48 }
49
50 int main()
51 {
52 queue<int> in, out;
53 int t, n;
54 while (cin >> n)
55 {
56 for (int i = 0; i != n; ++i)
57 {
58 cin >> t;
59 in.push(t);
60 }
61 for (int i = 0; i != n; ++i)
62 {
63 cin >> t;
64 out.push(t);
65 }
66 cout << foo(in ,out) << endl;
67 }
68 }
posted on 2011-07-23 13:14
unixfy 阅读(226)
评论(0) 编辑 收藏 引用