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

int main() {
    // 【默认构造】空字符串
    string s1;
    
    // 【C风格字符串构造】
    string s2("Hello");
    string s3 = "World";
    
    // 【重复字符构造】构造n个相同字符
    string s4(5, 'A');  // "AAAAA"
    
    // 【拷贝构造】
    string s5(s2);      // "Hello"
    string s6 = s2;     // "Hello"
    
    // 【子串构造】
    string s7(s2, 1, 3);  // 从位置1开始，长度为3："ell"
    
    cout << s1 << endl;  // 空字符串
    cout << s2 << endl;  // "Hello"
    cout << s4 << endl;  // "AAAAA"
    
    return 0;
}

string s = "Hello";

// 【push_back】在末尾添加字符
s.push_back('!');  // "Hello!"

// 【insert】在指定位置插入
s.insert(5, " World");  // "Hello World!"

// 【+=】字符串拼接
s += " C++";  // "Hello World! C++"

// 【append】追加字符串
s.append(" STL");  // "Hello World! C++ STL"

string s = "Hello World";

// 【erase】删除指定范围的字符
s.erase(5, 6);  // 从位置5开始删除6个字符："Hello"

// 【pop_back】删除最后一个字符
s.pop_back();  // "Hell"

// 【clear】清空字符串
s.clear();  // 空字符串

string s = "Hello";

// 【[]】下标访问（不检查边界）
char c1 = s[0];  // 'H'

// 【at】下标访问（检查边界，越界抛出异常）
char c2 = s.at(1);  // 'e'

// 【front】访问第一个字符
char c3 = s.front();  // 'H'

// 【back】访问最后一个字符
char c4 = s.back();  // 'o'

// 【substr】获取子串
string sub = s.substr(1, 3);  // 从位置1开始，长度为3："ell"

string s = "Hello World Hello";

// 【find】查找子串第一次出现的位置
size_t pos1 = s.find("World");  // 6
size_t pos2 = s.find("Hello", 1);  // 从位置1开始查找：12

// 【rfind】查找子串最后一次出现的位置
size_t pos3 = s.rfind("Hello");  // 12

// 【find_first_of】查找第一个匹配的字符
size_t pos4 = s.find_first_of("lo");  // 2（第一个'l'的位置）

// 【find_last_of】查找最后一个匹配的字符
size_t pos5 = s.find_last_of("lo");  // 16（最后一个'o'的位置）

// 【find_first_not_of】查找第一个不匹配的字符
size_t pos6 = s.find_first_not_of("Helo ");  // 6（'W'的位置）

// 如果未找到，返回string::npos
if (s.find("NotExist") == string::npos) {
    cout << "未找到" << endl;
}

string s1 = "Hello";
string s2 = "World";

// 【size/length】获取字符串长度
cout << s1.size() << endl;    // 5
cout << s1.length() << endl;  // 5

// 【empty】判断是否为空
if (!s1.empty()) {
    cout << "字符串不为空" << endl;
}

// 【compare】比较字符串
int result = s1.compare(s2);  // <0表示s1<s2，=0表示相等，>0表示s1>s2

// 【replace】替换子串
string s3 = "Hello World";
s3.replace(6, 5, "C++");  // 从位置6开始，替换5个字符："Hello C++"

// 【swap】交换两个字符串
s1.swap(s2);  // s1="World", s2="Hello"

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

int main() {
    // 【构造字符串】
    string s1 = "Hello";
    string s2(" World");
    
    // 【字符串拼接】
    string s3 = s1 + s2;  // "Hello World"
    s3 += "!";            // "Hello World!"
    
    // 【查找操作】
    size_t pos = s3.find("World");
    if (pos != string::npos) {
        cout << "找到'World'，位置：" << pos << endl;
    }
    
    // 【替换操作】
    s3.replace(pos, 5, "C++");  // "Hello C++!"
    cout << s3 << endl;
    
    // 【遍历字符串】
    for (size_t i = 0; i < s3.size(); i++) {
        cout << s3[i] << " ";
    }
    cout << endl;
    
    // 【范围for循环（C++11）】
    for (char c : s3) {
        cout << c << " ";
    }
    cout << endl;
    
    // 【子串操作】
    string sub = s3.substr(0, 5);  // "Hello"
    cout << sub << endl;
    
    return 0;
}

