posts - 183,  comments - 10,  trackbacks - 0

判断栈的 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> inout;
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 阅读(228) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理