STL--stack

stack--概述：

　　栈（Stack）是一种特殊的线性表，只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶。栈也称为先进后出表（LIFO）。

允许进行插入和删除操作的一端称为栈顶（Top），另一端为栈底（Bottom）。栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。

l插入一个元素称为进栈（Push），删除一个栈顶元素称为出栈（Pop）。

成员函数	功能
bool empty()	栈为空返回true，否则返回false
void pop()	删除栈顶元素，即出栈
void push( const TYPE &val )	将新元素val进栈，使其成为栈顶的第一个元素
TYPE &top()	查看当前栈顶元素
size_type size()	返回堆栈中的元素数目

题目练习：

（会陆续添加）

1.stack模拟题，要读懂题意（别忘了清空栈）

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1061

 1 #include<iostream>
 2 #include<string>
 3 #include<stack>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     //freopen( "in.txt", "r", stdin );
 9     //freopen( "out.txt", "w", stdout );
10     stack<string> s1;
11     stack<string> s2;
12     string str, str2;
13     string top;
14     int n;
15     cin>>n;
16     while(n--)
17     {
18         while(!s1.empty()) s1.pop();
19         while(!s2.empty()) s2.pop();
20         s2.push("http://www.acm.org/");
21         while(cin>>str&&str!="QUIT")
22         {
23             if(str=="VISIT")
24             {
25                 while(!s1.empty()) s1.pop();
26                 cin>>str2;
27                 s2.push(str2);
28                 cout<<str2<<endl;
29             }
30             if(str=="BACK")
31             {
32                 if(s2.size()==1) cout<<"Ignored
";
33                 else
34                 {
35                     top = s2.top();
36                     s2.pop();
37                     s1.push(top);
38                     top = s2.top();
39                     cout<<top<<endl;
40                 }
41             }
42             if(str=="FORWARD")
43             {
44                 if(s1.empty()) cout<<"Ignored
";
45                 else
46                 {
47                     top = s1.top();
48                     s1.pop();
49                     s2.push(top);
50                     cout<<top<<endl;
51                 }
52             }
53         }    
54         if(n) cout<<endl;
55     }
56     return 0;
57 }

View Code

2.一道较综合性的模拟题：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1094

 1 //解题思路， 用栈存储矩阵信息（行和列），
 2 // 遇到右括号进行栈顶两个元素相乘， 
 3 //并把乘积入栈。 
 4 
 5 #include<iostream>
 6 #include<cstdio>
 7 #include<map>
 8 #include<stack>
 9 #include<string>
10 using namespace std;
11 
12 struct Node{
13     int row;
14     int col;
15 };
16 
17 map<char, Node> matrix;
18 int n;
19 char name;
20 
21 int main()
22 {
23     //freopen( "in.txt", "r", stdin );
24     //freopen( "out.txt", "w", stdout );
25     cin>>n;
26     for(int i=0; i<n; i++)
27     {
28         cin>>name;
29         cin>>matrix[name].row>>matrix[name].col;
30     }  
31     string exp;
32     while(cin>>exp)
33     {
34         int i;
35         int count = 0;
36         stack<Node> array;
37         for(i=0; i<exp.size(); i++)
38         {
39             if(exp[i]=='(') continue;
40             if(exp[i]==')')
41             {
42                 Node b = array.top();
43                 array.pop();
44                 Node a = array.top();
45                 array.pop();
46                 if(a.col!=b.row)
47                 {
48                     cout<<"error"<<endl;
49                     break;
50                 }
51                 count += a.row*b.row*b.col;
52                 Node tmp = {a.row, b.col};
53                 array.push(tmp);
54             }
55             else array.push(matrix[exp[i]]);
56         }
57         if(i==exp.size())
58         cout<<count<<endl;
59     }
60     return 0;
61 }
62

View Code

3.注意读入技巧。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1259

 1 #include<iostream>
 2 #include<stack>
 3 using namespace std;
 4 
 5 const int maxn = 1000 + 5;
 6 int target[maxn], n;
 7 
 8 void go(int *target)
 9 {
10     int A=1, B=1;
11     stack<int> s;
12     int ok=1;
13     while(B<=n)
14     {
15         if(A==target[B]) 
16         {
17             A++, B++;
18         }
19         else if(!s.empty()&&s.top()==target[B])
20         {
21             s.pop(); B++;
22         }
23         else if(A<=n) s.push(A++);
24         else
25          {
26              ok = 0; break;
27          }
28     }
29     if(ok) printf("Yes
");
30     else printf("No
");
31 }
32 
33 int main()
34 {
35     //freopen( "in.txt", "r", stdin );
36     //freopen( "out.txt", "w", stdout );
37     while(scanf("%d", &n)!=EOF&&n)
38     {
39     RL:    scanf("%d", &target[1]);
40         if(!target[1])
41         {
42             printf("
");
43             continue;
44         }
45         else
46         {
47             for(int i=2; i<=n; i++)
48             scanf("%d", &target[i]);
49             go(target);    goto RL;    
50         }
51     }
52     return 0;
53 }

View Code

4.再来道稍难的（stack+回溯法）

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1004

 1 #include<iostream>
 2 #include<cstring>
 3 #include<string>
 4 #include<vector>
 5 #include<stack>
 6 using namespace std;
 7 
 8 string a, b;
 9 stack<char> build;
10 vector<char> operate;
11 int len;
12 
13 void dfs(int A, int B)
14 {
15     if(A==len&&B==len)
16     {
17         for(int i=0; i<operate.size(); i++)
18         cout<<operate[i]<<" ";
19         cout<<endl;
20     }
21     if(A+1<=len)
22     {
23         build.push(a[A]);
24         operate.push_back('i');
25         dfs(A+1, B);
26         build.pop();
27         operate.pop_back();
28     }
29     if(B+1<=A&&B+1<=len&&build.top()==b[B])
30     {
31         char tc = build.top();
32         build.pop();
33         operate.push_back('o');
34         dfs(A, B+1);
35         build.push(tc);
36         operate.pop_back();
37     }
38 }
39 int main()
40 {
41     //freopen( "in.txt", "r", stdin );
42     //freopen( "out.txt", "w", stdout );
43     while(cin>>a>>b)
44     {
45         len = a.length();
46         cout<<"["<<endl;
47         dfs(0, 0);
48         cout<<"]"<<endl;
49     }
50     return 0;
51 }

View Code