#include <utility>  // 或 <map>, <set> 等已包含
#include <iostream>
using namespace std;

int main() {
    // 【默认构造】使用默认值
    pair<int, string> p1;  // {0, ""}
    
    // 【直接构造】
    pair<int, string> p2(1, "one");
    pair<int, string> p3 = make_pair(2, "two");
    
    // 【列表初始化（C++11）】
    pair<int, string> p4{3, "three"};
    pair<int, string> p5 = {4, "four"};
    
    // 【拷贝构造】
    pair<int, string> p6(p2);
    pair<int, string> p7 = p2;
    
    return 0;
}

pair<int, string> p{1, "apple"};

// 【first】访问第一个元素
int key = p.first;  // 1

// 【second】访问第二个元素
string value = p.second;  // "apple"

// 【修改值】
p.first = 2;
p.second = "banana";

pair<int, string> p1{1, "apple"};
pair<int, string> p2{2, "banana"};
pair<int, string> p3{1, "apple"};

// 【比较操作】先比较first，相等时比较second
bool b1 = p1 < p2;   // true（1 < 2）
bool b2 = p1 == p3;   // true（first和second都相等）
bool b3 = p1 > p2;   // false

// 【make_pair】创建pair对象（自动推导类型）
auto p1 = make_pair(1, "one");
auto p2 = make_pair(2.5, 3);

// 【等价写法】
pair<int, string> p3 = make_pair(1, "one");
pair<double, int> p4 = make_pair(2.5, 3);

#include <iostream>
#include <utility>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

// 示例1：函数返回多个值
pair<int, int> findMinMax(vector<int>& nums) {
    if (nums.empty()) {
        return make_pair(0, 0);
    }
    int minVal = *min_element(nums.begin(), nums.end());
    int maxVal = *max_element(nums.begin(), nums.end());
    return make_pair(minVal, maxVal);
}

// 示例2：存储坐标点
void coordinatePoints() {
    vector<pair<int, int>> points;
    points.push_back({1, 2});
    points.push_back({3, 4});
    points.push_back({5, 6});
    
    cout << "坐标点: ";
    for (const auto& p : points) {
        cout << "(" << p.first << "," << p.second << ") ";
    }
    cout << endl;  // (1,2) (3,4) (5,6)
}

