vector 动态数组

#include<vector>
using namespace std;

vector<int> 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<int>::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

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
using namespace std;

const int maxn = 30;
int n;
vector<int> 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

#include<stack>
using namespace std;

stack<int> S;
S.push();
S.pop();
S.top;

例题：POJ1363

#include<stack>
#include<cstdio>
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<int> 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 队列

#include<queue>
using namespace std;

queue<int> que;
que.back();
que.empty();
que.front();
que.pop();
que.push(elem);
que.size();

例题：POJ2259

#include<cstdio>
#include<queue>
#include<string>
#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<int> team[maxn];
            queue<int> 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;
    }