C++ 复习总结记录十
主要内容
1、stack 介绍和使用
2、queue 介绍和使用
3、priority_queue 介绍和使用
4、容器适配器
一 stack 的介绍和使用
stack 文档介绍
1、 stack 是容器适配器,专用于后进先出的操作,只能从容器尾端进行元素插入和提取
2、 容器适配器是对特定类封装作为底层容器,并提供一组特定的成员函数
3、 stack 底层容器可以是任何标准的容器类模板或一些其他特定的容器类,这些容器类应支持以下操作
- empty 判空操作
- back 获取尾部元素操作
- push_back 尾部插入元素操作
- pop_back 尾部删除元素操作
4、标准容器 vector、deque、list 均符合上述需求,stack 的默认底层容器是 deque
1.1 stack 的使用
函数说明 接口说明
stack() 构造空的栈
empty() 检测 stack 是否为空
size() 返回 stack 中元素的个数
top() 返回栈顶元素的引用
push() 将元素 val 压入 stack 中
pop() 将 stack 中尾部的元素弹出
1.2 练习
最小栈
class MinStack {
public:
MinStack() {}
void push(int val)
{
if(minStack.size() == 0 || val <= minStack.top()) //若最小栈为空或插入数据小于或等于栈顶元素
minStack.push(val); //入最小栈
src.push(val); //所有数据栈, 则直接入栈
}
void pop()
{
if(minStack.size() != 0 && src.top() == minStack.top()) //若最小栈不为空且删除数据所有数据栈顶元素等于最小栈顶元素
minStack.pop(); //删除最小栈顶元素
src.pop(); //所有数据栈, 则直接删除栈顶元素
}
int top()
{
return src.top(); //返回所有数据栈顶元素
}
int getMin()
{
return minStack.top(); //返回最小栈顶元素
}
private:
stack<int> src; //所有数据的栈
stack<int> minStack; //最小栈
};
栈的弹出压入序列
bool IsPopOrder(vector<int>& pushV, vector<int>& popV)
{
stack<int> data; //data 模拟进出栈过程
int p1 = 0, p2 = 0; //p1, p2 是对用 vector 的下标
while(p1 < pushV.size()) //入栈顺序数据不为空
{
data.push(pushV[p1]); //直接入栈
while (p2 < popV.size() &&
data.size() !=0 &&
data.top() == popV[p2]) //判断栈顶元素是否和出栈数据相同(注意边界条件)
{
data.pop(); //出栈
++p2; //移动下标
}
++p1; //移动下标
}
return data.size() == 0; //校验栈内是否还有数据
}
逆波兰表达式求值
int evalRPN(vector<string>& tokens) {
stack<int> ans;
int left = 0, right = 0;
for (auto& str : tokens)
{
if (!("+" == str || "-" == str || "*" == str || "/" == str)) //注意这里的判断条件不能用 str[0] >= '0', 因为可能有负数
{
ans.push(stoi(str)); //C++11, C 风格转换 atoi(str.c_str());
}
else
{
right = ans.top(); //注意这里栈顶元素是右操作数
ans.pop();
left = ans.top();
ans.pop();
switch(str[0])
{
case '+':
ans.push(left + right);
break;
case '-':
ans.push(left - right);
break;
case '*':
ans.push(left * right);
break;
case '/':
ans.push(left / right);
break;
}
}
}
return ans.top();
}
用两个栈实现队列
class MyQueue {
public:
MyQueue() {}
void push(int x)
{
s1.push(x);
}
int pop()
{
int res = peek();
s2.pop();
return res;
}
int peek()
{
if (s2.size() == 0) //若 s2 为空, 需要把 s1 数据搬至 s2
{
while(s1.empty())
{
s2.push(s1.top());
s1.pop();
}
}
return s2.top(); //s2 栈顶元素即为队列头元素
}
bool empty()
{
return s1.size() == 0 && s2.size() == 0;
}
private:
stack<int> s1;
stack<int> s2;
};
1.3 stack 模拟实现
使用 vector 模拟实现 stack
#include<vector>
namespace lucky
{
template<class T>
class stack
{
public:
stack() {}
void push(const T& x) {_c.push_back(x);}
void pop() {_c.pop_back();}
T& top() {return _c.back();}
const T& top()const {return _c.back();}
size_t size()const {return _c.size();}
bool empty()const {return _c.empty();}
private:
std::vector<T> _c;
};
}
二 queue 的介绍和使用
queue 文档介绍
1、队列是一种容器适配器,用于 FIFO ( 先进先出 ) 操作,从容器一端插入元素,另一端提取元素
2、底层容器可以是标准容器类模板之一,也可是其它专门设计的容器类。该底层容器应至少支持以下操作
- empty 检测队列是否为空
- size 返回队列中有效元素个数
- front 返回队头元素引用
- back 返回队尾元素引用
- push_back 在队列尾部入队列
- pop_front 在队列头部出队列
4、标准容器类 deque 和 list 满足了这些要求。默认情况下 queue 指定使用标准容器 deque
2.1 queue 的使用
函数声明 接口说明
queue() 构造空的队列
empty() 检测队列是否为空, 是返回 true, 否则返回 false
size() 返回队列中有效元素的个数
front() 返回队头元素的引用
back() 返回队尾元素的引用
push() 在队尾将元素 val 入队列
pop() 将队头元素出队列
用队列实现栈
class MyStack {
public:
MyStack() {}
void push(int x)
{
q2.push(x); //元素先入 q2
while(!q1.empty()) //若 q1 不为空, 拷 q1 数据至 q2
{
q2.push(q1.front()); //将 q1 首元素拷至 q2
q1.pop(); //删除队列首元素
}
q1.swap(q2); //数据交换
}
int pop()
{
int res = q1.front();
q1.pop(); //删除 q1 队列首元素
return res;
}
int top() { return q1.front(); }
bool empty() { return q1.empty(); }
private:
queue<int> q1;
queue<int> q2;
};
2.2 queue 模拟实现
queue 接口中存在头删和尾插,使用 vector 封装效率太低,借助 list 模拟实现 queue
#include <list>
namespace lucky
{
template<class T>
class queue
{
public:
queue() {}
void push(const T& x) { _c.push_back(x); }
void pop() { _c.pop_front(); }
T& back() { return _c.back(); }
const T& back() const { return _c.back(); }
T& front() { return _c.front(); }
const T& front() const { return _c.front(); }
size_t size() const { return _c.size(); }
bool empty() const { return _c.empty(); }
private:
std::list<T> _c;
};
}
三 priority_queue 的介绍和使用
priority_queue 文档介绍
1、优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的
2、数据结构类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素 ( 优先队列中位于顶部的元素 )
3、底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作
- empty() 检测容器是否为空
- size() 返回容器中有效元素个数
- front() 返回容器中第一个元素的引用
- push_back() 在容器尾部插入元素
- pop_back() 删除容器尾部元素
4、标准容器类 vector 和 deque 满足上述需求;默认情况下,priority_queue 类实例化的容器类是 vector
5、需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 来自动完成此操作
3.1 priority_queue 的使用
优先级队列默认使用 vector 作为其底层存储数据的容器,在 vector 上又使用了堆算法将 vector 中元素构造成堆结构。
因此 priority_queue 就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue,注意:默认情况下 priority_queue 是大堆
函数声明 接口说明
priority_queue() 构造一个空的优先级队列
priority_queue(first,last) 构造一个优先级队列
empty() 检测优先级队列是否为空, 是返回 true, 否则返回 false
top() 返回优先级队列中最大(最小元素),即堆顶元素
push(x) 在优先级队列中插入元素 x
pop() 删除优先级队列中最大(最小)元素,即堆顶元素
默认情况下,priority_queue 是大堆
#include <vector>
#include <queue>
#include <functional> // greater算法的头文件
void TestPriorityQueue()
{
// 默认情况下, 创建的是大堆, 其底层按照小于号比较
vector<int> v{3,2,7,6,0,4,1,9,8,5};
priority_queue<int> q1;
for (auto& e : v)
q1.push(e);
cout << q1.top() << endl;
// 如果要创建小堆, 将第三个模板参数换成 greater 比较方式
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
cout << q2.top() << endl;
}
如果在 priority_queue 中放自定义类型数据,需在自定义类型中提供 > 或 < 重载
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
bool operator<(const Date& d) const
{
return (_year < d._year) ||
(_year == d._year && _month < d._month) ||
(_year == d._year && _month == d._month && _day < d._day);
}
bool operator>(const Date& d) const
{
return (_year > d._year) ||
(_year == d._year && _month > d._month) ||
(_year == d._year && _month == d._month && _day > d._day);
}
friend ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
private:
int _year;
int _month;
int _day;
};
void TestPriorityQueue()
{
// 大堆需要自定义类型中提供 < 重载
priority_queue<Date> q1;
q1.push(Date(2018, 10, 29));
q1.push(Date(2018, 10, 28));
q1.push(Date(2018, 10, 30));
cout << q1.top() << endl;
// 创建小堆提供 > 重载
priority_queue<Date, vector<Date>, greater<Date>> q2;
q2.push(Date(2018, 10, 29));
q2.push(Date(2018, 10, 28));
q2.push(Date(2018, 10, 30));
cout << q2.top() << endl;
}
3.2 练习
数组中第 K 大的元素
方法一 最大堆 : 时间复杂度 N * logN,空间复杂度 log N
#include<functional>
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, less<int>> p1(nums.begin(), nums.end()); //遍历时间复杂度 N, 调整最大堆时间复杂度 logN
while (k-- > 1)
{
p1.pop();
}
return p1.top();
}
方法二 排序 : 时间复杂度 N * logN,空间复杂度 O(1)
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
方法三 最小堆 : 时间复杂度 N * logK,空间复杂度 logK
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> p1(nums.begin(), nums.begin() + k);
for (int i = k; i < nums.size(); ++i)
{
if (nums[i] > p1.top())
{
p1.pop();
p1.push(nums[i]);
}
}
return p1.top();
}
3.3 priority_queue 模拟实现
priority_queue 的底层结构就是堆,此处只需对其进行通用封装即可
#pragma once
#include <iostream>
using namespace std;
#include <vector>
// priority_queue ---> 堆
namespace lucky
{
template<class T>
struct less
{
bool operator()(const T& left, const T& right)
{
return left < right;
}
};
template<class T>
struct greater
{
bool operator()(const T& left, const T& right)
{
return left > right;
}
};
template<class T, class Container = std::vector<T>, class Compare = less<T>>
class priority_queue
{
public:
// 创造空的优先级队列
priority_queue() : c() {}
template<class Iterator>
priority_queue(Iterator first, Iterator last)
: c(first, last)
{
// 将 c 中的元素调整成堆的结构
int count = c.size();
int root = ((count - 2) >> 1);
for (; root >= 0; root--)
AdjustDown(root);
}
void push(const T& data)
{
c.push_back(data);
AdjustUP(c.size() - 1);
}
void pop()
{
if (empty())
return;
swap(c.front(), c.back());
c.pop_back();
AdjustDown(0);
}
size_t size() const
{
return c.size();
}
bool empty() const
{
return c.empty();
}
// 堆顶元素不允许修改,因为:堆顶元素修改可以会破坏堆的特性
const T& top()const
{
return c.front();
}
private:
// 向上调整
void AdjustUP(int child)
{
int parent = ((child - 1) >> 1);
while (child)
{
if (Compare()(c[parent], c[child]))
{
swap(c[child], c[parent]);
child = parent;
parent = ((child - 1) >> 1);
}
else
{
return;
}
}
}
// 向下调整
void AdjustDown(int parent)
{
size_t child = parent * 2 + 1;
while (child < c.size())
{
// 找以 parent 为根的较大的孩子
if (child + 1 < c.size() && Compare()(c[child], c[child + 1]))
child += 1;
// 检测双亲是否满足情况
if (Compare()(c[parent], c[child]))
{
swap(c[child], c[parent]);
parent = child;
child = parent * 2 + 1;
}
else
return;
}
}
private:
Container c;
};
}
void TestQueuePriority()
{
lucky::priority_queue<int> q1;
q1.push(5);
q1.push(1);
q1.push(4);
q1.push(2);
q1.push(3);
q1.push(6);
cout << q1.top() << endl;
q1.pop();
q1.pop();
cout << q1.top() << endl;
vector<int> v{ 5,1,4,2,3,6 };
lucky::priority_queue<int, vector<int>, lucky::greater<int>> q2(v.begin(), v.end());
cout << q2.top() << endl;
q2.pop();
q2.pop();
cout << q2.top() << endl;
}
四 容器适配器
适配器是一种设计模式 ( 设计模式是一套被反复使用的、经过分类编目的、代码设计经验的总结),该种模式是将一个类接口转换成期望的另一个接口
STL 标准库中 stack 和 queue 的底层结构
虽然 stack 和 queue 中也可以存放元素,但在 STL 中并没有将其划分在容器的行列,而是将其称为容器适配器。因为 stack 和队列只是对其它容器接口进行了包装,STL 中 stack 和 queue 默认使用 deque
4.1 deque 介绍
deque ( 双端队列 ),是一种双开口的连续空间数据结构,双开口含义是可以在头尾两端进行插入和删除操作,且时间复杂度为 O(1),与 vector 比较,头插效率高,不需要搬移元素;与 list 比较,支持随机访问且空间利用率比较高
deque 并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际 deque 类似于一个动态二维数组,其底层结构如下图所示
双端队列的连续空间,实际是分段连续的,其整体连续以及随机访问的功能,主要因为 deque 的迭代器,设计如下
4.2 deque 缺陷
与 vector 相比,deque 优势是头部插入和删除时,不需要搬移元素,效率特别高且扩容时,也不需要搬移元素,效率 vector 高
与 list 相比,其底层是连续空间,空间利用率比较高,不需要存储额外字段
deque 的缺陷是不适合遍历,因为在遍历时,deque 迭代器要频繁的去检测其是否移动到某段小空间边界,导致效率低下。而序列式场景中,可能需要经常遍历,因此在大多数线性结构情况下,使用的是 vector 和 list,deque 应用并不多
4.3 为什么选择 deque 作为 stack 和 queue 的底层默认容器
stack 是一种后进先出的特殊线性数据结构,因此只要具有 push_back 和 pop_back 操作的线性结构,都可以作为 stack 的底层容器,比如 vector 和 list 等
queue 是先进先出的特殊线性数据结构,只要具有 push_back 和 pop_front 操作的线性结构,都可以作为 queue 的底层容器,比如 list 等
STL 中对 stack 和 queue 默认选择 deque 作为其底层容器,主要因为
① stack 和queue 不需要遍历 (因此 stack 和 queue 没有迭代器),只需要在固定的一端或者两端进行操作
② 在 stack 中元素增长时,deque 比 vector 的效率高 ( 扩容时不需要搬移大量数据 ) queue 中的元素增长时,deque 不仅效率高,且空间利用率高
4.4 STL 中对 stack 和 queue 模拟实现
stack 模拟实现
#include<deque>
namespace lucky
{
template<class T, class Con = deque<T>>
//template<class T, class Con = vector<T>>
//template<class T, class Con = list<T>>
class stack
{
public:
stack() {}
void push(const T& x) { _c.push_back(x); }
void pop() { _c.pop_back(); }
T& top() { return _c.back(); 1}
const T& top() const {return _c.back();}
size_t size() const {return _c.size();}
bool empty() const {return _c.empty();}
private:
Con _c;
};
}
queue 模拟实现
#include<deque>
#include <list>
namespace lucky
{
template<class T, class Con = deque<T>>
//template<class T, class Con = list<T>>
class queue
{
public:
queue() {}
void push(const T& x) { _c.push_back(x); }
void pop() { _c.pop_front(); }
T& back() { return _c.back(); }
const T& back() const { return _c.back(); }
T& front() { return _c.front(); }
const T& front() const { return _c.front(); }
size_t size() const { return _c.size(); }
bool empty() const { return _c.empty(); }
private:
Con _c;
};
}