// 示例3：存储区间
void intervals() {
    vector<pair<int, int>> intervals{{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    
    // 按起始位置排序
    sort(intervals.begin(), intervals.end());
    
    cout << "区间: ";
    for (const auto& interval : intervals) {
        cout << "[" << interval.first << "," << interval.second << "] ";
    }
    cout << endl;  // [1,3] [2,6] [8,10] [15,18]
}

// 示例4：在map中使用
void mapWithPair() {
    map<string, pair<int, int>> studentScores;
    
    // 存储学生的数学和英语成绩
    studentScores["Alice"] = {95, 88};
    studentScores["Bob"] = {87, 92};
    studentScores["Charlie"] = {92, 85};
    
    // 访问
    for (const auto& [name, scores] : studentScores) {
        cout << name << ": 数学=" << scores.first 
             << ", 英语=" << scores.second << endl;
    }
}

// 示例5：作为vector的元素
void vectorOfPairs() {
    vector<pair<string, int>> fruits;
    fruits.push_back({"apple", 5});
    fruits.push_back({"banana", 3});
    fruits.push_back({"orange", 2});
    
    // 按数量排序
    sort(fruits.begin(), fruits.end(), 
         [](const pair<string, int>& a, const pair<string, int>& b) {
             return a.second < b.second;
         });
    
    cout << "按数量排序: ";
    for (const auto& [name, count] : fruits) {
        cout << name << ":" << count << " ";
    }
    cout << endl;  // orange:2 banana:3 apple:5
}

int main() {
    // 【基本使用】
    pair<int, string> p{1, "apple"};
    cout << "pair: (" << p.first << ", " << p.second << ")" << endl;
    
    // 【make_pair】
    auto p2 = make_pair(2, "banana");
    cout << "make_pair: (" << p2.first << ", " << p2.second << ")" << endl;
    
    // 【函数返回值示例】
    vector<int> nums{3, 1, 4, 1, 5, 9, 2, 6};
    auto [minVal, maxVal] = findMinMax(nums);  // C++17结构化绑定
    cout << "最小值: " << minVal << ", 最大值: " << maxVal << endl;
    
    // 【坐标点示例】
    coordinatePoints();
    
    // 【区间示例】
    intervals();
    
    // 【map中使用示例】
    mapWithPair();
    
    // 【vector of pairs示例】
    vectorOfPairs();
    
    return 0;
}

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

int main() {
    // 【默认构造】空vector
    vector<int> v1;
    
    // 【指定大小构造】n个默认值
    vector<int> v2(5);  // 5个0
    
    // 【指定大小和初始值构造】
    vector<int> v3(5, 10);  // 5个10
    
    // 【列表初始化（C++11）】
    vector<int> v4{1, 2, 3, 4, 5};
    
    // 【拷贝构造】
    vector<int> v5(v4);
    vector<int> v6 = v4;
    
    // 【范围构造】
    vector<int> v7(v4.begin(), v4.end());
    
    return 0;
}

vector<int> v;

// 【push_back】在尾部插入元素
v.push_back(1);
v.push_back(2);
v.push_back(3);  // v = {1, 2, 3}

// 【insert】在指定位置插入元素
v.insert(v.begin() + 1, 10);  // 在位置1插入10：{1, 10, 2, 3}
v.insert(v.end(), 4);         // 在末尾插入4：{1, 10, 2, 3, 4}

// 【insert】插入多个相同元素
v.insert(v.begin(), 3, 0);  // 在开头插入3个0：{0, 0, 0, 1, 10, 2, 3, 4}

vector<int> v{1, 2, 3, 4, 5};

// 【pop_back】删除最后一个元素
v.pop_back();  // {1, 2, 3, 4}

// 【erase】删除指定位置的元素
v.erase(v.begin() + 1);  // 删除位置1的元素：{1, 3, 4}

// 【erase】删除指定范围的元素
v.erase(v.begin(), v.begin() + 2);  // 删除前2个元素：{4}

// 【clear】清空所有元素
v.clear();  // 空vector

vector<int> v{1, 2, 3, 4, 5};

// 【[]】下标访问（不检查边界）
int a = v[0];  // 1
int b = v[2];  // 3

// 【at】下标访问（检查边界，越界抛出异常）
int c = v.at(1);  // 2

// 【front】访问第一个元素
int d = v.front();  // 1

// 【back】访问最后一个元素
int e = v.back();  // 5

// 【迭代器访问】
for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it << " ";
}

vector<int> v;

// 【size】获取元素个数
cout << v.size() << endl;  // 0

// 【empty】判断是否为空
if (v.empty()) {
    cout << "vector为空" << endl;
}

// 【capacity】获取容量（已分配的内存大小）
cout << v.capacity() << endl;  // 可能大于size

// 【resize】改变大小
v.resize(5);      // 大小变为5，新元素为默认值0
v.resize(10, 1);  // 大小变为10，新元素为1

// 【reserve】预留容量（避免频繁重新分配内存）
v.reserve(100);  // 预留100个元素的空间

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 【创建vector】
    vector<int> v{3, 1, 4, 1, 5, 9, 2, 6};
    
    // 【遍历vector】
    cout << "原始vector: ";
    for (int x : v) {
        cout << x << " ";
    }
    cout << endl;
    
    // 【排序】
    sort(v.begin(), v.end());
    cout << "排序后: ";
    for (int x : v) {
        cout << x << " ";
    }
    cout << endl;
    
    // 【查找】
    auto it = find(v.begin(), v.end(), 5);
    if (it != v.end()) {
        cout << "找到5，位置：" << it - v.begin() << endl;
    }
    
    // 【删除重复元素】
    v.erase(unique(v.begin(), v.end()), v.end());
    cout << "去重后: ";
    for (int x : v) {
        cout << x << " ";
    }
    cout << endl;
    
    // 【二维vector】
    vector<vector<int>> matrix(3, vector<int>(4, 0));  // 3x4的矩阵，初始值为0
    matrix[0][0] = 1;
    matrix[1][1] = 2;
    
    return 0;
}

