C++U4-第09课-STL容器

学习目标

 STL

 栈stack

[入栈出栈]

【算法分析】
栈的基本操作。

【参考代码】
#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int>st;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        st.push(x);
    }
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    return 0;
}

[模拟栈操作]

栈的基本操作，要注意输出格式。

【参考代码】
#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int>st;
    int n;
    cin >> n;
    while (n--) {
        string option;
        cin >> option;
        if (option == "push") {
            int x;
            cin >> x;
            st.push(x);
        }
        else if (option == "pop") {
            if (st.empty()) cout << "pop fail" << '\n';
            else {
                cout << "pop " << st.top() << '\n';
                st.pop();
            }
        }
        else if (option == "top") {
            if (st.empty()) cout << "top fail" << '\n';
            else cout << "top = " << st.top() << '\n';
        }
        else if (option == "size") {
            cout << "size = " << st.size() << '\n';
        }
        else {
            if (st.empty()) cout << "yes" << '\n';
            else cout << "no" << '\n';
        }
    }
    return 0;
}

[后缀表达式求值]

【算法分析】
后缀表达式求值的基本操作。

【参考代码】
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int num = 0;
    stack<int> st;
    for (int i = 0; i < s.length() - 1; i++) {
        if (s[i] == '.') {
            st.push(num);
            num = 0;
        }
        else if (s[i] >= '0' && s[i] <= '9') {
            num = num * 10 + s[i] - '0';
        }
        else {
            int r = st.top(); st.pop();
            int l = st.top(); st.pop();
            if (s[i] == '-') {
                st.push(l - r);
            }
            else if (s[i] == '+') {
                st.push(l + r);
            }
            else if (s[i] == '*') {
                st.push(l * r);
            }
        }
    }
    cout << st.top();
    return 0;
}

队列queue

[取牌游戏]

【算法分析】
用队列模拟取牌的操作。每次处理发队首的牌，然后将后面的 p 张牌依次放到队尾。重复上面的过程，直到队列为空。

【参考代码】
#include <bits/stdc++.h>
using namespace std;

int main() {
    queue<int> q;
    int k, n, p;
    cin >> k >> n >> p;
    for (int i = 1; i <= k; i++) q.push(i);
    while (q.size()) {
        cout << q.front() << " ";
        q.pop();
        if (q.size()) {//要队列里有元素才能访问队首
            for (int i = 0; i < p; i++) {
                int x = q.front();
                q.pop();
                q.push(x);
            }
        }
    }
    return 0;
}

优先队列：priority_queue

[合并果子]

【算法分析】
分析题目可以发现，每次合两个苹果数最小的堆消耗的体力最少。可以使用优先队列来维护最小数目的苹果堆。

【参考代码】
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int> >q;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        q.push(x);
    }
    int ans = 0;
    while (q.size() > 1) {
        int x = q.top();
        q.pop();
        int y = q.top();
        q.pop();
        ans += x + y;
        q.push(x + y);
    }
    cout << ans;
    return 0;
}

总结

 本节课作业讲解视频及分析

链接：https://pan.baidu.com/s/1SfdLzP9m2YpS_XBwwoHwsw?pwd=i1vt
提取码：i1vt