【STL编程】【竞赛常用】【part 3】

• 【STL编程】【竞赛常用】【part 1】
• 【STL编程】【竞赛常用】【part 2】
• 【STL编程】【竞赛常用】【part 3】
• • 11. list 双向链表容器
  • • 结构体：
    • list链表归并例程
  • 12. stack 堆栈容器
  • 13. queue 队列容器
  • 14. deque 双端队列容器
  • 15. priority_queue 优先队列容器

【STL编程】【竞赛常用】【part 1】

【STL编程】【竞赛常用】【part 2】

list双向链表容器在头文件中声明，它对任一位置元素的查找、插入及删除都具有高效的常数阶算法时间复杂度。

#include  //使用万能头文件，无需写#include 
using namespace std;

int main(){
    list l;
    l.push_back(2); //尾部插入新元素，链表自动扩张
    l.push_back(2);
    l.push_back(9);
    l.push_back(12);
    l.push_back(12);
    l.push_back(4);
    l.push_back(4);
    l.push_back(6);
    // l.clear();//清空链表
    l.push_front(9); //头部插入新元素，链表自动扩张
    list::iterator it;
    it = l.begin();
    it++;             //链表迭代器只能++或--操作，不能进行+n操作，因为list节点不是连续内存
    l.insert(it, 20); //当前位置插入新元素
    it++;
    l.erase(it);                              //删除迭代器位置上的元素
    for (it = l.begin(); it != l.end(); it++) //正向遍历
        cout << *it << " ";
    cout << endl;
    l.remove(12);                     //删除所有值为12的元素
    l.pop_front();                    //删除链表首元素
    l.pop_back();                     //删除链表尾元素
    it = find(l.begin(), l.end(), 4); //查找元素值为4
    if (it != l.end())
        cout << "find " << *it << endl;
    l.sort();                                 //升序排列
    l.unique();                               //删除连续重复元素（只保留一个）
    for (it = l.begin(); it != l.end(); it++) //正向遍历
        cout << *it << " ";
    cout << endl;
    return 0;
}

#include 
using namespace std;

struct student{
    char *name;
    int age;
    char *city;
};

int main(){
    student s[] = {
            {"张三", 18, "浙江"},
            {"李四", 19, "北京"},
            {"王二", 18, "上海"}};
    list l;
    l.push_back(s[0]); //插入元素
    l.push_back(s[1]);
    l.push_back(s[2]);
    student x = {"刘四", 19, "新疆"};
    l.push_front(x);        //插入到首位，复杂度为O(1)
    l.insert(l.begin(), x); //插入任意位置,时间复杂度O(1)
    // l.pop_front();//删除首元素
    // l.pop_back();//删除尾元素
    l.erase(l.begin());
    // l.erase(l.begin(),l.end());//删除区间的元素
    for (list::iterator i = l.begin(); i != l.end(); i++)
        cout << (*i).name << "  " << (*i).age << "  " << (*i).city << "n";
    return 0;
}

#include 
using namespace std;

void print(list l){
    list::iterator i;
    for (i = l.begin(); i != l.end(); i++)
        cout << *i << " ";
    cout << endl;
}

int main(){
    list l1;
    for (int j = 10; j >= 0; j--)
        l1.push_back(j);

    list l2;
    list::iterator ii;
    l2.splice(l2.begin(), l1); //将l1的全部元素归并到L2，L1清空
    ii = l2.begin()++;
    l1.splice(l1.begin(), l2, ii); //将l2的ii位置的元素归并到l1，l2原元素删除
    print(l1);
    print(l2);
    // swap(l1,l2);//交换l1,l2
    l1.push_back(8);
    l1.push_back(8);
    l1.push_back(35);
    l1.unique(); //除去连续重复元素
    l2.push_back(30);
    l1.sort(); //排序
    l2.sort();
    print(l1);
    l2.merge(l1); // L1归并到l2，两链表需排序,具体见后面的见归并算法merge
    print(l2);
    return 0;
}

堆栈类似于一个一端开口、一端封闭的容器，开口端称为栈顶（Stack Top），封闭端称为栈底（Stack Bottom），元素的插入和删除只能在栈顶操作。堆栈的元素插入称为入栈，元素的删除称为出栈。堆栈的主要特点是“后进先出”（Last In First Out），即后入栈的元素先出栈。每次入栈的元素都放在原当前栈顶元素之上，成为新的栈顶元素，每次出栈的元素都是原当前栈顶元素