#include <list>
#include <iostream>
using namespace std;

int main() {
    // 【默认构造】空list
    list<int> l1;
    
    // 【指定大小构造】n个默认值
    list<int> l2(5);  // 5个0
    
    // 【指定大小和初始值构造】
    list<int> l3(5, 10);  // 5个10
    
    // 【列表初始化（C++11）】
    list<int> l4{1, 2, 3, 4, 5};
    
    // 【拷贝构造】
    list<int> l5(l4);
    list<int> l6 = l4;
    
    return 0;
}

list<int> l;

// 【push_front】在头部插入
l.push_front(1);
l.push_front(2);  // {2, 1}

// 【push_back】在尾部插入
l.push_back(3);
l.push_back(4);  // {2, 1, 3, 4}

// 【insert】在指定位置插入
auto it = l.begin();
++it;  // 指向第二个元素
l.insert(it, 10);  // 在位置1插入10：{2, 10, 1, 3, 4}

// 【insert】插入多个相同元素
l.insert(l.end(), 3, 5);  // 在末尾插入3个5：{2, 10, 1, 3, 4, 5, 5, 5}

list<int> l{1, 2, 3, 2, 4, 2, 5};

// 【pop_front】删除第一个元素
l.pop_front();  // {2, 3, 2, 4, 2, 5}

// 【pop_back】删除最后一个元素
l.pop_back();  // {2, 3, 2, 4, 2}

// 【erase】删除指定位置的元素
auto it = l.begin();
++it;
l.erase(it);  // 删除位置1的元素：{2, 2, 4, 2}

// 【erase】删除指定范围的元素
l.erase(l.begin(), l.end());  // 清空（等同于clear）

// 【remove】删除所有等于指定值的元素
l = {1, 2, 3, 2, 4, 2, 5};
l.remove(2);  // 删除所有2：{1, 3, 4, 5}

// 【clear】清空所有元素
l.clear();

list<int> l{1, 2, 3, 4, 5};

// 【front】访问第一个元素
int a = l.front();  // 1

// 【back】访问最后一个元素
int b = l.back();  // 5

// 【注意】list不支持[]和at()，只能通过迭代器访问
for (auto it = l.begin(); it != l.end(); ++it) {
    cout << *it << " ";
}

list<int> l1{3, 1, 4, 1, 5};
list<int> l2{2, 7, 1, 8};

// 【sort】排序（成员函数，不是算法库的sort）
l1.sort();  // {1, 1, 3, 4, 5}

// 【unique】去除连续重复元素（需要先排序）
l1.unique();  // {1, 3, 4, 5}

// 【merge】合并两个有序list（l2会被清空）
l2.sort();  // {1, 2, 7, 8}
l1.merge(l2);  // l1 = {1, 1, 3, 4, 5, 7, 8}, l2为空

// 【reverse】反转
l1.reverse();  // {8, 7, 5, 4, 3, 1, 1}

// 【splice】移动元素（从一个list移动到另一个list）
list<int> l3{10, 20};
l1.splice(l1.begin(), l3);  // l1 = {10, 20, 8, 7, ...}, l3为空

