## vector 动态数组 ```cpp #include using namespace std; vector vec; vec.begin(); vec.clear(); vec.empty(); vec.end(); vec.push_back(elem); vec.size(); vec.resize(); vec.push_back(2); vec.push_back(4); //下标遍历 for (int i = 0; i < vec.size(); ++i)cout << vec[i] << " "; cout << endl; //迭代器遍历 vector::iterator it; for (it = vec.begin(); it != vec.end(); ++it) cout << *it << " "; cout << endl; vec.insert(vec.begin() + 1, 6);//第二个位置插入6 vec = [2, 6, 4] vec.erase(vec.begin() + 1);//删除第二个位置的元素 vec = [2, 4] vec.clear(); ``` [例题：POJ1208](https://vjudge.net/contest/698956#problem/A) ``` cpp #include #include #include #include using namespace std; const int maxn = 30; int n; vector pile[maxn]; //找木块a所在的pile和height以引用形式返回调用者 void find_block(int a, int &p, int &h){ for (p = 0; p < n; p++) for (h = 0; h < pile[p].size(); h++) if (pile[p][h] == a) return; } //把第p堆高度为h的木块上方的所有木块移回原位 void clear_above(int p, int h){ for (int i = h + 1; i < pile[p].size(); i++){ int b = pile[p][i]; pile[b].push_back(b); } pile[p].resize(h + 1);//只保留下标0-h的元素节省内存 } //把第p堆高度为h及其上方的木块整体移动到p2堆的顶端 void place(int p, int h; int p2){ for (int i = h; i < pile[p].size(); i++) pile[p2].push_back(pile[p][i]); pile[i].resize(h); } void print(){ for (int i = 0; i < n; i++){ printf("%d:", i); for (int j = 0; j < pile[i].size(); j++) printf(" %d", pile[i][j]); printf("\n"); } } int main(){ //freopen("in.txt", "r", stdin); int a, b; cin >> n; string s1, s2; for (int i = 0; i < n; i++) pile[i].push_back(i); while (cin >> s1 >> a >> s2 >> b){ int pa, pb, ha, hb; if (s1 == "quit") break; find_block(a, pa, ha); find_block(b, pb, hb); if (pa == pb) continue; if (s2 == "onto") clear_above(pb, hb); if (s1 == "move") clear_above(pa, ha); place(pa, ha, pb); } print(); return 0; } ``` ## stack 栈后进先出 LIFO ``` cpp #include using namespace std; stack S; S.push(); S.pop(); S.top; ``` [例题：POJ1363](https://vjudge.net/contest/698956#problem/B) ```cpp #include #include using namespace std; typedef long long LL; const int mx = 1010; int n, a[mx], i; bool nfi; int main(){ while (~scanf("%d", &n) && n){ if (nfi) printf("\n"); while (~scanf("%d", &a[1]) && a[1]){ for (i = 2; i <= n; ++i) scanf("%d", &a[i]); stack S; i = 1; for (int j = 1; j <= n; ++j){ S.push(j); while (!S.empty() && S.top() == a[i]){ S.pop(); i++; } } if (S.empty()) printf("Yes\n"); else printf("No\n"); } nfi = true; } return 0; } ``` ## queue 队列 ```cpp #include using namespace std; queue que; que.back(); que.empty(); que.front(); que.pop(); que.push(elem); que.size(); ``` [例题：POJ2259](https://vjudge.net/contest/698956#problem/C) ```cpp #include #include #include #define maxn 1010 using namespace std; int belong[1000000]; int main(){ int T, n, a, t = 0; while (~scanf("%d", &T)){ if (T == 0) break; else{ queue team[maxn]; queue que; for (int i - 1; i <= T; i++){ scanf("%d", &n); while(n--){ scanf("%d", &a); belong[a] = i; } } printf("Scenario #%d\n", ++t); char command[200]; while (~scanf("%s", command)){ if (command[0] == 'S') break; if (command[0] == 'E'){ int elements, b; scanf("%d", &elements); b = belong[elements]; if (team[b].empty()){ que.push(b); team[b].push(elements); } else team[b].push(elements); else if (command == 'D'){ int ans = que.front(); printf("%d\n", team[ans].front()); team[ans].pop(); if (team[ans].empty()) que.pop(); } } } printf("\n") } return 0; } ```

Schabe Antimonfeld

ACM-ICPC基础 STL