一、stack栈容器(先进后出)
1. stack基本概念(顶端元素才被使用)
- 概念:stack是一种先进后出(First In Last Out,FILO)的数据结构,它只有一个出口。
- 栈中只有顶端的元素才可以被外界使用,因此栈不允许有遍历行为
- 栈中进入数据称为 — 入栈
push - 栈中弹出数据称为 — 出栈
pop
2. stack常用接口
功能描述: 栈容器常用的对外接口 构造函数:
stack<T> stk; stack采用模板类实现, stack对象的默认构造形式stack(const stack &stk); 拷贝构造函数
赋值操作:
stack& operator=(const stack &stk); 重载等号操作符
数据存取:
push(elem); 向栈顶添加元素pop(); 从栈顶移除第一个元素top(); 返回栈顶元素
大小操作:
empty(); 判断堆栈是否为空size(); 返回栈的大小
总结:
- 入栈 — push
- 出栈 — pop
- 返回栈顶 — top
- 判断栈是否为空 — empty
- 返回栈大小 — size
#include<algorithm>
#include<iostream>
#include<stack>
using namespace std;
void test01()
{
stack<int>s;
s.push(10);
s.push(20);
s.push(30);
s.push(40);
cout << "栈的大小:" << s.size() << endl;
while (!s.empty())
{
cout << "栈顶元素为:" << s.top() << endl;
s.pop();
}
cout << "栈的大小:" << s.size() << endl;
}
int main()
{
test01();
system("pause");
return 0;
}
二、queue队列容器(先进先出)
1. queue基本概念(队头队尾元素才被使用)
- 概念:Queue是一种先进先出(First In First Out,FIFO)的数据结构,它有两个出口。
- 队列容器允许从一端新增元素,从另一端移除元素。
- 队列中只有队头和队尾才可以被外界使用,因此队列不允许有遍历行为。
- 队列中进数据称为 — 入队
push - 队列中出数据称为 — 出队
pop
2. queue常用接口
功能描述: 栈容器常用的对外接口 构造函数:
queue<T> que; queue采用模板类实现,queue对象的默认构造形式queue(const queue &que); 拷贝构造函数
赋值操作:
queue& operator=(const queue &que); 重载等号操作符
数据存取:
push(elem); 往队尾添加元素pop(); 从队头移除第一个元素back(); 返回最后一个元素front(); 返回第一个元素
大小操作:
empty(); 判断堆栈是否为空size(); 返回栈的大小
总结:
- 入队 — push
- 出队 — pop
- 返回队头元素 — front
- 返回队尾元素 — back
- 判断队是否为空 — empty
- 返回队列大小 — size
#include<vector>
#include<algorithm>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
class Person
{
public:
Person(string name, int age)
{
this->m_Name = name;
this->m_Age = age;
}
string m_Name;
int m_Age;
};
void test01()
{
queue<Person>q;
Person p1("唐僧", 30);
Person p2("孙悟空", 1000);
Person p3("猪八戒", 900);
Person p4("沙僧", 800);
q.push(p1);
q.push(p2);
q.push(p3);
q.push(p4);
cout << "队列的大小:" << 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 << "队列的大小:" << q.size() << endl;
}
int main()
{
test01();
system("pause");
return 0;
}
三、list链表容器
1. list基本概念
- 功能: 将数据进行链式存储
- 链表(list)是一种物理存储单元上非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接实现的。
- 链表的组成:链表由一系列结点组成。
- 结点的组成:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
- STL中的链表是一个双向循环链表,既指向前一个节点,又指向后一个节点。
- 由于链表的存储方式并不是连续的内存空间,因此链表list中的迭代器只支持前移和后移,属于双向迭代器
list的优点:
- 采用动态存储分配,不会造成内存浪费和溢出
- 链表执行插入和删除操作十分方便,修改指针即可,不需要移动大量元素
list的缺点:
- 链表灵活,但是空间(指针域) 和 时间(遍历)额外耗费较大
重要性质:
- List有一个重要的性质,插入操作和删除操作都不会造成原有list迭代器的失效,这在vector是不成立的。
- 遍历速度没有指针快,因为数组地址是连续的
- 总结:STL中List和vector是两个最常被使用的容器,各有优缺点。
2. list构造函数
功能描述:
函数原型:
list<T> lst; list采用采用模板类实现,对象的默认构造形式:list(beg,end); 构造函数将[beg, end)区间中的元素拷贝给本身。list(n,elem); 构造函数将n个elem拷贝给本身。list(const list &lst); 拷贝构造函数
总结:
- list构造方式同其他几个STL常用容器,熟练掌握即可
#include<vector>
#include<algorithm>
#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;
}
void test01()
{
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);
list<int>L4(10, 1000);
printList(L4);
}
int main()
{
test01();
system("pause");
return 0;
}
3. list赋值与交换(加const)
功能描述:
函数原型:
assign(beg, end); 将[beg, end)区间中的数据拷贝赋值给本身。assign(n, elem); 将n个elem拷贝赋值给本身。list& operator=(const list &lst); 重载等号操作符swap(lst); 将lst与本身的元素互换。
总结:
#include<algorithm>
#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;
}
void test01()
{
list<int>L1;
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
printList(L1);
list<int>L2;
L2 = L1;
printList(L2);
list<int>L3;
L3.assign(L2.begin(), L2.end());
printList(L3);
list<int>L4;
L4.assign(10, 100);
printList(L4);
}
void test02()
{
list<int>L1;
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
list<int>L2;
L2.assign(10, 100);
cout << "交换前: " << endl;
printList(L1);
printList(L2);
L1.swap(L2);
cout << "交换后: " << endl;
printList(L1);
printList(L2);
}
int main()
{
test01();
test02();
system("pause");
return 0;
}
4. list大小操作
功能描述:
函数原型:
size(); 返回容器中元素的个数empty(); 判断容器是否为空resize(num); 重新指定容器的长度为num,若容器变长,则以默认值填充新位置;如果容器变短,则末尾超出容器长度的元素被删除。resize(num, elem); 重新指定容器的长度为num,若容器变长,则以elem值填充新位置;如果容器变短,则末尾超出容器长度的元素被删除。
总结:
- 判断是否为空 — empty
- 返回元素个数 — size
- 重新指定个数 — resize
#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;
}
void test01()
{
list<int>L1;
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
printList(L1);
if (L1.empty())
{
cout << "L1为空" << endl;
}
else
{
cout << "L1不为空" << endl;
cout << "L1的元素个数:" << L1.size() << endl;
}
L1.resize(10);
printList(L1);
L1.resize(2);
printList(L1);
}
int main()
{
test01();
system("pause");
return 0;
}
5. list插入与删除
功能描述:
函数原型:
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值匹配的元素
总结:
- 尾插 — push_back
- 尾删 — pop_back
- 头插 — push_front
- 头删 — pop_front
- 插入 — insert
- 删除 — erase
- 移除 — remove
- 清空 — clear
#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;
}
void test01()
{
list<int>L;
L.push_back(10);
L.push_back(20);
L.push_back(30);
L.push_front(100);
L.push_front(200);
L.push_front(300);
printList(L);
L.pop_back();
printList(L);
L.pop_front();
printList(L);
list<int>::iterator it = L.begin();
L.insert(++it, 1000);
printList(L);
it = L.begin();
L.erase(it);
printList(L);
L.push_back(10000);
L.push_back(10000);
L.push_back(10000);
L.push_back(10000);
printList(L);
L.remove(10000);
printList(L);
L.clear();
printList(L);
}
int main()
{
test01();
system("pause");
return 0;
}
6. list数据存取
功能描述:
函数原型:
front(); 返回第一个元素。back(); 返回最后一个元素。
总结:
- list容器中不可以通过[]或者at方式访问数据,因为存储空间不是连续的,且迭代器不支持随机访问
- list本质是个链表,每个数据不是用连续的线性空间存储数据,数据地址不是连续的,迭代器也是不支持随机访问,
- 返回第一个元素 — front
- 返回最后一个元素 — back
#include<iostream>
#include<list>
using namespace std;
void test01()
{
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;
list<int>::iterator it = L1.begin();
it++;
it--;
}
int main()
{
test01();
system("pause");
return 0;
}
7. list反转和排序
功能描述:
函数原型:
reverse(); 反转链表sort(); 链表排序
总结:
- 反转 — 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;
}
void test01()
{
list<int>L1;
L1.push_back(20);
L1.push_back(10);
L1.push_back(50);
L1.push_back(40);
L1.push_back(30);
cout << "反转前: " << endl;
printList(L1);
L1.reverse();
cout << "反转后: " << endl;
printList(L1);
}
bool myCompare(int v1, int v2)
{
return v1 > v2;
}
void test02()
{
list<int>L1;
L1.push_back(20);
L1.push_back(10);
L1.push_back(50);
L1.push_back(40);
L1.push_back(30);
cout << "排序前: " << endl;
printList(L1);
L1.sort();
cout << "升序排序后: " << endl;
printList(L1);
L1.sort(myCompare);
cout << "降序排序后: " << endl;
printList(L1);
}
int main()
{
test01();
test02();
system("pause");
return 0;
}
8. list排序案例
- 案例描述:将Person自定义数据类型进行排序,Person中属性有姓名、年龄、身高
- 排序规则:按照年龄进行升序,如果年龄相同按照身高进行降序
#include<iostream>
#include<list>
#include<string>
using namespace std;
class Person
{
public:
Person(string name, int age, int height)
{
this->m_Name = name;
this->m_Age = age;
this->m_Height = height;
}
string m_Name;
int m_Age;
int m_Height;
};
bool comparePerson(Person &p1,Person &p2)
{
if (p1.m_Age == p2.m_Age)
{
return p1.m_Height > p2.m_Height;
}
else
{
return p1.m_Age < p2.m_Age;
}
}
void test01()
{
list<Person>L;
Person p1("刘备", 35, 175);
Person p2("曹操", 45, 180);
Person p3("孙权", 40, 170);
Person p4("赵云", 25, 190);
Person p5("张飞", 35, 160);
Person p6("关羽", 35, 200);
L.push_back(p1);
L.push_back(p2);
L.push_back(p3);
L.push_back(p4);
L.push_back(p5);
L.push_back(p6);
cout << "排序前:" << endl;
for (list<Person>::iterator it = L.begin(); it != L.end(); it++)
{
cout << "姓名: " << (*it).m_Name << " 年龄: " << it->m_Age << " 身高: " << it->m_Height << endl;
}
cout << "----------------------------------" << endl;
cout << "排序后:" << endl;
L.sort(comparePerson);
for (list<Person>::iterator it = L.begin(); it != L.end(); it++)
{
cout << "姓名: " << (*it).m_Name << " 年龄: " << it->m_Age << " 身高: " << it->m_Height << endl;
}
}
int main()
{
test01();
system("pause");
return 0;
}
|