#include <iostream>
#include <list>
using namespace std;

int main() {
    // 【创建list】
    list<int> l{3, 1, 4, 1, 5, 9, 2, 6};
    
    // 【遍历list】
    cout << "原始list: ";
    for (int x : l) {
        cout << x << " ";
    }
    cout << endl;
    
    // 【排序】
    l.sort();
    cout << "排序后: ";
    for (int x : l) {
        cout << x << " ";
    }
    cout << endl;
    
    // 【去重】
    l.unique();
    cout << "去重后: ";
    for (int x : l) {
        cout << x << " ";
    }
    cout << endl;
    
    // 【在中间插入】
    auto it = l.begin();
    advance(it, 2);  // 移动到第3个位置
    l.insert(it, 10);
    cout << "插入10后: ";
    for (int x : l) {
        cout << x << " ";
    }
    cout << endl;
    
    // 【删除指定值】
    l.remove(5);
    cout << "删除5后: ";
    for (int x : l) {
        cout << x << " ";
    }
    cout << endl;
    
    return 0;
}

#include <stack>
#include <iostream>
using namespace std;

int main() {
    // 【默认构造】空stack
    stack<int> s1;
    
    // 【基于其他容器构造】
    deque<int> d{1, 2, 3};
    stack<int> s2(d);  // 基于deque构造
    
    // 【基于vector构造】
    vector<int> v{1, 2, 3};
    stack<int, vector<int>> s3(v);  // 指定底层容器为vector
    
    return 0;
}

stack<int> s;

// 【push】在栈顶插入元素
s.push(1);
s.push(2);
s.push(3);  // 栈顶是3

// 【pop】删除栈顶元素（不返回值）
s.pop();  // 删除3，栈顶变为2

// 【注意】pop()不返回值，需要先top()再pop()
int top = s.top();  // 获取栈顶元素：2
s.pop();            // 删除栈顶元素

stack<int> s;
s.push(1);
s.push(2);
s.push(3);

// 【top】访问栈顶元素（不删除）
int top = s.top();  // 3

// 【注意】stack不支持遍历，只能访问栈顶

stack<int> s;

// 【size】获取元素个数
cout << s.size() << endl;  // 0

// 【empty】判断是否为空
if (s.empty()) {
    cout << "栈为空" << endl;
}

// 【注意】stack没有clear()，需要手动清空
while (!s.empty()) {
    s.pop();
}

#include <iostream>
#include <stack>
#include <string>
using namespace std;

// 示例1：括号匹配
bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return st.empty();
}

// 示例2：表达式求值（简单版本）
int evaluatePostfix(string expr) {
    stack<int> st;
    for (char c : expr) {
        if (isdigit(c)) {
            st.push(c - '0');
        } else {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            if (c == '+') st.push(a + b);
            else if (c == '-') st.push(a - b);
            else if (c == '*') st.push(a * b);
            else if (c == '/') st.push(a / b);
        }
    }
    return st.top();
}

int main() {
    // 【基本使用】
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    
    cout << "栈顶元素: " << s.top() << endl;  // 3
    s.pop();
    cout << "弹出后栈顶元素: " << s.top() << endl;  // 2
    
    // 【括号匹配示例】
    string expr1 = "()[]{}";
    string expr2 = "([)]";
    cout << expr1 << " 是否有效: " << isValid(expr1) << endl;  // true
    cout << expr2 << " 是否有效: " << isValid(expr2) << endl;  // false
    
    // 【表达式求值示例】
    string postfix = "23+";
    cout << "后缀表达式 " << postfix << " 的值: " << evaluatePostfix(postfix) << endl;  // 5
    
    return 0;
}

#include <queue>
#include <iostream>
using namespace std;

