C++学习笔记（二十）

一、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();? ? ? ? // 返回栈的大小

#include <iostream>
#include <stack>

using namespace std;

void test01()
{
	stack<int>s;

	// 入栈
	s.push(10);
	s.push(20);
	s.push(30);
	s.push(40);
	s.push(50);

	// 查看栈的大小
	cout << "栈的大小为:" << s.size() << endl;

	// 只要栈不为空，查看栈顶，并且执行出栈操作
	while (!s.empty())
	{
		// 查看栈顶元素
		cout << "栈顶元素为:" << s.top() << endl;

		// 出栈
		s.pop();
	}
	cout << "栈的大小为:" << s.size() << endl;
}

int main(int argc, char* argv[])
{
	test01();
	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();? ? ? ? // 返回队列的大小

#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("刘备", 50);
	Person p2("关羽", 40);
	Person p3("张飞", 30);
	Person p4("赵云", 20);

	// 入栈
	q.push(p1);
	q.push(p2);
	q.push(p3);
	q.push(p4);

	// 查看队列的大小
	cout << "栈的大小为:" << q.size() << endl;

	// 只要队列不为空，查看队头队尾，并且执行出队操作
	while (!q.empty())
	{
		cout << "----------------" << endl;
		// 查看队头队尾元素
		cout << "队头:" << endl;
		cout << "姓名:" << q.front().m_Name << " " << "年龄:" << q.front().m_Age << endl;
		cout << "队尾:" << endl;
		cout << "姓名:" << q.back().m_Name << " " << "年龄:" << q.back().m_Age << endl;

		// 出队
		q.pop();
	}
	cout << "队列的大小为:" << q.size() << endl;
}

int main(int argc, char* argv[])
{
	test01();
	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);? ? ? ? // 拷贝构造函数

#include <iostream>
#include <list>

using namespace std;

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

void test01()
{
	list<int> l1;
	for (int i = 0; i < 10; i++)
	{
		l1.push_back(i);
	}
	printList(l1);

	list<int> l2(l1.begin(), l1.end());
	printList(l2);

	list<int> l3(10, 100);
	printList(l3);

	list<int> l4(l3);
	printList(l4);
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

3. list赋值与交换

函数原型：

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(list<int>& l)
{
	for (list<int>::iterator it = l.begin(); it != l.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	list<int> l1;
	for (int i = 0; i < 10; i++)
	{
		l1.push_back(i);
	}
	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);

	list<int> l5;
	l5.push_back(1);
	l5.push_back(1);
	l5.push_back(1);
	l5.push_back(1);
	l5.push_back(1);
	cout << "交换前:" << endl;
	cout << "l4:";
	printList(l4);
	cout << "l5:";
	printList(l5);

	l5.swap(l4);
	cout << "交换后:" << endl;
	cout << "l4:";
	printList(l4);
	cout << "l5:";
	printList(l5);
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

4. list大小操作

函数原型：

size();? ? ? ? // 返回容器中元素的个数

empty();? ? ? ? // 判断容器是否为空

resize(num);? ? ? ? // 重新指定容器的长度为num，若容器变长，则以默认值填充新位置

? ? ? ? ? ? ? ? ? ???????? ?// 如果容器变短，则末尾超出容器长度的元素被删除

resize(num, elem);? ? ? ? // 重新指定容器的长度为num，若容器变长，则以elem填充新位置

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ?// 如果容器变短，则末尾超出容器长度的元素被删除

#include <iostream>
#include <list>

using namespace std;

void printList(list<int>& l)
{
	for (list<int>::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);
	l1.push_back(50);
	printList(l1);

	// 判断容器是否为空
	if (l1.empty())
	{
		cout << "l1为空..." << endl;
	}
	else
	{
		cout << "l1不为空..." << endl;
		cout << "l1的元素个数为:" << l1.size() << endl;
	}

	// 重新指定大小
	l1.resize(10);
	printList(l1);

	l1.resize(20, 100);
	printList(l1);

	l1.resize(2);
	printList(l1);
}

int main(int argc, char* argv[])
{
	test01();
	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值匹配的元素

#include <iostream>
#include <list>

using namespace std;

void printList(list<int>& l)
{
	for (list<int>::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);
	l1.push_back(50);
	printList(l1);

	// 头插
	l1.push_front(100);
	l1.push_front(200);
	l1.push_front(300);
	printList(l1);
	
	// 尾删,头删
	l1.pop_back();
	l1.pop_front();
	printList(l1);

	// 插入
	list<int>::iterator it = l1.begin();
	l1.insert(++(++it), 1000);
	printList(l1);

	// erase删除
	it = l1.begin();
	l1.erase(it);
	printList(l1);

	// remove删除
	l1.push_back(1000);
	printList(l1);
	l1.remove(1000);
	printList(l1);

	// 清空
	l1.clear();
	printList(l1);
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

6. list数据存取

函数原型：

front();? ? ? ? // 返回第一个元素

back();? ? ? ? // 返回最后一个元素

#include <iostream>
#include <list>

using namespace std;

void printList(list<int>& l)
{
	for (list<int>::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);
	l1.push_back(50);
	printList(l1);

	cout << "第一个元素是:" << l1.front() << endl;
	cout << "最后一个元素是:" << l1.back() << endl;

	// 验证迭代器是不支持随机访问的
	list<int>::iterator it = l1.begin();
	// 支持双向
	cout << *++it << endl;
	cout << *--it << endl;
	// it = it + 1; 不支持随机访问
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

7. list反转和排序

函数原型：

reverse();? ? ? ? // 反转链表

sort();? ? ? ? // 排序链表

#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

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

bool myCompare(int num1, int num2)
{
	return num1 > num2;
}

void test01()
{
	list<int> l1;
	l1.push_back(20);
	l1.push_back(50);
	l1.push_back(30);
	l1.push_back(10);
	l1.push_back(40);
	
	cout << "排序前:";
	printList(l1);

	// 排序
	// 所有不支持随机访问迭代器的容器,不可以用标准算法
	// 不支持随机访问迭代器的容器,内部会提供对应的一些算法
	l1.sort();	// 默认排序规则,从小到大,升序
	cout << "升序排序后:";
	printList(l1);
	l1.sort(myCompare);	// 默认排序规则,从小到大,升序
	cout << "降序排序后:";
	printList(l1);

	cout << "反转前:";
	printList(l1);

	// 反转
	l1.reverse();
	cout << "反转后:";
	printList(l1);
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}

8. list排序案例

案例描述：将Person自定义数据类型进行排序，Person中属性有姓名，年龄，身高

排序规则：按照年龄进行升序排序，如果年龄相同贼按照身高进行降序排序

#include <iostream>
#include <list>
#include <string>
#include <algorithm>

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;
	}
	return p1.m_Age < p2.m_Age;
}

void test01()
{
	// 创建list容器
	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;
	}

	// 排序后
	l.sort(comparePerson);
	cout << "——————排序后——————" << endl;
	for (list<Person>::iterator it = l.begin(); it != l.end(); it++)
	{
		cout << "姓名:" << (*it).m_Name << "  " << "年龄:" << it->m_Age << "  " << "身高:" << it->m_Height << endl;
	}
}

int main(int argc, char* argv[])
{
	test01();
	return 0;
}