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模拟题， 要读懂题意（别忘了清空栈）
#include<iostream>
#include<string>
#include<stack>
using namespace std; int main()
{
//freopen( "in.txt", "r", stdin );
//freopen( "out.txt", "w", stdout );
stack<string> s1;
stack<string> s2;
string str, str2;
string top;
int n;
cin>>n;
while(n--)
{
while(!s1.empty()) s1.pop();
while(!s2.empty()) s2.pop();
s2.push("http://www.acm.org/");
while(cin>>str&&str!="QUIT")
{
if(str=="VISIT")
{
while(!s1.empty()) s1.pop();
cin>>str2;
s2.push(str2);
cout<<str2<<endl;
}
if(str=="BACK")
{
if(s2.size()==) cout<<"Ignored\n";
else
{
top = s2.top();
s2.pop();
s1.push(top);
top = s2.top();
cout<<top<<endl;
}
}
if(str=="FORWARD")
{
if(s1.empty()) cout<<"Ignored\n";
else
{
top = s1.top();
s1.pop();
s2.push(top);
cout<<top<<endl;
}
}
}
if(n) cout<<endl;
}
return ;
}
2.一道较综合性的模拟题：
//解题思路， 用栈存储矩阵信息（行和列），
// 遇到右括号进行栈顶两个元素相乘，
//并把乘积入栈。 #include<iostream>
#include<cstdio>
#include<map>
#include<stack>
#include<string>
using namespace std; struct Node{
int row;
int col;
}; map<char, Node> matrix;
int n;
char name; int main()
{
//freopen( "in.txt", "r", stdin );
//freopen( "out.txt", "w", stdout );
cin>>n;
for(int i=; i<n; i++)
{
cin>>name;
cin>>matrix[name].row>>matrix[name].col;
}
string exp;
while(cin>>exp)
{
int i;
int count = ;
stack<Node> array;
for(i=; i<exp.size(); i++)
{
if(exp[i]=='(') continue;
if(exp[i]==')')
{
Node b = array.top();
array.pop();
Node a = array.top();
array.pop();
if(a.col!=b.row)
{
cout<<"error"<<endl;
break;
}
count += a.row*b.row*b.col;
Node tmp = {a.row, b.col};
array.push(tmp);
}
else array.push(matrix[exp[i]]);
}
if(i==exp.size())
cout<<count<<endl;
}
return ;
}
3.注意读入技巧。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1259
#include<iostream>
#include<stack>
using namespace std; const int maxn = + ;
int target[maxn], n; void go(int *target)
{
int A=, B=;
stack<int> s;
int ok=;
while(B<=n)
{
if(A==target[B])
{
A++, B++;
}
else if(!s.empty()&&s.top()==target[B])
{
s.pop(); B++;
}
else if(A<=n) s.push(A++);
else
{
ok = ; break;
}
}
if(ok) printf("Yes\n");
else printf("No\n");
} int main()
{
//freopen( "in.txt", "r", stdin );
//freopen( "out.txt", "w", stdout );
while(scanf("%d", &n)!=EOF&&n)
{
RL: scanf("%d", &target[]);
if(!target[])
{
printf("\n");
continue;
}
else
{
for(int i=; i<=n; i++)
scanf("%d", &target[i]);
go(target); goto RL;
}
}
return ;
}
4.再来道稍难的（stack+回溯法）
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1004
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<stack>
using namespace std; string a, b;
stack<char> build;
vector<char> operate;
int len; void dfs(int A, int B)
{
if(A==len&&B==len)
{
for(int i=; i<operate.size(); i++)
cout<<operate[i]<<" ";
cout<<endl;
}
if(A+<=len)
{
build.push(a[A]);
operate.push_back('i');
dfs(A+, B);
build.pop();
operate.pop_back();
}
if(B+<=A&&B+<=len&&build.top()==b[B])
{
char tc = build.top();
build.pop();
operate.push_back('o');
dfs(A, B+);
build.push(tc);
operate.pop_back();
}
}
int main()
{
//freopen( "in.txt", "r", stdin );
//freopen( "out.txt", "w", stdout );
while(cin>>a>>b)
{
len = a.length();
cout<<"["<<endl;
dfs(, );
cout<<"]"<<endl;
}
return ;
}