int main() {
    // 【默认构造】空queue
    queue<int> q1;
    
    // 【基于其他容器构造】
    deque<int> d{1, 2, 3};
    queue<int> q2(d);  // 基于deque构造
    
    // 【基于list构造】
    list<int> l{1, 2, 3};
    queue<int, list<int>> q3(l);  // 指定底层容器为list
    
    return 0;
}

queue<int> q;

// 【push】在队尾插入元素
q.push(1);
q.push(2);
q.push(3);  // 队列：1 -> 2 -> 3（队头是1，队尾是3）

// 【pop】删除队头元素（不返回值）
q.pop();  // 删除1，队头变为2

// 【注意】pop()不返回值，需要先front()再pop()
int front = q.front();  // 获取队头元素：2
q.pop();                // 删除队头元素

queue<int> q;
q.push(1);
q.push(2);
q.push(3);

// 【front】访问队头元素（不删除）
int front = q.front();  // 1

// 【back】访问队尾元素（不删除）
int back = q.back();  // 3

// 【注意】queue不支持遍历，只能访问队头和队尾

queue<int> q;

// 【size】获取元素个数
cout << q.size() << endl;  // 0

// 【empty】判断是否为空
if (q.empty()) {
    cout << "队列为空" << endl;
}

// 【注意】queue没有clear()，需要手动清空
while (!q.empty()) {
    q.pop();
}

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 示例1：BFS遍历（广度优先搜索）
void bfs(vector<vector<int>>& graph, int start) {
    queue<int> q;
    vector<bool> visited(graph.size(), false);
    
    q.push(start);
    visited[start] = true;
    
    cout << "BFS遍历顺序: ";
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";
        
        // 遍历相邻节点
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    cout << endl;
}

// 示例2：任务调度（简单版本）
void taskScheduler() {
    queue<string> tasks;
    
    // 添加任务
    tasks.push("任务1");
    tasks.push("任务2");
    tasks.push("任务3");
    
    // 处理任务
    cout << "任务处理顺序: ";
    while (!tasks.empty()) {
        string task = tasks.front();
        tasks.pop();
        cout << task << " ";
    }
    cout << endl;
}

// 示例3：层次遍历二叉树（模拟）
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void levelOrder(TreeNode* root) {
    if (!root) return;
    
    queue<TreeNode*> q;
    q.push(root);
    
    cout << "层次遍历: ";
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    cout << endl;
}

int main() {
    // 【基本使用】
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    
    cout << "队头元素: " << q.front() << endl;  // 1
    cout << "队尾元素: " << q.back() << endl;   // 3
    cout << "队列大小: " << q.size() << endl;  // 3
    
    q.pop();
    cout << "弹出后队头元素: " << q.front() << endl;  // 2
    
    // 【BFS示例】
    vector<vector<int>> graph = {
        {1, 2},      // 节点0的邻居
        {0, 3, 4},   // 节点1的邻居
        {0, 5},     // 节点2的邻居
        {1},        // 节点3的邻居
        {1},        // 节点4的邻居
        {2}         // 节点5的邻居
    };
    bfs(graph, 0);
    
    // 【任务调度示例】
    taskScheduler();
    
    return 0;
}

#include <queue>
#include <iostream>
#include <vector>
#include <functional>
using namespace std;

int main() {
    // 【默认构造】空优先队列（最大堆）
    priority_queue<int> pq1;
    
    // 【基于vector构造】最大堆
    vector<int> v{3, 1, 4, 1, 5, 9, 2, 6};
    priority_queue<int> pq2(v.begin(), v.end());
    
    // 【最小堆】使用greater比较函数
    priority_queue<int, vector<int>, greater<int>> pq3;
    
    // 【自定义比较函数】最小堆
    priority_queue<int, vector<int>, less<int>> pq4;  // 最大堆（默认）
    
    return 0;
}

priority_queue<int> pq;  // 最大堆

// 【push】插入元素
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(1);
pq.push(5);  // 堆顶是5（最大值）

// 【pop】删除堆顶元素（不返回值）
pq.pop();  // 删除5，堆顶变为4

