一.stack栈
1.栈的介绍
stack 栈是一种只在一端(栈顶)进行数据插入(入栈)和删除(出栈)的数据结构,它满足后进
先出(LIFO)的特性。
使用push(入栈)将数据放入stack,使用pop(出栈)将元素从容器中移除。
栈的结构如图：
在头文件<stack>中，class stack定义如下：
namespace std{
template <typename T,
typename container = deque<T>>
class stack;
}第一个参数T代表类型,第二个参数用来定义stack内部存放数据的容器,默认为deque。之所以选择deque而非vector,是因为deque移除数据时可能会释放内存,并在插入数据需要扩容时不需要复制所有的数据。
std::stack<int> st;//定义一个元素类型为整数的栈stack 只是很单纯地把各项操作转化为内部容器对应的函数调用。你可以使用任何支持back()、push back()和pop back()成员函数的标准容器支持 stack。例如你可以使用vector或list 来存放数据:
stack<int,vector<int> st;注意：forword_list和array不可以作为容器
2.stack定义及初始化
#include <iostream>
#include<stack>
#include <vector>
#include <list>
using namespace std;
int main()
{
stack<char> s1;//创建一个默认的栈,最常用
stack<char，deque<char>>s2;//显示创建用deque保存数据的栈,和s1等价
stack<int，vector<int>>s3;//创建用vector保存数据的栈
stack<int，list<int>>s4;//创建用list保存数据的栈
return 0;
}3.常用操作
stack栈的操作比较简单，不支持迭代器和运算符
常用的成员函数及其函数原型：
//empty成员函数
void pop();//pop成员函数：出栈函数，删除栈顶元素
void push(const Type&_val);//push成员函数：入栈函数，往栈顶添加数据
size_type size()const;//size成员函数：返回栈的数据个数
//top成员函数，返回栈顶元素的引用二.queue队列
1.queue队列介绍
queue队列是一个先进先出的队列，从一段插入数据，另一端获取与删除数据
push() 入队，back()获取队尾元素的引用，pop()出队，front()获取队头元素的引用
queue的结构
namespace std{
template <typename T,
typename container =deque<T>>
class queue;
}第一个参数代表元素类型，第二个参数是queue内部存放函数的容器，默认使用deque
queue<int> q1;//包含int数据的q1实际上queue只是简单的把各项操作转为内部容器对应的函数调用。你可以使用支持front(),pop front(),back(),push back()操作的其它容器作为queue内部的容器。例如使用list作为内部容器的queue。
queue<int,list<int>> q2;//包含int数据的q2，内部存储数据的容器为list2.定义及初始化
#include <queue>
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int main()
{
queue<char> q1;//定义存放char数据的队列,内部使用默认deque容器
queue<char，deque<char>> q2;//同q1,显示说明用deque
// queue <int，vector<int>> q3;//定义存放int数据的队列,内部使用vector容器
//q3.push(10);//入队10，vector感觉可以,实际不可以
queue<int，list<int>> q4;//定义存放int数据的队列,内部使用list容器
return 0;
}注意：因为vector不支持pop_front，所以不能使用vector不能作为队列的容器
3.常用操作
queue队列操作简单,不支持迭代器和运算符,只要几个操作函数。
back成员函数
返回最后一个元素的引用。
empty成员函数
判断queue队列是否为空,是返回true,不是返回false.
front成员函数
返回第一个元素的引用。
pop成员函数
删除第一个元素(在队头处删除)。
push成员函数
将元素添加到队列(插入在队尾)。
size成员函数
返回queue队列元素的个数。
int main()
{
queue<int>cq;//创建一个int的空队列g
for(int i=0;i<10;i++)//入队0~9
q.push(i);cout<<"队列的数据个数:"<<q.size()<<endl;
cout <<"队头元素:"<<q.front()<<",队尾元素:"<<q.back()<< endl;
cout<<"出队"<< endl;while(!q.empty())//只要q不空,循环继续
{
cout<<q.front()<<endl;//输出队头元素
q.pop();
}return 0;
}三.priority queue优先级队列
1.priority queue优先级队列介绍
priority queue优先级队列,它的接口和queue非常相似,有入队push(),获取第一个元素top(),pop删除第一个元素。这里的第一个元素并不是第一个放入的元素,而是"优先级最高“的元素。
priority queue内的元素已经根据其值进行了排序。当然你可以通过参数指定一个排序准则,默认的排序是升序排列。所谓的第一个元素就是当前"数值最大的元素”(默认的vector第一个"最大值”元素保存在最后,因为vector尾删效率高)。如果同时存在多个数值最大的元素,我们无法确定哪一个在前哪一个在后。
其内部数据结构为:大根堆
不能使用list作为其容器
priority queue也是定义在头文件<queue>中
结构如下：
namespace std（
template<typename T,
typename container=vector<Type>
typename Compare=less<typename Container::value type>>
class priority_queue;
}第一个参数T是元素类型,第二个参数为内部存放元素的容器,默认为vector,第三个参数是排序规则,默认是升序(less)。
下面定义一个int的priority queue。
priority_queue<int,deque<int>> pq2;//创建一个int的优先级队列，使用deque作为存储数据的容器下面定义一个使用降序排序规则的优先级队列：
priority_queue<int,vector<int>,greater<int>> pq3;2.定义及初始化
#include <queue>
#include <iostream>
using namespace std;
int main()
{
priority_queue<int>q1;//创建一个保存int的空优先级队列
if(q1.empty())
cout<<"q1是空的,它的数据个数为:"<<q1.size()<<endl;
//创建一个保存int,且用deque保存内部数据的优先级队列(默认为升序)
priority queue <int,deque <int>>q2;
q2.push(5);//入队
q2.push(15);//入队
q2.push(10);//入队
cout<<"q2的数据:";
while(!q2.empty())//只要q2不为空,循环继续
{
cout<< q2.top()<<"";//输出第一个元素的值(最大)
q2.pop();//删除第一个元素
}
cout << endl;
//创建保存int,用vector保存内部数据且降序的优先级队列
priority queue <int,vector<int>,greater<int>> q3,
q3.push(2);//入队
q3.push(1);//入队
q3.push(3);//入队
cout<<"q3的数据:";
while(!g3.empty())
{
cout << q3.top()<<"";//输出第一个元素的值(最小)
q3.pop();//删除第一个元素
}
cout << endl;
q1.push(100);
q1.push(200);
cout<<"q4的数据：";
while(!q4.empty())
{
cout<< q4.top()<<"";
q4.pop();
}
cout << endl;
//利用迭代器创建优先级队列
vector <int> v5{10,30,20,40};
priority_queue <int>q5(v5.begin(),v5.end());
cout<<"q5的数据:";
while(!q5.empty())
{
cout << q5.top()<<" ";
q5.pop();
}
cout << endl;
return 0;
}3.常用操作
priority queue优先级队列的操作比较简单,只要几个简单的成员函数。
empty成员函数
判断优先级队列是否为空。是返回true,不是返回false。
pop成员函数
把第一个元素从队列删除
push成员函数
往优先级队列中插入一个数据。
size成员函数
返回优先级队列数据个数。
top成员函数
返回第一个元素的引用。
int main()
{
priority_queue<int> q;//创建一个空优先级队列
if(q.empty())
cout<<"q是一个空队"<<endl;
q.push(3);
q.push(2);
q.push(5);
q.push(4);
q.push(1);
cout<<"插入5个数据之后,当前的数据个数为"<<q.size()<< endl;
cout<<"依次出队的数据为:";
while(!q.empty())//只要q1不为空,循环继续
{
cout << q.top()<<" ";
q.pop();
}
return 0;
}4.深入priority queue
其内部是使用STL的堆排序heap算法
下面是queue文件部分源码
template<class Ty,class _Container =vector< Ty>,
class_Pr = less<typename _Container::value_type>>
class priority_queue
{
protected:
_Container c{};//容器
_Prcomp{};//比较函数对象
public:
template <class _Alloc,enable_if_t<uses_allocator_v<_container,_Alloc>,int>= 0>
priority_queue(const _Pr&_Pred,const _Container&_Cont,const _Alloc& _AI):
c(_Cont，_Al)，comp(_Pred)//构造函数
{
make_heap(c.begin()，c.end()，comp);//变成堆(默认为大根堆)
}
void push(const value_type& Val){
c.push_back(_Val);
push_heap(c.begin()，c.end()，comp);//往堆增加一个元素
}
void pop(){
pop_heap(c.begin()，c.end()，comp);//从堆中删除一个元素
c.pop_back();
}
}可以看到其内部使用heap函数