摘要：structPoint{intx;inty;};Pointp={1,2};structListNode{intval;ListNode*next;ListNode(intx):val(x),next(NULL){}//节点构造函数 };
C++数据结构分为：原生数据结构 和 STL(标准模板库)
原生数据结构
1、数组 Array
连续内存空间、支持随机访问，适合存储固定大小数据，访问速度快；
固定大小，插入删除效率低
intarr[5]={1,2,3,4,5};a[0]=1;2、结构体struct
将多种不同类型的数据组合在一起，形成自定义数据结构；
不支持复杂功能
structPoint{intx;inty;};Pointp={1,2};structListNode{intval;ListNode*next;ListNode(intx):val(x),next(NULL){}//节点构造函数 };3、指针与动态内存分配
使用new和delete动态分配内存和释放内存，灵活性该，可动态调整大小；容易产生内存泄漏，操作复杂
int*ptr=newint[10];deleteptr;STL(标准模板库)
1、向量 std::vector
动态数组，支持自动扩容，随机访问快，插入删除操作灵活；
在中间插入和删除效率不高
usingnamespacestd;vectorvec={1,2,3};vec.push_back(4);//添加元素 vec.erase(vec.begin+1);//删除元素2、链表 std::list
双向链表，插入和删除效率高；
不支持随机访问
usingnamespacestd;listlst={1,2,3};lst.push_back(4);//添加到末尾 lst.pop_front;//删除第一个元素3、集合 set / unordered_set
存储不重复元素（会自动去重），set有序，unordered_set无序，查找效率高；
set插入较慢usingnamespacestd;sets={3,1,2};s.insert(4);//插入元素 s.erase(1);//删除元素 unordered_setud_s={2,1,3};4、映射 map / unordered_map
键值对，map有序，unordered_map无序，适合较快查找键值对；
map插入较慢usingnamespacestd;mapm;m[1]="one";m[2]="two";5、双端队列 deque
双端动态数组，支持在两端插入和删除，两端操作效率高；
比vector占内存
usingnamespacestd;dequedq={1,2,3};dq.push_front(0);//前端插入 dq.push_back(4);//后端插入6、栈 stack
后进先出，LIFO，适合模拟递归、括号匹配等；
只能从栈顶操作
usingnamespacestd;stackst;st.push(1);//入栈 st.pop;//出栈7、队列 queue / priority_queue
queue先进先出FIFO，priority_queue按优先级出队，适合排队、任务调度等；
usingnamespacestd;queueq;q.push(1);//入队 q.pop;//出队STL有多个版本
1、HP STL
C++ STL的第一个实现版本，开放源代码；其他版本的C++ STL一般是以HP STL为蓝本实现出来的
2、P.J.Plauger STL
参照HP STL实现，Visual C++编译器使用，不开源
3、SGI STL
参照HP STL实现，Linux的C++编译器GCC使用，开源，源码可读性甚高
SGI STL的 栈
提供 push 和 pop 等接口，所有元素都是 先进后出 规则
不提供走访功能，不提供迭代器(iteator)，不能像set或map那样用迭代器来遍历
以地层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的(可以控制使用哪种容器来实现栈的功能)
STL中 栈 往往不被归类为 容器，被归类为 container adapter（容器适配器）
栈 的底层实现可以是vector，deque，list，主要就是数组和链表的底层实现
SGI STL 没有指定底层容器的话，默认以 deque为缺省情况下 栈 的底层结构
deque是双向队列，封住一端，就变成了栈
// 指定vector为底层容器的栈 std::stack>third;SGI STL 没有指定底层容器的话，默认以 deuqe为缺省情况下 队列 的底层结构
队列，先进先出，不允许遍历行为，不提供迭代器
// 指定 list 为底层容器的 队列 std::queue>third；栈 的使用
#includeusingnamespacestd;// 创建存储int型数据的栈 stackst;主要成员函数：
1、push(x) 将元素 x 压入栈顶（void）
2、pop 移除栈顶元素，不返回元素（void）
4、empty 检查栈是否为空格，返回true或false，（bool）5、size 返回栈中元素的个数（int）
6、emplace(x) 直接构造元素到栈顶，避免拷贝开销（C++11起）
用栈实现队列
classMyQueue{public://创建两个栈，一个入栈一个出栈 stackst_in;stackst_out;MyQueue{}voidpush(intx){st_in.push(x);}intpop{if(st_out.empty==true){while(st_in.empty!=true){st_out.push(st_in.top);st_in.pop;}}intresult=st_out.top;st_out.pop;returnresult;}intpeek{if(st_out.empty==true){while(st_in.empty!=true){st_out.push(st_in.top);st_in.pop;}}intresult=st_out.top;returnresult;}boolempty{if(st_in.empty==true&&st_out.empty==true){returntrue;}returnfalse;}};栈是一个端口，队列是两个端口；使用两个栈来实现队列，一个栈专门负责入队列，另一个栈专门负责出队列
入队列和入栈一样
出队列，需要注意，每次都要检查了出队列栈里面有没有元素，有的话就直接输出那个就行；如果没有，这时候需要把入队列栈里面的所有元素都搬移到出队列栈，不然下一个进入入队列栈的元素就会捣乱顺序
判断是否为空，也就是两个栈都要为空
注：因为 peek 和 pop 的功能非常相似，实际上 peek 可以通过复用 pop 然后再次把输出的元素放回去就行
注：复用 比 直接复制粘贴 好！
intpeek{intres=this->pop;// 直接使用已有的pop函数 stOut.push(res);// 因为pop函数弹出了元素res，所以再添加回去 returnres;}void push(int x) 将元素 x 推到队列的末尾
int pop 从队列的开头移除并返回元素
int peek 返回队列开头的元素
boolean empty如果队列为空，返回true；否则，返回来指定函数明确表示这个函数是属于当前类的成员函数，解决名字冲突或模版推导问题
1、名字冲突
this->#includeclassBase{public:intpop{return10;}};classDerived:publicBase{public:intpop;// 这里是一个成员变量 voidexample{intpop=20;// 外部作用域的 pop 变量 // 使用 this-> 可以明确访问 Base 类的 pop 函数 intres=this->pop;// 调用 Base 类的 pop 函数 std::cout如果没有this->，编译器可能会认为pop是访问成员变量pop，而不是基类在模版类中，如果成员函数依赖于类的模版参数 并且 类内部有成员变量 或 函数 与外部名字 重名时，this->#includetemplateclassMyClass{public:Tvalue;voidpop{std::coutpop;// 使用 this-> 明确调用 pop 函数 }};intmain{MyClassobj;obj.value=42;obj.example;// 调用 example，从而调用 pop return0;}队列 的使用
#includeusingnamespacestd;// 创建int数据类型的队列 queueq;主要成员函数：
1、push(x) 将元素x入队，从队列头部放到队列的尾部（队尾）(void)
2、pop 移除队列尾部的元素（队尾），不返回元素（void)
3、front 返回队列尾部的元素，但不移除，返回元素
4、back 返回队列头部的元素，但不移除，返回元素
5、empty 检查队列是否为空，返回true或false6、size 返回队列中元素个数
用队列实现栈
classMyStack{public:queueq_in;queueq_temp;MyStack{}voidpush(intx){q_in.push(x);}intpop{intresult;intnums=0;while(q_in.empty==false){result=q_in.front;q_in.pop;q_temp.push(result);nums++;}nums-=1;while(nums--){inttemp=q_temp.front;q_temp.pop;q_in.push(temp);}q_temp.pop;returnresult;}inttop{intresult=this->pop;q_in.push(result);returnresult;}boolempty{if(q_in.empty==true&&q_temp.empty==true){returntrue;}returnfalse;}};要实现的栈是先进后出，已有的队列是先进先出
在push，也就是加入这个环节是一样的
关键是在于pop这个环节，也就是输出并删除元素；
pop主要思路：栈要输出的第一个其实也就是队列要输出的最后一个，先把出了最后一个的所有其他元素输出后放到temp队列中，然后输出删除原队列中的最后一个元素，也就实现了输出删除栈的第一个元素，然后再把刚刚的元素放回来
top的实现，和在栈中实现队列一样，先使用pop再把删除的元素放回来
优化，仅用一个队列就能实现；在pop的时候不需要放到temp队列里面，直接又从头部放回来，只需要注意操作的元素个数就行了
classMyStack{public:queueq;MyStack{}voidpush(intx){q.push(x);}intpop{intsize=q.size;size--;while(size--){q.push(q.front);q.pop;}intresult=q.front;q.pop;returnresult;}inttop{intresult=this->pop;q.push(result);returnresult;}boolempty{returnq.empty;}};void push(int x) 将元素 x 压入栈顶。
int pop 移除并返回栈顶元素。
int top 返回栈顶元素。
boolean empty如果栈是空的，返回true；否则，返回。有效的括号
boolisValid(strings){stackst;for(inti=0;i左右括号的顺序要相互匹配，内层的在内层，外层的在外层，这与栈的进出顺序一致
识别到左括号就放到栈里面，识别到右括号就出栈一个元素对比是不是匹配的
注：在识别到右括号时(也就是else情况)，要先判断栈是不是为空，因为可能没有对应的左括号
注：最后还需要判断栈是不是为空，因为可能有左括号没有被匹配
注：最后那个 if 的判断条件是根据ACISS值来的
符号ASCII 值(40)41[91]93{123}125删除字符串中的所有相邻重复项
stringremoveDuplicates(strings){stackst;for(inti=0;i先往栈中填一个字符，然后看下一个字符和这个是不是一样的，如果是一样就得删除栈中的这个字符，同时这个下一个字符也会因为 i++ 自动被删掉
如果下一个字符是不同，就会被存入栈中
这样直到遍历完整个字符串，这时候在栈中的就是完全没有相邻元素是相同
但是因为栈的取出顺序是先进后出，最后还需要reverse颠倒一下
优化改进，直接使用string字符串来模拟栈的行为
stringremoveDuplicates(strings){stringresult;for(inti=0;i注：关键点，使用.back和.push_back以及pop_back，保证每次都是只对字符串的尾部这个方向操作，就像一个反向的栈一样，这样最后就不需要从栈中提前和反向了string字符串的成员函数
1、size或length，返回字符串长度
2、empty，判断字符串是否为空
3、at，通过下标访问字符（相比直接用中括号，at会进行越界检查）
4、front，获取字符串中的第一个字符
5、back，获取字符串中的最后一个字符
6、push_back，在字符串的末尾添加一个字符
7、pop_back，删除字符串的最后一个字符
8、insert，在指定位置插入管字符或字符串
9、erase，删除指定位置的字符或子字符串
10、clear，情况字符串内存，将字符串长度size设置为0
11、append，将另一个字符串或字符追加到字符串末尾
12、substr，提取子字符串，返回从指定位置开始，指定长度的子字符串
std::string::npos14、rfind，查找子字符串或字符串，返回最后一次出现的位置
15、find_first_of，查找字符串中第一个匹配给定字符集的字符
16、find_lost_of，查找字符串中最后一个匹配给定字符集的字符
17、find_first_not_of，查找第一个不匹配给定字符集的字符
18、find_last_not_of，查找最后一个不匹配给定字符集的字符
19、compare，比较当前字符串与另一个字符串的字典顺序，返回另一个整数，负值代表当前字符串小，正值代表当前字符串大，零值表示想等
20、c_str，返回C风格的字符串(const char*)
21、data，返回指向字符串数据的指针
22、swap，交换当前字符串与另一个字符串的内容
23、replace，替换字符串中的指定范围的字符或子字符串
24、resize，修改字符串的大小
逆波兰表达式求值
intevalRPN(vector&tokens){stackst;for(inti=0;i在不是计算符号的时候把数字存到栈里面，遇到计算符号拿出来两个进行计算，计算结果再放回去
注：这里面 if 的判断条件只能根据是不是计算符号，不能根据是不是数字；
因为这里面的数字是从-200到200的数字的字符串形式，在直接进行判断的时候，是 按字典序 对字符串进行对比的，string类型的比较是逐字进行的，根据字符的ASCII值进行大小判断
字符串的字典序对比 不适合用于数组比较，尤其是有正负符号的数值
滑动窗口的最大值
classSolution{private:classMyQueue{public:dequedq;intfront{returndq.front;}voidpop(intval){if(dq.empty==false&&dq.front==val){dq.pop_front;}}voidpush(intval){while(dq.empty==false&&dq.backmaxSlidingWindow(vector&nums,intk){vectorresult;MyQueuemq;for(inti=0;i这里面要自定义一个和滑动窗口功能类似的MyQueue，其模式为：
是一个双端队列，左侧为头(front)，右侧为尾(back)；一开始是空的，每次把一个nums数组的一个元素从尾巴像头部（从右口入，从右往左添加）；每次添加元素的时候，如果上一个元素比较小，就删除这个元素，直到上一个元素是更大的元素，如：
头 -> 尾，需要加入新元素4原队列：8 5 3 1现队列：8 5 4注：这个自定义的队列并不完全等同于滑动窗口，其中的元素只是滑动窗口中最大的几个元素（因为只需要求出最大值），任何时候这个队列中的最左侧元素就是队列里面的最大值，也就是滑动窗口中最大值
注：虽然MyQueue的front函数就是直接返回的front，但是这里面是不一样的，函数内的那个dq.front是对于双端队列数据类型dequeMyQueueMyQueue中的pop函数是在模拟滑动窗口移动的时候，原窗口位置最左侧的那个元素会被移除；这里使用if来判断，如果队列里面最左边的元素(最大的元素)就是实际上滑动窗口上最左侧的元素，这时候才删除这个元素，不然不执行操作MyQueue中的push函数通过if判断中的dq.back 就是用来消除队列中比当前元素要小的元素前K个高频元素
classSolution{private:classMyComparison{public:booloperator(constpair&lhs,constpairrhs){returnlhs.second>rhs.second;}};public:vectortopKFrequent(vector&nums,intk){unordered_mapmap;for(inti=0;i,vector
>,MyComparison>pq;for(unordered_map::iteratorit=map.begin;it!=map.end;it++){pq.push(*it);if(pq.size>k){pq.pop;}}vectorresult(k);for(inti=0;i整体思路：先使用map，存放每个元素和它对应出现的次数，其中元素值对应key，出现的次数对应；然后把的数据放到小顶堆中，这个小顶堆的大小保持只有 k 个元素，这样小顶堆中留下来的元素就是频率最高的几个class MyComparison是为重定义operator来自定义priority_queue实现小顶堆注：在使用了result(k)来初始化定义了vector的大小为k之后不要使用push_back来添加元素，这样不会被放到那个里面，如果是result;定义的就可以使用引用符号booloperator(constpair&lhs,constpair&rhs){}booloperator(constpairlhs,constpairrhs){}
priority_queue（最大堆）
STL里的一个容器适配器，实现了一个优先队列（或者叫做 堆）
优先队列，是一种数据结构，一般使用二叉堆实现，其中的元素按照优先级排列，支持 插入、查看以及删除堆顶元素
默认情况是 最大堆，堆顶的元素是优先级最高的元素
主要成员函数：
1、push(const T& val) 将元素val插入到队列中2、pop 删除堆顶元素
3、top 返回堆顶元素，不删除
4、empty 判断堆是否为空
5、size 返回堆的元素数量
priority_queuepq;pq.push(10);pq.push(20);pq.push(15);cout优先级比较器（默认是operator
比如，需要一个最小堆（堆顶元素是优先级最小的元素）
// 方法一 structmycomparison{booloperator(intlhs,intrhs){returnlhs>rhs;// 小的优先 }}// 方法二 classmycomparison{public:booloperator(intlhs,intrhs){returnlhs>rhs;// 小的优先 }}// 使用 intmain{priority_queue,mycomparision>pq;}priority_queue是优先队列队列的标准格式T，队列存储元素的数据类型，必须定义，如Container，底层容器类型，默认，可以定义Compare::unordered_map::iteratorit=map.begin;iterator是一种数据类型，表示迭代器，这里表示为在unordered_map中的迭代器pri_que.push(*it);it是一个迭代器，本质上是一个指针，指向容器中的一个元素使用解引用运算符来源：生活智慧谷