// 【注意】pop()不返回值，需要先top()再pop()
int top = pq.top();  // 获取堆顶元素：4
pq.pop();            // 删除堆顶元素

priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(5);

// 【top】访问堆顶元素（不删除）
int top = pq.top();  // 5（最大值）

// 【注意】priority_queue不支持遍历，只能访问堆顶

priority_queue<int> pq;

// 【size】获取元素个数
cout << pq.size() << endl;  // 0

// 【empty】判断是否为空
if (pq.empty()) {
    cout << "优先队列为空" << endl;
}

// 【注意】priority_queue没有clear()，需要手动清空
while (!pq.empty()) {
    pq.pop();
}

// 【最小堆】使用greater
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(3);
minHeap.push(1);
minHeap.push(4);
cout << minHeap.top() << endl;  // 1（最小值）

// 【自定义结构体】按某个字段排序
struct Person {
    string name;
    int age;
    Person(string n, int a) : name(n), age(a) {}
};

// 按年龄从大到小排序（最大堆）
struct CompareAge {
    bool operator()(const Person& a, const Person& b) {
        return a.age < b.age;  // 注意：优先队列的比较函数是反的
    }
};

priority_queue<Person, vector<Person>, CompareAge> pq;
pq.push(Person("Alice", 25));
pq.push(Person("Bob", 30));
pq.push(Person("Charlie", 20));
cout << pq.top().name << endl;  // Bob（年龄最大）

// 【使用Lambda表达式（C++11）】
auto cmp = [](int a, int b) { return a > b; };  // 最小堆
priority_queue<int, vector<int>, decltype(cmp)> pq2(cmp);

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

// 示例1：Top K问题（找出最大的K个数）
vector<int> topK(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;  // 最小堆
    
    for (int num : nums) {
        pq.push(num);
        if (pq.size() > k) {
            pq.pop();  // 保持堆大小为k
        }
    }
    
    vector<int> result;
    while (!pq.empty()) {
        result.push_back(pq.top());
        pq.pop();
    }
    reverse(result.begin(), result.end());  // 反转得到从大到小
    return result;
}

// 示例2：合并K个有序序列
vector<int> mergeKSortedArrays(vector<vector<int>>& arrays) {
    struct Element {
        int val;
        int arrayIdx;
        int idx;
        Element(int v, int a, int i) : val(v), arrayIdx(a), idx(i) {}
    };
    
    auto cmp = [](const Element& a, const Element& b) {
        return a.val > b.val;  // 最小堆
    };
    
    priority_queue<Element, vector<Element>, decltype(cmp)> pq(cmp);
    
    // 将每个数组的第一个元素加入堆
    for (int i = 0; i < arrays.size(); i++) {
        if (!arrays[i].empty()) {
            pq.push(Element(arrays[i][0], i, 0));
        }
    }
    
    vector<int> result;
    while (!pq.empty()) {
        Element e = pq.top();
        pq.pop();
        result.push_back(e.val);
        
        // 将下一个元素加入堆
        if (e.idx + 1 < arrays[e.arrayIdx].size()) {
            pq.push(Element(arrays[e.arrayIdx][e.idx + 1], e.arrayIdx, e.idx + 1));
        }
    }
    
    return result;
}

// 示例3：任务调度（按优先级）
struct Task {
    string name;
    int priority;
    Task(string n, int p) : name(n), priority(p) {}
};

bool operator<(const Task& a, const Task& b) {
    return a.priority < b.priority;  // 优先级大的在前（最大堆）
}

void taskScheduler() {
    priority_queue<Task> tasks;
    
    tasks.push(Task("任务1", 3));
    tasks.push(Task("任务2", 1));
    tasks.push(Task("任务3", 5));
    tasks.push(Task("任务4", 2));
    
    cout << "任务执行顺序（按优先级）: ";
    while (!tasks.empty()) {
        Task task = tasks.top();
        tasks.pop();
        cout << task.name << " ";
    }
    cout << endl;
}

