判斷棧的 push 和 pop 序列是否正確
有兩個隊列分別是 push 隊列和 pop 隊列
判斷其入棧出棧序列是否正確
利用一個輔助棧 tmp
掃描 pop 隊列
對 pop 隊列的首元素進行檢測，首先檢測 tmp 棧頂元素是否與 pop 隊首元素一樣，如果一樣則將則將 tmp 棧頂元素刪除。
如果不一樣，則遍歷整個 push 隊列，將不一樣的壓入到 tmp 中，直到遇到一樣的。
http://m.shnenglu.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 閱讀(241)
評論(0) 編輯 收藏 引用