Posted on 2010-09-01 11:30
David Fang 閱讀(933)
評論(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 }