int main() {
    // 【基本使用】最大堆
    priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);
    
    cout << "最大堆堆顶: " << pq.top() << endl;  // 5
    pq.pop();
    cout << "弹出后堆顶: " << pq.top() << endl;  // 4
    
    // 【最小堆】
    priority_queue<int, vector<int>, greater<int>> minHeap;
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(4);
    minHeap.push(5);
    cout << "最小堆堆顶: " << minHeap.top() << endl;  // 1
    
    // 【Top K示例】
    vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    vector<int> top3 = topK(nums, 3);
    cout << "Top 3: ";
    for (int x : top3) {
        cout << x << " ";
    }
    cout << endl;  // 9 6 5
    
    // 【合并K个有序序列示例】
    vector<vector<int>> arrays = {
        {1, 4, 7},
        {2, 5, 8},
        {3, 6, 9}
    };
    vector<int> merged = mergeKSortedArrays(arrays);
    cout << "合并后: ";
    for (int x : merged) {
        cout << x << " ";
    }
    cout << endl;  // 1 2 3 4 5 6 7 8 9
    
    // 【任务调度示例】
    taskScheduler();
    
    return 0;
}

#include <deque>
#include <iostream>
using namespace std;

int main() {
    // 【默认构造】空deque
    deque<int> dq1;
    
    // 【指定大小构造】n个默认值
    deque<int> dq2(5);  // 5个0
    
    // 【指定大小和初始值构造】
    deque<int> dq3(5, 10);  // 5个10
    
    // 【列表初始化（C++11）】
    deque<int> dq4{1, 2, 3, 4, 5};
    
    // 【拷贝构造】
    deque<int> dq5(dq4);
    deque<int> dq6 = dq4;
    
    // 【范围构造】
    deque<int> dq7(dq4.begin(), dq4.end());
    
    return 0;
}

deque<int> dq;

// 【push_front】在头部插入
dq.push_front(1);
dq.push_front(2);  // {2, 1}

// 【push_back】在尾部插入
dq.push_back(3);
dq.push_back(4);  // {2, 1, 3, 4}

// 【insert】在指定位置插入元素
dq.insert(dq.begin() + 2, 10);  // 在位置2插入10：{2, 1, 10, 3, 4}

// 【insert】插入多个相同元素
dq.insert(dq.end(), 3, 5);  // 在末尾插入3个5：{2, 1, 10, 3, 4, 5, 5, 5}

deque<int> dq{1, 2, 3, 4, 5};

// 【pop_front】删除第一个元素
dq.pop_front();  // {2, 3, 4, 5}

// 【pop_back】删除最后一个元素
dq.pop_back();  // {2, 3, 4}

// 【erase】删除指定位置的元素
dq.erase(dq.begin() + 1);  // 删除位置1的元素：{2, 4}

// 【erase】删除指定范围的元素
dq.erase(dq.begin(), dq.end());  // 清空（等同于clear）

// 【clear】清空所有元素
dq.clear();  // 空deque

deque<int> dq{1, 2, 3, 4, 5};

// 【[]】下标访问（不检查边界）
int a = dq[0];  // 1
int b = dq[2];  // 3

// 【at】下标访问（检查边界，越界抛出异常）
int c = dq.at(1);  // 2

// 【front】访问第一个元素
int d = dq.front();  // 1

// 【back】访问最后一个元素
int e = dq.back();  // 5

// 【迭代器访问】
for (auto it = dq.begin(); it != dq.end(); ++it) {
    cout << *it << " ";
}

deque<int> dq;

// 【size】获取元素个数
cout << dq.size() << endl;  // 0

// 【empty】判断是否为空
if (dq.empty()) {
    cout << "deque为空" << endl;
}

// 【resize】改变大小
dq.resize(5);      // 大小变为5，新元素为默认值0
dq.resize(10, 1);  // 大小变为10，新元素为1