C++学习笔记（十）

一、stack容器

1.1基本概念

stack是一种先进后出的数据结构，只有一个出口

栈中只有顶端元素可以被外界使用，所以栈是不可以做遍历的

• 栈中进入数据的行为被称为入栈push
• 栈中弹出数据的行为被称为出栈pop

1.2stack常用接口

1.2.1构造函数

• stack<t> stackstack采用的是模板类操作，stack对象的默认构造形式
• stack(const stack &stk)拷贝构造函数

1.2.2赋值操作

• stack& operator = (const stack &stk)重载等号操作

1.2.3数值存取

• push(elem)向栈顶添加元素
• pop()从栈顶移除第一个元素
• top()返回栈顶元素

1.2.4大小操作

• empty()判断栈是否为空
• size()返回栈的大小

#include "iostream"
#include "stack"
using namespace std;

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);
    s.push(30);
    s.push(40);

    while(!s.empty()) {
        cout << s.top() << endl;
        s.pop();
    }
}

二、queue容器

2.1基本概念

Queue是一种先进先出的数据结构，它有两个出口

队列容器允许从一端新增元素，从另外一端移除元素

队列中只有队头和队尾才可以被外界所使用，因此队列不允许有遍历的行为

队列中进数据被称为-入队：push

队列中出数据被称为-出队：pop

2.2queue常用接口

2.2.1构造函数

• queue<t> queuequeue采用的是模板类操作，queue对象的默认构造形式
• queue(const queue &que)拷贝构造函数

2.2.2赋值操作

• queue& operator = (const queue &que)重载等号操作

2.2.3数值存取

• push(elem)向栈顶添加元素
• pop()从栈顶移除第一个元素
• back()返回最后一个元素
• front()返回第一个元素

2.2.4大小操作

• empty()判断栈是否为空
• size()返回栈的大小

#include "iostream"
#include "queue"
using namespace std;

int main() {
    queue<int> q;

    q.push(10);
    q.push(20);
    q.push(30);
    q.push(40);

    while (!q.empty()) {
        // 队头
        cout << q.front() << endl;
        // 队尾
        cout << q.back() << endl;
        // 出队
        q.pop();
    }
}

三、list容器

3.1基本概念

功能：将数据进行链式存储

链表是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现

结点的组成：一个是存储数据元素的数据域，一个是存储下一个结点地址的指针域

• 优点是可以对任意位置进行快速的插入和删除元素

• 缺点是容器遍历速度没有数组快，占用空间比数组大

由于链表的存储方式并不是连续的存储空间，因此链表中的迭代器直支持前移和后移，属于双向迭代器

链表采用动态存储分配，不会造成内存的浪费和溢出

STL中list和vector是两个最常用的容器，需要根据各自的优缺点进行选择

3.2构造函数

• list<T> lst;采用模板类实现，对象的默认构造方式
• list(beg, end);构造函数将[beg, end]中间的元素拷贝给本身
• list(n, elem);构造函数将n个elem拷贝给本身
• list(const list &lst);拷贝构造函数

#include "iostream"
#include "list"
using namespace std;

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

int main() {
    // 默认构造
    list<int> L1;
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);
    printList(L1);

    // 区间构造
    list<int> L2(L1.begin(), L1.end());
    printList(L2);

    // 拷贝构造
    list<int> L3(L2);
    printList(L3);

    // n个elem
    list<int> L4(10, 1000);
    printList(L4);
}

3.3list赋值域交换

• assign(beg, end)将[beg, end]区间中的数据拷贝赋值给本身
• assign(n, elem)将n个elem拷贝赋值给本身
• list& operator = (const list &lst)重载等号运算符
• swap(lst)将lst与本身元素互换

#include "iostream"
#include "list"
using namespace std;

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

int main() {
    // 默认构造
    list<int> L1;
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);
    printList(L1);

    list<int> L2 = L1;
    printList(L2);

    list<int> L3;
    L3.assign(L2.begin(), L2.end());
    printList(L3);

    list<int> L4;
    L4.assign(10, 1000);
    printList(L4);

    // 交换
    L3.swap(L4);
    printList(L3);
    printList(L4);
}

3.4大小操作

• size()返回容器中元素的个数
• empty()判断容器是否为空
• resize(num)重新指定容器长度为num，如果容器变长，则以默认值填重新位置，如果变短，超出部分被删除
• resize(num, elem)重新指定容器长度为num，如果容器变长，则以elem值填重新位置，如果变短，超出部分被删除

3.5插入与删除

• push_back(elem);在容器尾部加入一个元素
• pop_back();删除容器中最后一个元素
• push_front(elem);在容器开头插入一个元素
• pop_front();从容器开头移除第一个元素
• insert(pos, elem);在pos位置插elem元素的拷贝，返回新数据的位置
• insert(pos, n, elem);在pos位置插入n个elem数据，无返回值
• insert(pos, beg, end);在pos位置插入[beg, end)区间的数据，无返回值
• clear();移除容器的所有数据
• erase(beg, end);删除[beg, end)区间的数据，返回下一个数据的位置
• erase(pos);删除pos位置的数据，返回下一个数据的位置
• remove(elem);删除容器中所有与elem值匹配的元素

3.6数据存取

• front()返回第一个元素
• back()返回最后一个元素

#include "iostream"
#include "list"
using namespace std;

int main() {
    // 默认构造
    list<int> L1;
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);

    cout << L1.front() << endl;
    cout << L1.back() << endl;
}

3.7list反转和排序

• reverse()反转链表
• sort()链表排序

#include "iostream"
#include "list"
using namespace std;

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

int main() {
    // 默认构造
    list<int> L1;
    L1.push_back(10);
    L1.push_back(30);
    L1.push_back(20);
    L1.push_back(40);

    printList(L1);
    // 反转
    L1.reverse();
    printList(L1);
    // 排序
    L1.sort();
    printList(L1);
}

所有不支持随机访问迭代器的容器，不可以使用标准算法