Posted on 2010-09-01 11:30
David Fang 阅读(912)
评论(0) 编辑 收藏 引用 所属分类:
算法点滴
昨天看程序员面试精选100题，看到一个栈的push，pop序列问题。
题目：输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。
一开始还真不知道怎么下手，看了分析才知道大概方法。然后再看参考代码,感觉还是有些复杂。自己想了个稍微简单的方法,pop队列还可能是push队列的子集：
1 #include <iostream>
2 #include <stack>
3
4 using namespace std;
5 /*!
6 \brief This algorithm demostrates how to judge whether or not a given seqence is
7 possibly a popup sequence providing the pushing sequence.
8 */
9
10 bool IsPopSequence(int* ppush, int pushm, int* ppop, int popm)
11 {
12 int i = 0, j = 0;
13 stack<int> help_stack;
14 while(j < popm)
15 {
16 if (!help_stack.empty() && help_stack.top() == ppop[j])
17 {
18 help_stack.pop();
19 j++;
20 }
21 else if (i < pushm)
22 {
23 help_stack.push(ppush[i++]);
24 }
25 else
26 break;
27 }
28
29 return j >= popm;
30 }
31
32 int main(int argc, char *argv, char *env[])
33 {
34 //int pushseq[] = {1, 2, 3, 4, 5};
35 //int pushseqlen = sizeof(pushseq)/sizeof(pushseq[0]);
36 ////int popseq[] = {4, 5, 3, 2, 1};
37 //int popseq[] = {4, 3, 5, 1, 2};
38 //int popseqlen = sizeof(popseq)/sizeof(popseq[0]);
39
40 int pushseq[] = {1, 2, 3, 4, 5, 6};
41 int popseq[] = {4, 3, 5, 2, 1};
42 int pushseqlen = sizeof(pushseq)/sizeof(pushseq[0]);
43 int popseqlen = sizeof(popseq)/sizeof(popseq[0]);
44
45 cout<<boolalpha<<IsPopSequence(pushseq, pushseqlen, popseq, popseqlen)<<"\n";
46
47 return 0;
48 }