昨天看程序员面试精选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[] = {123456};
41     int popseq[] = {43521};
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 }



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


posts - 9, comments - 13, trackbacks - 0, articles - 0

Copyright © David Fang