C++算法
STL 容器适配器 Stack、Queue 与 Priority Queue 的模拟实现
STL 容器适配器 Stack、Queue 和 Priority Queue 原理及模拟实现。Stack 基于 deque 或 vector 等容器，遵循后进先出原则；Queue 默认使用 deque，遵循先进先出原则；Priority Queue 基于堆结构，通过向上或向下调整算法维护堆序。此外讲解反向迭代器概念及其在 List 中的应用，包括正向与反向迭代器的镜像对称关系及代码实现细节。
STL 容器适配器 Stack、Queue 和 Priority Queue 原理及模拟实现。Stack 基于 deque 或 vector 等容器，遵循后进先出原则；Queue 默认使用 deque，遵循先进先出原则；Priority Queue 基于堆结构，通过向上或向下调整算法维护堆序。此外讲解反向迭代器概念及其在 List 中的应用，包括正向与反向迭代器的镜像对称关系及代码实现细节。
目录
4.1.2:back 和 front 和 size 与 empty
stack 和 queue 有一点需要注意，虽然 stack 和 queue 也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，STL 中stack 和 queue默认使用deque。在 stack 和 queue 的类模版声明中我们可以看到，它们的模版参数有两个，第一个是 stack 和 queue 当中所存储的元素类型，而另一个则是指定使用的容器类型，只不过当我们不指定使用何种容器的情况下，stack 和 queue 默认使用 deque 作为容器。
#include <iostream>
using namespace std;
#include <deque>
namespace MyStack {
template<class T, class Container = deque<T> >
class stack {
public:
void push(const T& x);
void pop();
//自定义类型传值返回时会调用拷贝构造，所以传引用
T& top();
const T& top()const;
size_t size()const;
bool empty();
private:
Container _Container;
};
};
栈的特点是后进先出，那么对于 push 我们可以调用容器适配器的 push_back，由于是后进先出，那么 pop 调用的则是 pop_back。
void push(const T& x) {
//尾插
_Container.push_back(x);
}
void pop() {
_Container.pop_back();
}
栈的 top 指的是栈顶元素，那么对应的则应该是容器适配器的 back() 函数，由于会存在 const 对象调用 top 函数，那么因此我们要对其进行函数重载。size 和 empty 直接调用容器适配器的 size() 和 empty 函数即可。
const T& top()const { return _Container.back(); }
size_t size()const { return _Container.size(); }
bool empty() { return _Container.empty(); }
T& top() { return _Container.back(); }
#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
#include <vector>
int main() {
MyStack::stack<int,vector<int>> st1;
st1.push(1);
st1.push(2);
st1.push(3);
st1.push(4);
st1.push(5);
cout << "size:> " << st1.size() << endl;
while (!st1.empty()) {
cout << st1.top() << " ";
st1.pop();
}
return 0;
}
#include <iostream>
using namespace std;
#include <deque>
namespace MyQueue {
template<class T, class Container = deque<T>>
class queue {
public:
//尾插
void push(const T& value);
//头删
void pop();
//获取队尾元素
T& back();
T& back() const;
//获取队头元素
T& front();
T& front() const;
size_t size()const;
bool empty() const;
private:
Container _Container;
};
};
队列的特点是先进先出，那么对于 push 我们可以调用容器适配器的 push_back，由于是先进先出，那么 pop 调用的则是 pop_front。
//尾插
void push(const T& value) {
_Container.push_back(value);
}
//头删
void pop() {
_Container.pop_front();
}
队列的 back 指的是队尾元素，那么对应的则应该是容器适配器的 back() 函数，由于会存在 const 对象调用 back 函数，那么因此我们要对其进行函数重载。队列的 front 指的是队头元素，那么对应的则应该是容器适配器的 front() 函数，同理 back 函数我们也要对其进行函数重载。size 和 empty 直接调用容器适配器的 size() 和 empty 函数即可。
T& back() { return _Container.back(); }
T& back() const { return _Container.back(); }
T& front() { return _Container.front(); }
T& front() const { return _Container.front(); }
size_t size()const { return _Container.size(); }
bool empty() const { return _Container.empty(); }
#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
#include <list>
int main() {
MyQueue::queue<int, list<int>> q1;
q1.push(1);
q1.push(2);
q1.push(3);
q1.push(4);
q1.push(5);
while (!q1.empty()) {
cout << q1.front() << "::" << q1.back() << endl;
q1.pop();
}
return 0;
}
#pragma once
#include <iostream>
using namespace std;
#include <assert.h>
#include <vector>
#include <algorithm>
namespace MyPriorityQueue {
template <class T,class Container = vector<T>,class Compare = less<T>>
class priority_queue {
public:
void Adjust_Up(int child);
void Adjust_Down(int parent);
void push(const T& val);
void pop();
bool empty() const;
size_t size() const;
T& top();
private:
Container _Container;
};
}
void Adjust_Up(int child) {
//找到目标节点的父亲节点
int parent = (child - 1) / 2;
while(child > 0) {
//孩子比父亲大，进行交换
if(_Container[child] > _Container[parent]) {
swap(_Container[child],_Container[parent]);
//更新孩子和父亲，继续进行向上调整
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
使用向下调整算法有一个前提：若想将其调整为小堆，那么根结点的左右子树必须都为小堆。若想将其调整为大堆，那么根结点的左右子树必须都为大堆。
void Adjust_Down(int parent) {
//假设左孩子最大
int child = parent * 2 + 1;
while (child < size()) {
if(child + 1 < size() && _Container[child + 1] > _Container[child]) {
child++;
}
//孩子比父亲大，进行交换
if (_Container[child] > _Container[parent]) {
swap(_Container[child], _Container[parent]);
//更新孩子和父亲，继续进行向下调整
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
对于 push，直接尾插，然后进行向上调整算法即可。对于 pop，删除的是堆顶的元素，但是这个删除过程可并不是直接删除堆顶的数据，而是先将堆顶的数据与最后一个结点的位置交换，然后再删除最后一个结点，再对堆进行一次向下调整。若是直接删除堆顶的数据，那么原堆后面数据的父子关系就全部打乱了，需要全体重新建堆，时间复杂度为 O(N)。若是用上述方法，那么只需要对堆进行一次向下调整即可，因为此时根结点的左右子树都是小堆，我们只需要在根结点处进行一次向下调整即可，时间复杂度为 O(log(N))。
void push(const T& val) {
//尾插
_Container.push_back(val);
//向上调整
Adjust_Up(size() - 1);
}
void pop() {
//交换堆顶和堆底
swap(_Container[0], _Container[size() - 1]);
//尾删
_Container.pop_back();
//向下调整
Adjust_Down(0);
}
bool empty() const { return _Container.empty(); }
size_t size() const { return _Container.size(); }
T& top() { return _Container[0]; }
#include "Priority_queue.h"
int main() {
MyPriorityQueue::priority_queue<int> pq;
pq.push(70);
pq.push(56);
pq.push(30);
pq.push(15);
pq.push(25);
pq.push(10);
pq.push(90);
pq.push(100);
while(!pq.empty()) {
cout << pq.top() << " " << "size:>" << pq.size() << endl;
pq.pop();
}
return 0;
}
反向迭代器与正向迭代器的区别主要在遍历的方向上：正向迭代器是从容器的第一个元素开始向后遍历的，反向迭代器是从容器的最后一个元素开始向前遍历的。因此我们可以通过对正向迭代器的封装来生成反向迭代器----迭代器适配器。
反向迭代器在实现的时候与正向迭代器是一种镜像对称的关系。
使用正向迭代器适配反向迭代器的时候会认为它两存在对称关系，那么此时就会导致两个问题 rbegin 第一次解引用是一个随机值。rbegin == rend 就结束了。
那么就导致了第一个元素没有取到，那么我们该如何解决这个对称的坑呢通过解引用来解决这个坑，解引用时，我们并不是解引用当前位置，而是解引用它的前一个位置！
反向迭代器的++是正向迭代器的--，反向迭代器的--就是正向迭代器的++。
#define _CRT_SECURE_NO_WARNINGS
namespace MyReverseIterator {
template<class Iterator,class Reference,class Pointer>
class ReverseIterator {
typedef ReverseIterator<Iterator, Reference, Pointer> Self;
ReverseIterator(Iterator it) :_it(it) { };
Self& operator++() { --_it; return *this; }
Self& operator--() { ++_it; return *this; }
Reference operator*() {
/*
* 正向迭代器与反向迭代器成一个镜像对称的关系，所以反向迭代器解引用时的元素不是解引用当前位置
* 而是解引用它的前一个位置
* 因为解引用是不能够影响当前迭代器的，所以需要创建一个临时变量
*/
Iterator temp = _it;
--temp;
return *temp;
}
Pointer operator->() { return &(operator*()); }
bool operator!=(const Self& rit) { return _it != rit._it; }
bool operator==(const Self& rit) { return _it == rit._it; }
private:
Iterator _it;
};
}
我们用 list 的正向迭代器生成 list 的反向迭代器为例。
#pragma once
#define _CRT_SECURE_NO_WARNINGS
namespace MyReverseIterator {
template<class Iterator, class Reference, class Pointer>
struct ReverseIterator {
typedef ReverseIterator<Iterator, Reference, Pointer> Self;
Iterator _it;
ReverseIterator(Iterator it) :_it(it) { };
Self& operator++() { --_it; return *this; }
Self& operator--() { ++_it; return *this; }
Reference operator*() {
/*
* 正向迭代器与反向迭代器成一个镜像对称的关系，所以反向迭代器解引用时的元素不是解引用当前位置
* 而是解引用它的前一个位置
* 因为解引用是不能够影响当前迭代器的，所以需要创建一个临时变量
*/
Iterator temp = _it;
--temp;
return *temp;
}
Pointer operator->() { return &(operator*()); }
bool operator!=(const Self& rit) { return _it != rit._it; }
bool operator==(const Self& rit) { return _it == rit._it; }
};
};
#pragma once
#include <iostream>
using namespace std;
#include <assert.h>
#include <string>
#include "ReverseIterator.h"
namespace MyList {
//节点类的定义
template <class T>
struct ListNode {
ListNode* Previous;
ListNode* Next;
T Val;
//构造函数
ListNode(const T& val = T()) :Previous(nullptr), Next(nullptr), Val(val) { }
};
//迭代器类的定义
template <class T, class Reference, class Pointer>
struct ListIterator {
typedef ListNode<T> Node;
typedef ListIterator<T, Reference, Pointer> Self;
//构造函数
ListIterator(Node* node) :_Node(node) { };
Node* _Node;
//前置++
Self& operator++() { _Node = _Node->Next; return *this; }
//后置++
Self operator++(int) {
Self temp = *;
_Node = _Node->Next;
temp;
}
Self& --() { _Node = _Node->Previous; *; }
Self --() {
Self temp = *;
_Node = _Node->Previous;
temp;
}
Reference *() { _Node->Val; }
Pointer ->() { &_Node->Val; }
!=( Self& it) {
_Node != it._Node;
}
==( Self& it) { _Node == it._Node; }
};
< >
{
ListNode<T> Node;
:
ListIterator<T, T&, T*> iterator;
ListIterator<T, T&, T*> const_iterator;
MyReverseIterator::ReverseIterator<iterator, T&, T*> reverse_iterator;
MyReverseIterator::ReverseIterator<iterator, T&, T*> const_reverse_iterator;
:
{
_Head = ();
_Head->Next = _Head;
_Head->Previous = _Head;
_Size = ;
}
() { (); }
( List<T>& lt) { (); (& element : lt) { (element); } }
{ (()); }
{ (()); }
{ (()); }
{ (()); }
{
(_Head->Next);
}
{
(_Head);
}
{
_Head->Next;
}
{
_Head;
}
{
((), Val);
}
{ (--()); }
{ ((), Val); }
{ (()); }
{
Node* NewNode = (Val);
Node* Current = Position._Node;
Node* Prev = Current->Previous;
Prev->Next = NewNode;
NewNode->Previous = Prev;
NewNode->Next = Current;
Current->Previous = NewNode;
_Size++;
}
{
Node* Current = Position._Node;
Node* Prev = Current->Previous;
Node* Next = Current->Next;
Prev->Next = Next;
Next->Previous = Prev;
Current;
_Size--;
(Next);
}
{ _Size; }
{ _Size == ; }
{
iterator it = ();
(it != ()) { it = (it); }
}
{ std::(_Head, lt._Head); std::(_Size, lt._Size); }
List<T>& =(List<T> lt) { (lt); *; }
~() { (); _Head; _Head = ; }
:
Node* _Head;
_Size;
};
}
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include "List.h"
void TestList12() {
MyList::List<int> lt;
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(40);
lt.push_back(50);
MyList::List<int>::reverse_iterator rit = lt.rbegin();
while (rit != lt.rend()) {
cout << *rit << " ";
++rit;
}
cout << endl;
}
void TestList13() {
MyList::List<int> lt;
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(40);
lt.push_back(50);
MyList::List<int>::reverse_iterator rit = lt.rbegin();
while (rit != lt.rend()) {
cout << *rit << " ";
++rit;
}
cout << endl;
}
{
();
cout << endl;
();
;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online