一.链表list

1.创建

list<int> iNum

2.插入

①尾插法：push_back(data)

iNum.push_back(1);

②头插法:  push_front(data)

iNum.push_front(3);//头插法

3.遍历

①不删除的方式遍历

即用迭代器的方式进行遍历

list<int>::iterator iter;
for(iter=iNum.begin();iter!=iNum.end();iter++)
{
    cout<<*iter<<" ";
}

②删除方式遍历

(可以从头部读一个删一个，也可以在尾部进行同样的操作，用back()访问元素&用pop_back进行删除)

while(!iNum.empty())
{
    cout<<iNum.front()<<"  ";
    iNum.pop_front();  //头部删除
}

4.指定位置操作

函数原型：iterator find(iterator begin,iterator end,data);返回的是一个迭代器，用auto偷懒(

find没找的话，将返回end()所指向的位置。

//函数原型：iterator find(iterator begin,iterator end,data);
auto result=find(iNum.begin(),iNum.end(),2);
//返回的是一个迭代器类型,此处是list<int>::iterator 类型
//若没有找到，就是返回end结束的位置
if(result==iNum.end())
{
    cout<<"not find"<<endl;
}
iNum.insert(result,100);//该函数的作用是在result这个迭代器所指向的位置的前面插入100

insert()需要传入两个参数，一个是迭代器类型，一个是需要插入的数据。插入的位置是在迭代器所指向位置的前面进行插入，若需要在迭代器所指向位置后面进行插入，给这个迭代器位置+1即可。

5.删除函数

①iNum.erase(迭代器)    

会删除迭代器所指向的位置中的元素，然后原迭代器删除，返回一个新的迭代器，是指向原来所删除位置的下一个位置！！！(ps.  6.22终于理解了python列表的range()中的pop为什么删不干净了)

②区分三种写法(因为erase只能删除一个位置，所以此处需要删除所有指定的值)--"相同元素删除"

写法一(×)：

int array[4]={1,2,2,3};
list<int>data;
for(list<int>::iterator iter=data.begin();iter!=data.end();iter++)
{
    if(*iter==2)
    {
        data.erase(iter);
    }
}

报错：

 原因：当前迭代器已经被删除了，它无法再去做++运算。

改进----

写法二(×)：

int array[4]={1,2,2,3};
list<int>data;
for(list<int>::iterator iter=data.begin();iter!=data.end();iter++)
{
    if(*iter==2)
    {
        iter=data.erase(iter);
    }
}

虽然不报错了。实际上iter在第一次被找到并按删除时，本身删完之后会++，在for里面也会++所以会跳过第一个2后面的2，于是会漏删一个。(删不干净)

写法三（√）：正确写法。

int array[4]={1,2,2,3};
list<int>data;
for(list<int>::iterator iter=data.begin();iter!=data.end();)
{
    if(*iter==2)
    {
        iter=data.erase(iter);
    }
    else
    {
        iter++;
    }
 
}

6.其他操作：

①reverse()   翻转链表函数。

②sort()         默认从小到大进行排序  

#include<functional>
iNum.sort(less<int>());
iNum.sort(greater<int>());

 上面代码块中(需要包含头文件functional，less和greater都是类，()是里面被运算符重载过的)

        第一行是从小到大进行排序       <  -------less

        第二行是从大到小进行排序       > -------greater

-------------以上:排序准则------------------

③swap()       交换

7.操作自定义类型数据。

list是无参构造，不能定长。

需要注意的几个问题

①按照姓名进行查找find的写法(必须要自己写重载函数->需要按照什么查找就在重载函数里面按照该属性去实现。)

②按照age ||  name排序

        i)重载写法（利用已有的比较准则）(需要按照哪一个属性进行重载，就写哪一个重载)

mmDate.sort(less<int>());//需要重载<
mmDate.sort(greater<int>());//需要重载>

        ii)不采用重载方式，自己写比较准则

//比较准则是一个函数指针，该函数的返回值是bool类型，两个参数
bool compareByName(const MM&object1,const MM& object2)//比较准则
{
    return object1.getName()<object2.getName();
}
mmDate.sort(compareByName);

操作自定义类型数据相关代码：

//操作自定义类型数据
class MM 
{
public:
	MM(string name, int age, int num) :name(name), age(age), num(num) {}
	void print() 
	{
		cout << name << "\t" << age << "\t" << num << endl;
	}
	bool operator==(const string& name) const
	{
		return this->name == name;
	}
	bool operator<(const MM& object) const 
	{
		return this->name < object.name;
	}
	string getName() const
	{
		return name;
	}
	int getAge() const
	{
		return age;
	}
protected:
	string name;
	int age;
	int num;
};
bool compareByName(const MM& object1, const MM& object2) 
{
	return object1.getName() < object2.getName();
}
bool compareByAge(const MM& object1, const MM& object2)
{
	return object1.getAge() < object2.getAge();
}
void testUserData() 
{
	list<MM> mmData;
	string name;
	int age;
	int num;
	while (1) 
	{
		cout << "input MM:" << endl;
		cin >> name >> age >> num;
		mmData.push_back(MM(name, age, num));
		cout << "是否继续输入？" << endl;
		while (cin.get() != '\n');
		if (cin.get() == 'n')
			break;
	}
	cout << "姓名\t年龄\t编号" << endl;
	for (MM v : mmData) 
	{
		v.print();
	}
	//二进制“==”: 没有找到接受“MM”类型的左操作数的运算符(或没有可接受的转换)
	auto result = find(mmData.begin(), mmData.end(), "name1");
	//重载方式
	mmData.sort(less<MM>());		//重载<  
	//mmData.sort(greater<MM>());	//重载>
	//不采用重载方式，需要自己写比较准则
	mmData.sort(compareByName);
	mmData.sort(compareByAge);
}

注意：重载函数的写法与需求。

这一行，我们的目标是按照姓名进行查找name1对应的位置， 在MM类中需要写的重载函数中传入的参数应该是const string类型！！！ 而非一个对象！！！

 二、栈stack

1.栈的相关原理：先进后出    注：无迭代器，是一个适配器

2.相关操作：

①push(data)

②pop():  删除操作（无指定位置删除or插入）

③top() ：获取栈顶元素

④size()和empty()

#include <stack>
#include <iostream>
#include <string>
using namespace std;
void testStack() 
{
	//穿脱原则
	//FILO  
	//1 2 3 
	//3 2 1 
	//push(data)
	//pop()  删除
	//top()  获取栈顶元素
	//size() empty();
	stack<int> intStack;
	for (int i = 0; i < 3; i++) 
	{
		intStack.push(i);
	}
	while (!intStack.empty()) 
	{
		cout << intStack.top() << "\t";
		intStack.pop();
	}
	cout << endl;
}

3.应用：①中缀表达式的转换；②将一个数字转成二进制(代码见下)

void NumTobinary(int data) 
{
	stack<int> bin;
	while (data) 
	{
		bin.push(data % 2);
		data = data / 2;
	}
	if (bin.size() < 8) 
	{
		for (int i = bin.size(); i < 8; i++) 
		{
			bin.push(0);
		}
	}
	while (!bin.empty()) 
	{
		cout << bin.top();
		bin.pop();
	}
	cout << endl;
	//中缀和后缀表达式资料看看
	//a+b 中缀
	//ab+
	//a+b*c+d;
}

 三、双向队列deque

(即可代表栈,也可以代表队列)->用双向链表也可以描述这一操作

1.插入操作同list(①尾插法②头插法)

	deque<int> deData;
	for (int i = 0; i < 3; i++) 
	{
		deData.push_back(i);		//尾插法入队
		deData.push_front(i);		//头插法入队
	}

2.此队列既可以从头部出来，也可以从尾部出来

①从头出来

//从头出来
void pop_front_dequeue(deque<int> dData) 
{
	while (!dData.empty()) 
	{
		cout << dData.front()<<" ";
		dData.pop_front();
	}
	cout << endl;
}

②从尾部出来

//从尾出来
void pop_back_dequeue(deque<int> dData)
{
	while (!dData.empty())
	{
		cout << dData.back() << " ";
		dData.pop_back();
	}
	cout << endl;
}

四、普通队列 queue

双向队列用的较多(速度更快)

1.原理：先进先出

2.入队：push(data)

3.获取队头元素: front()

4.出队：pop()

（注：若不想删除原容器改动，那么就函数传参生成拷贝本操作即可。）

5.应用：层次遍历二叉树BFS(广度优先搜索)

五、优先队列 priority_queue

1.头文件可以写以下两个之一

#include<concurrent_priority_queue.h>
#include<queue>

2.原理：需要另外一个容器充当容量（常用vector当做容器(无需传参数)，array还需要传参数）

(原型：第一个参数是存储的数据类型，第二个参数是容器(中间的那个=号是缺省值)，第三个参数是排序准则，第四个个参数是类名)

template <class _Ty,class _Container = vector<_Ty>,class _Pr = less<_Ty>>
class my_priority_queue
{
public:
 
protected:
 
};

按照特定的方式进行出队（按照数据的优先权出队）其实就是排好序再出队。

3.创建优先队列的三种方式：

//默认的方式，一级下面三种 都一样，大的先出队
	priority_queue<int> pqData;
	priority_queue<int,vector<int>> pqData2;			//默认排序准则
	priority_queue<int,vector<int>,less<int>> pqData3;	//所有参数都完整

4.入队：push()

pqData.push(12);
	pqData.push(0);
	pqData.push(34);

5.出队是默认从大到小(大的先出队)->default:  less<int>  (区别sort)

priority_queue<int> pqData;
while (!pqData.empty()) 
	{
		cout << pqData.top()<<" ";
		pqData.pop();		//出队
	}

若想让小的先出队 排序准则传参为  greater<int>

priority_queue<int, vector<int>, greater<int>> pqDataG;	
	pqDataG.push(12);
	pqDataG.push(0);
	pqDataG.push(34);
	while (!pqDataG.empty())
	{
		cout << pqDataG.top() << " ";
		pqDataG.pop();		//出队
	}

6.应用：贪心算法、Huffman树