参考我的数据结构教程：
2021-9-22【数据结构/严蔚敏】【顺序栈&链式栈&迷宫求解&表达式求值】【代码实现算法3.1-3.5】

#include  
using namespace std;
#define STACK_SIZE 100

int main(){
    stack s;
    s.push("aaa"); //入栈
    s.push("bbb");
    s.push("ccc");
    if (s.size() < STACK_SIZE) //可限制大小
        s.push("68");
    cout << s.size() << endl; //输出栈内元素个数
    while (!s.empty()) {   //当栈不为空
        cout << s.top() << endl; //出栈
        s.pop();                 //出栈
    }
    return 0;
}

结果：

4
68
ccc
bbb
aaa

#include  
using namespace std;

int main(){
    queue q;
    q.push(3); //入队
    q.push(5);
    q.push(2);
    cout << "The number of elements is:" << q.size() << endl;
    cout << q.back();  //取队尾元素
    while (!q.empty())  { //当队列未空
        cout << q.front() << endl; //打印队首元素
        q.pop();                   //出队
    }
    return 0;
}

结果：

The number of elements is:3      
23
5
2

deque在头文件中声明，它是一种双向开口的连续线性空间，可以高效地在头、尾两端插入和删除元素。它的时间复杂度为O(1)，考虑容器元素的内存分配策略和操作性能时，deque比vector有优势。

#include 
using namespace std;

int main(){
    deque d;  //定义一个包含string类型的deque
    d.push_back("A"); //尾部插入元素
    d.push_back("B");
    d.push_back("C");
    d.push_front("X"); //头部插入元素
    d.push_front("Y");
    // d.pop_front();//删除首元素
    // d.pop_back();//删除尾元素
    // d.erase(d.begin()+1);//删除指定位置元素
    // d.clear();//删除所有元素
    d.insert(d.end() - 2, "O"); //指定位置插入

    reverse(d.begin(), d.end());       //反转元素顺序
    for (int i = 0; i < d.size(); i++) //数组方式访问
        cout << d[i] << " ";
    cout << endl;

    swap(d[1], d[2]);          //两元素交换
    deque::iterator i; //迭代器访问
    for (i = d.begin(); i != d.end(); i++)
        cout << *i << " ";
    cout << endl;

    cout << "nDeque is empty " << d.empty();
    cout << "nDeque element number is " << d.size();
    cout << "nDeque's first element is " << d.front();
    cout << "nThe last element of Deque is " << d.back();
    return 0;
}

结果：

C B O A X Y 
C O B A X Y

Deque is empty 0
Deque element number is 6
Deque's first element is C
The last element of Deque is Y

priority_queue优先队列容器在头文件中声明，与队列容器一样，只能从队尾插入元素，从队首删除元素。其一般形式为priority_queue，其中Type为数据类型，Container为保存数据的容器，Functional为元素比较方式。

Container必须是用数组实现的容器，例如vector、deque等，但不能用 list，STL里面默认用的是vector。如果后面两个参数采用默认设置，优先队列容器就是大顶堆（降序），队首元素最大。可以重载运算符来重新定义比较规则。

从小到大排列，让小的元素优先出队的基本写法如下。
priority_queue,greater >q;
从大到小排列，让大的元素优先出队的基本写法如下。(默认)
priority_queue,less >q;

#include 
using namespace std;

struct cmp{
    bool operator()(const int &a, const int &b) {//重载"()"操作符
        return a > b; //由小到大排列用">"，否则用"<"
    }
};

int main(){
    priority_queue, cmp> que1;
    //priority_queue, greater> que1;
    priority_queue> que2;
    int a[] = {1, 3, 4, 2, 5, 0, 6};
    for (int i = 0; i < 7; i++){
        que1.push(a[i]);
        que2.push(a[i]);
    }
    cout << "que1:";
    while (!que1.empty()){
        cout << que1.top() << " ";
        que1.pop();
    }
    cout << endl
         << "que2:";
    while (!que2.empty()){
        cout << que2.top() << " ";
        que2.pop();
    }
    return 0;
}