stack&queue&list

环境：ide：Mac+clion

视频链接：
https://www.bilibili.com/video/BV1Hb411Y7E5?p=5

stack 容器，栈容器。先进后出。 类似于压子弹。只有一个出口。而且栈不允许有遍历的行为。

栈可以判断是否为空。可以判断栈的个数。
入栈：push
出栈：pop
栈顶元素：top
栈的大小：size

void test(){
    stack<int>s;//先进后出的容器。
    s.push(10);//入栈/压栈
    s.push(20);
    s.push(30);
    s.push(40);
    cout <<"入栈后的大小"<< s.size()<<endl;//4
    while(!s.empty()){
        cout << s.top()<<endl;//打印栈顶元素。
        s.pop();//出栈。
    }
    cout << "出栈后的大小"<<s.size()<<endl;//0
}

queue 先进先出的数据结构 和stack 正好相反。 有两个出口。 一头负责push，一头负责pop。 这样就保证了先进先出的特性。只有对头和对尾进行操作。 不允许遍历。

stl 提供了如下函数：入队push/出队pop/队尾back/队头front/是否为空empty/大小size

void test1(){
    queue<Person>q;//先进先出的数据结构。
    Person p1("sheik1",10);
    Person p2("sheik2",20);
    Person p3("sheik3",30);
    Person p4("sheik4",40);
    q.push(p1);//入队
    q.push(p2);
    q.push(p3);
    q.push(p4);
    cout << "queue 大小:"<<q.size()<<endl;
    while (!q.empty()){
        cout <<"队头中的数据姓名:"<< q.front().m_Name<<"  年龄:"<<q.front().m_Age<<endl;
        cout <<"队尾中的数据姓名:"<< q.back().m_Name<<"  年龄:"<<q.back().m_Age<<endl;
        q.pop();

    }
    cout << "queue 大小:"<<q.size()<<endl;
//    queue 大小:4
//    队头中的数据姓名:sheik1  年龄:10
//    队尾中的数据姓名:sheik4  年龄:40
//    队头中的数据姓名:sheik2  年龄:20
//    队尾中的数据姓名:sheik4  年龄:40
//    队头中的数据姓名:sheik3  年龄:30
//    队尾中的数据姓名:sheik4  年龄:40
//    队头中的数据姓名:sheik4  年龄:40
//    队尾中的数据姓名:sheik4  年龄:40
//    queue 大小:0
}

list 容器，将数据进行链式存储。数据中的逻辑是通过链表指针实现。由各种结点构成。结点是由数据域与指针域构成。

优点：就是可以快速的任意位置插入和删除。
缺点：
1.占用内存大。
2.遍历速度没有数组快。
STL中的链表是双向链表。
STL中list 和vector 是比较常用的容器。
list 构造和赋值：

void printList(const list<int> &l){
    for (list<int>::const_iterator it = l.begin();it!= l.end();it++){
        cout << *it << " ";
    }
    cout << endl;
}

void test2(){
    list<int>l;//默认构造函数。
    l.push_back(10);//尾插法，填入数据
    l.push_back(20);
    l.push_back(30);
    l.push_back(40);
    printList(l);
    list<int>l1(l);//这里类似于copy 构造函数
    printList(l1);
    list<int>l2(l.begin(),l.end());//通过区间来进行构造了
    printList(l2);
    list<int>l3(4,66);//使用66 初始化四个元素。
    printList(l3);
    list<int>l4 = l3;//直接使用operator=来进行赋值。
    printList(l4);

    list<int>l5 ;
    l5.assign(l1.begin(),l1.end());//通过assign的方式进行赋值。
    printList(l5);

    list<int>l6;
    l6.assign(4,777);//通过assign的方式进行赋值。
    printList(l6);
    l1.swap(l6);//交换。
    printList(l1);
    printList(l6);
}

list 大小：size/empty/resize 等函数。
list 容器的插入和删除：这里提供了一个remove 的函数，可以删除list 中某个elem。

void test3(){
    list<int>l;//默认构造函数。
    l.push_back(10);//尾插法，填入数据
    l.push_back(20);
    l.push_back(30);
    l.push_back(40);

    l.push_front(100);//头插法
    l.push_front(200);
    l.push_front(300);
    l.push_front(400);
    printList(l);//400 300 200 100 10 20 30 40

    l.pop_back();//尾删
    printList(l);//400 300 200 100 10 20 30
    l.pop_front();//头删
    printList(l);//300 200 100 10 20 30

//    插入
    l.insert(l.begin(),1);
    printList(l);//1 300 200 100 10 20 30
    list<int>::iterator it = l.begin();
    l.insert(++(++it),5);
    printList(l);

    //删除
    it = l.begin();
    l.erase(it);
    printList(l);
    l.push_back(5);
    printList(l);//300 5 200 100 10 20 30 5
    l.remove(5);//删除list 中所有=5的元素。
    printList(l);//300 200 100 10 20 30
    
};

list 容器数据存取：不支持[] 和at 访问list 里面的数据。

void test4(){
    list<int>l;//默认构造函数。
    l.push_back(10);//尾插法，填入数据
    l.push_back(20);
    l.push_back(30);
    l.push_back(40);
    //不支持[] 和at 访问list 里面的数据。
    cout<<"第一个元素："<<l.front()<<endl;
    cout << "最后一个元素："<<l.back()<<endl;
}

list 反转/排序，这里面有一个降序排序，引入了一个仿函数。

bool myCompare(int v1,int v2){
    return v1 > v2;//如果降序，那么就需要v1 > v2
}

void test5(){
    list<int>l;//默认构造函数。
    l.push_back(10);//尾插法，填入数据
    l.push_back(30);
    l.push_back(20);
    l.push_back(40);
    cout << "反转前打印:"<<endl;
    printList(l);//10 30 20 40
    l.reverse();
    cout << "反转后打印:"<<endl;
    printList(l);//40 20 30 10
    l.sort();//默认排序规则：从小到大
    cout << "排序后打印:"<<endl;
    printList(l);//10 20 30 40
    cout << "降序后打印:"<<endl;
    l.sort(myCompare);//降序排序，需要引入仿函数。
    printList(l);//40 30 20 10
}