本期我们将深入学习C++中关于STL容器的容器类型:stack(栈)和deque(队列)
作者本人的gitee:楼田莉子 (riko-lou-tian) - Gitee.com
目录
stack的介绍和官方文档
官方文档: stack - C++ 参考
stack的介绍
stack的构造函数
stack不支持迭代器遍历,因此stack也不支持范围for。
stack相关的函数
empty(判空)
push(入栈)
pop(出栈)
top(取栈顶元素 )
测试:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stack>
using namespace std;
void test1()
{
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
while (!s.empty())
{
cout << s.top() << " ";
s.pop();
}
cout << endl;
}
int main()
{
test1();
return 0;
}
结果为:
size
emplace
swap
stack的模拟实现
#pragma once
#include <iostream>
#include<vector>
#include<list>
#include<deque>
using namespace std;
namespace Boogiepop
{
//适配器/配接器 //用缺省值可以不传递第二个模板参数
template<class T, class container=deque<T>>
//适配器是用来实现转换的
//本质上是容器适配器
//用容器适配转换出来的
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
const T& top() const
{
return _con.back();
}
private:
container _con;
};
stack相关题目
1、最小栈
题目中“在常数时间内获取最小栈”意思是getmin()函数的时间复杂度是O(1).
答案:
class MinStack {
public:
MinStack()
{
}
void push(int val)
{
_st.push(val);
if(_minst.empty()||val<=_minst.top())
{
_minst.push(val);
}
}
void pop()
{
if(_st.top()==_minst.top())
{
_minst.pop();
}
_st.pop();
}
int top()
{
return _st.top();
}
int getMin()
{
return _minst.top();
}
private:
stack<int> _st;
stack<int> _minst;
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
2、栈的压入弹出序列
本题中从大小关系入手是没有意义的。
思路是模拟出入栈顺序跟出栈顺序匹配
思路如下:
1、pushi指向的数据入栈
2、持续地让栈中数据与popi比较。如果想等则popi++,出栈顶数据,直到为空或者不匹配。
3、重复1、2 步
核心原则:持续比较
结束条件:pushi走到尾部
class Solution
{
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pushV int整型vector
* @param popV int整型vector
* @return bool布尔型
*/
bool IsPopOrder(vector<int>& pushV, vector<int>& popV)
{
// write code here
stack<int> st;
size_t pushi=0,popi=0;
while(pushi<pushV.size())
{
//先入栈
st.push(pushV[pushi++]);
//尝试与出栈序列匹配
while(!st.empty()&&st.top()==popV[popi])
{
popi++;
st.pop();
}
}
return st.empty();
}
};
3、逆波兰表达式求值
逆波兰表达式的解释和扩展:【数据结构】你知道波兰表达式和逆波兰表达式吗?我才知道原来栈在表达式求值中还能这样使用……-腾讯云开发者社区-腾讯云 简单来说,计算机的运算表达式有三种:
中缀表达式(最常用的):运算数+运算符+运算数
前缀表达式:运算符+运算数+运算数
后缀表达式:运算数+运算数+运算符
所以本质上逆波兰表达式就是后缀表达式
后缀表达式运算符按优先级排列,而且要挨着要运算的运算数。
思路:
1、运算数入栈
2、如果是运算符,则出栈顶的两个数据,然后继续入栈
这里额外科普一个string的应用:将string转化为整数
答案:
class Solution {
public:
int evalRPN(vector<string>& tokens)
{
stack<int> st;
for(auto& str:tokens)
{
if(str=="+"||str=="-"||str=="*"||str=="/")
{
//遇到运算符要出栈两个运算数然后运算后入栈
int right=st.top();
st.pop();
int left=st.top();
st.pop();
switch(str[0])
{
case '+':
st.push(left+right);
break;
case '-':
st.push(left-right);
break;
case '*':
st.push(left*right);
break;
case '/':
st.push(left/right);
break;
default:
break;
}
}
else
{
//运算数入栈
st.push(stoi(str));
}
}
return st.top();
}
};
4、用栈实现队列
5、二叉树层序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root)
{
queue<TreeNode*>q;
int levelsize=0;//记录当前层数多少个数据
if(root)
{
q.push(root);
levelsize=1;
}
vector<vector<int>>vv;
//层序遍历
while(!q.empty())
{
vector<int>v;
//控制一层一层出
while(levelsize--)
{
TreeNode*front=q.front();
q.pop();
v.push_back(front->val);
if(front->left)
{
q.push(front->left);
}
if(front->right)
{
q.push(front->right);
}
}
vv.push_back(v);
//当前层出完了下一层节点都进队列,队列数据个数就是下一次节点个数
levelsize=q.size();
}
return vv;
}
};
这段代码的时间复杂度不是O(N^2)。因为队列进入和出只用了N次。所以实际上时间复杂度是O(N)
queue的介绍和官方文档
官方文档:
queue(单端队列)的介绍
queue构造函数
queue相关的函数
empty
size
front
back
push(入队列)
pop(出队列)
emplace
swap
测试:
void test1()
{
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
cout << q.front() << endl;
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
int main()
{
test1();
return 0;
}
答案:
queue的模拟实现
#pragma once
#include <iostream>
#include<vector>
#include<list>
#include<deque>
using namespace std;
namespace Boogiepop
{
//适配器/配接器 //用缺省值可以不传递第二个模板参数
template<class T, class container = deque<T>>
//适配器是用来实现转换的
//本质上是容器适配器
//用容器适配转换出来的
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
//_con.erase(_con.begin());效率比较低
_con.pop_front();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
const T& top() const
{
return _con.back();
}
private:
container _con;
};
}
deque的介绍和官方文档
官方文档:deque - C++ 参考
std::d eque - cppreference.com
deque(双端队列)的介绍
deque的结构图
deque的特殊之处:为什么模拟实现用deque
如上图所示,deque在功能上拥有vector和list的结合。
但是deque遍历的性能并不高效
vector
优点:
1下标随机访问,快;
2尾插尾删效率高
3、CPU高速缓存命中率高
缺点:
1头部、中间插入删除效率低下;
2插入空间不够要扩容,扩容有一定性能消耗,倍数扩容有一定空间浪费
list
优点:
1、任意位置均为O(1)复杂度的插入删除
2、按需申请释放内存
缺点:
1、不支持下标随机访问
2、CPU高速缓存命中率低,还存在缓存污染。
deque
优点:适合头尾插入删除,效率高;下标随机访问效率还不错(大量数据处理不如vector)
缺点:中间位置插入删除效率低,需要大量挪动数据。
相比于vector和list,性能都不够极致
[]下标随机访问的效率:
list<<deque<vector
那是否存在一种数据结构将两者的优点结合起来呢?deque。那么deque的底层结构是怎么样的呢?
我们可以创建一个buffer数组,每个数组由10个,然后创建一个指针数组
buffer数组的迭代器
以下是deque的功能介绍,了解即可。
deque初始
构造
析构
=运算符重载
迭代器
正向
反向
const正向
const反向
容器
size
max_size
resize
empty
shrink_to_fit
访问队列
[]运算符重载
at
front
back
deque的成员函数
push_back
push_front
pop_back
pop_front
insert
erase
swap
clear
emplace
emplace_front
emplace_back
deque非成员函数
关系运算符重载
swap(双队列)
priority_queue的介绍和官方文档
官方文档: priority_queue - C++ 参考
入数据随便入,出数据按优先级高的出队列。
而数据大的优先级高,优先出队列
测试:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
using namespace std;
int main()
{
priority_queue<int> pq;
//数据大的优先级高;
//优先级高的优先出队列
pq.push(5);
pq.push(3);
pq.push(8);
pq.push(1);
pq.push(6);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
结果为:
默认情况下priority_queue是大的数据优先级高。如果需要小的数据优先级高则需要通过仿函数控制。
而如下图所示
默认传递的是小于less的仿函数的时候,大的优先级高;因此反过来说,当我们传大于greater的仿函数的时候,小的优先级高
less和greater是标准库内的仿函数
官方文档:
priority_queue
void test_priority_queue()
{
priority_queue<int> pq1;
//数据大的优先级高;
//默认情况下优先级高的优先出队列
//控制小的数据优先级高需要仿函数
priority_queue<int, vector<int>, greater<int>> pq2;
//less和greater是标准库函数
//greater<int>是仿函数,表示优先级高的元素优先出队列
//小的元素优先级高,所以优先出队列
pq1.push(5);
pq1.push(3);
pq1.push(8);
pq1.push(1);
pq1.push(6);
while (!pq1.empty())
{
cout << pq1.top() << " ";
pq1.pop();
}
cout << endl;
pq2.push(5);
pq2.push(3);
pq2.push(8);
pq2.push(1);
pq2.push(6);
while (!pq2.empty())
{
cout << pq2.top() << " ";
pq2.pop();
}
cout << endl;
}
结果为:
vector也有类似的用法
void test_vector()
{
vector<int>v = {6,7,4,1,3,5 };
//vector的sort默认小的优先级高
//< 升序
sort(v.begin(), v.end());
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
//> 降序
sort(v.begin(), v.end(), greater<int>());
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
}
结果为:
通过上面两段代码,我们发现这两者第三个参数传的是不一样的。
为什么算法库的sort第三个参数跟仿函数不一样呢?
我们会发现,sort第三个参数类型是对象,而priority_queue传递的是类模板参数。
priority_queue的相关函数
构造函数
empty
size
top
push
pop
emplace
swap
priority_queue相关题目
数组中第K个最大元素
class Solution {
public:
int findKthLargest(vector<int>& nums, int k)
{
priority_queue<int>pq(nums.begin(),nums.end());
while(--k)
{
pq.pop();
}
return pq.top();
}
};
priority_queue的模拟实现
逻辑结构图:
priority_queue的底层结构是堆
#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
namespace Boogiepop
{
template<class T, class container =vector<T>>
class priority_queue
{
public:
priority_queue() = default;
//迭代器区间初始化
template<class InputItreator>
priority_queue(InputItreator first, InputItreator last)
:_con(first, last)
{
//向下调整堆
for (int i = _con.size() / 2 - 1; i >= 0; --i)
{
adjust_down(i);
}
}
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void pop()
{
swap(_con[0],_con[_con.size()-1]);
_con.pop_back();
adjust_down(0);
}
const T& top() const
{
return _con[0];
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
private:
container _con;
//向上调整
void adjust_up(int child)
{
int parent = (child - 1) / 2;//不需要考虑左右孩子
while (parent >= 0)
{
if (_con[child] > _con[parent])
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整
void adjust_down(int parent)
{
//选出大孩子
int child = 2 * parent + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && _con[child + 1] > _con[child])
{
++child;
}
if (_con[parent] < _con[child])
{
swap(_con[parent], _con[child]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
};
}
仿函数(重点!!!)
仿函数是C++为了替代函数指针而存在的(因为函数指针过于复杂)。而且函数指针没法应用于类模板
比如:
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
//仿函数/函数对象
template<class T>
class Less
{
public:
bool operator()(const T& a, const T& b) const
{
return a < b;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& a, const T& b) const
{
return a > b;
}
};
int main()
{
Less<int> lessfunc;
cout<<lessfunc(3, 5)<<endl;
//相当于调用了cout<<<lessfunc.operator()(3, 5)<<endl;
}
仿函数改造冒泡排序
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
//仿函数/函数对象
template<class T>
class Less
{
public:
bool operator()(const T& a, const T& b) const
{
return a < b;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& a, const T& b) const
{
return a > b;
}
};
//仿函数改造冒泡排序
template<class T, class Compare >
void Bubbersort(T* a, int n,Compare cmp)
{
int exhange = 0;
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (cmp(a[j], a[j + 1]))
{
exhange = a[j];
a[j] = a[j + 1];
a[j + 1] = exhange;
}
}
if (exhange == 0)
{
break;
}
}
}
int main()
{
/*Less<int> lessfunc;
cout<<lessfunc(3, 5)<<endl;*/
//相当于调用了cout<<<lessfunc.operator()(3, 5)<<endl;
int a[] = { 3,5,2,8,1,9,4,7,6 };
Bubbersort(a,7,Less<int>());
for (auto& i : a)
{
cout << i << " ";
}
cout<<endl;
for (auto& i : a)
{
cout << i << " ";
}
cout << endl;
return 0;
}
接下来,我们用仿函数对priority_queue进行改造吧!
#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
namespace Boogiepop
{
//仿函数/函数对象
template<class T>
class Less
{
public:
bool operator()(const T& a, const T& b) const
{
return a < b;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& a, const T& b) const
{
return a > b;
}
};
//仿函数改造
template<class T, class container =vector<T>,class Compare=Less<T>>
class priority_queue
{
public:
priority_queue() = default;
//迭代器区间初始化
template<class InputItreator>
priority_queue(InputItreator first, InputItreator last)
:_con(first, last)
{
//向下调整堆
for (int i = _con.size() / 2 - 1; i >= 0; --i)
{
adjust_down(i);
}
}
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void pop()
{
swap(_con[0],_con[_con.size()-1]);
_con.pop_back();
adjust_down(0);
}
const T& top()
{
return _con[0];
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
private:
container _con;
//向上调整
void adjust_up(int child)
{
Compare com;
int parent = (child - 1) / 2;//不需要考虑左右孩子
while (child >= 0)
{
//等同于if (_con[child] < _con[parent])
if (com(_con[parent] , _con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整
void adjust_down(int parent)
{
Compare com;
//选出大孩子
int child = 2 * parent + 1;
while (child < _con.size())
{
//等同于if (child + 1 < _con.size() &&_con[child] < _con[child + 1])
if (child + 1 < _con.size() &&com( _con[child ] , _con[child+1]))
{
++child;
}
if (com(_con[parent] , _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
};
}
测试:
#define _CRT_SECURE_NO_WARNINGS
#include"priority_queue.h"
void test1()
{
Boogiepop::priority_queue<int> pq;
//Boogiepop::priority_queue<int,vector<int>,greater<int>> pq;
pq.push(0);
pq.push(6);
pq.push(3);
pq.push(20);
pq.push(1);
while (!pq.empty())
{
std::cout << pq.top() << " ";
pq.pop();
}
std::cout << std::endl;
}
int main()
{
test1();
return 0;
}
上下两个优先级队列pq的结果分别为:
我们在之前类和对象的时候会接触到一些空类(即没有成员变量的类),它的一个用途就是仿函数。
下面再举一个例子:查找第一个偶数
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
struct OP1
{
bool operator()(int x) const
{
return x % 2 == 0;
}
};
int main()
{
int a[] = { 3,5,2,8,1,9,4,7,6 };
//查找第一个偶数
int n=sizeof(a)/sizeof(a[0]);
auto it =find_if(a, a + n, OP1());
cout << *it << endl;
//如果没有找到返回最后一个位置
return 0;
}
结果为:
本期内容就到这里,喜欢的话点个赞谢谢
封面图自取: