前言： Hello！！大家早上中午晚上好！！本文将介绍几个使用了适配器的容器的使用方法和模拟实现，例如：stack、queue、priority_queue!!
一、Stack
1.1 库里的stack
栈的特点：LIFO（last in first out - - 即后进先出）；
1.2 stack的使用
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <stack>
using namespace std;
int main()
{
stack<int> stack1;
stack1.push(1);
stack1.push(2);
stack1.push(3);
stack1.push(4);
while (!stack1.empty())
{
cout << stack1.top() << " ";
stack1.pop();
}
cout << endl;
return 0;
}
1.3 Stack的模拟实现
#pragma once
namespace ldc
{
template<class T,class container =vector<T>>//这里的适配器简单点就用vector来实现
class Stack
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
const T& top()
{
return _con.back();
}
private:
container _con;
};
}测试：
int main()
{
ldc::Stack<int> stack1;
stack1.push(5);
stack1.push(6);
stack1.push(7);
stack1.push(8);
while (!stack1.empty())
{
int a = stack1.top();
cout << a << " ";
stack1.pop();
}
}
二、queue
2.1 库里的queue
队列的特点：先进先出 FIFO(first in first out)
2.2queue的使用
#include <queue>
int main()
{
queue<int> queue1;
queue1.push(1);
queue1.push(2);
queue1.push(3);
queue1.push(4);
while (!queue1.empty())
{
int ret = queue1.front();
cout << ret << " ";
queue1.pop();
}
return 0;
}
2.3 queue的模拟实现
template<class T, class container = list<T>>
class queue
{
public:
void push(const T&val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_front();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
const T& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
private:
container _con;
};测试：
#include <queue>
int main()
{
ldc::queue<int> queue1;
queue1.push(1);
queue1.push(2);
queue1.push(3);
queue1.push(4);
cout << queue1.back() << endl;
while (!queue1.empty())
{
int ret = queue1.front();
cout << ret << " ";
queue1.pop();
}
cout << endl;
return 0;
}
三、priority_queue
3.1 库里的priority_queue
优先级队列的特点：底层实际是：二叉树 -- 堆，默认的是大的优先级高（默认是大堆），适配器采用的数据结构是vector；
3.2 priority_queque的使用
#include <queue>
int main()
{
priority_queue<int> que1;
que1.push(3);
que1.push(5);
que1.push(22);
que1.push(9);
que1.push(76);
while (!que1.empty())
{
int ret = que1.top();
cout << ret << " ";
que1.pop();
}
3.3 priority_queue的模拟实现
优先级队列记住几个点：①push尾插找到插入节点其父然后向上调整；②pop头删（弹出）交换最后一个结点并向下调整；③优先级队列使用的适配器是vector；
比较方法：
//大小堆的比较方法，小堆用greater，大堆用less
template<class T>
class greater
{
public:
bool operator()(const T& val1, const T& val2)
{
return val1 > val2;
}
};
template <class T>
class less
{
public:
bool operator()(const T& val1, const T& val2)
{
return val1 < val2;
}
};类的定义：
template<class T, class contanier = vector<T>, class compare = less<T>>
class priority_queue
{
void AdjustUp(int child)
{
compare cmp;
int parent = (child - 1) / 2;
while (child > 0)
{
if (cmp(_con[parent], _con[child]))
{
swap(_con[parent],_con[child]);
child=parent;
parent=(parent-1)/2;
}
else
break;
}
}
void AdJustDown(int parent)
{
compare cmp;
int child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && cmp(_con[child], _con[child + 1]))
{
child = child + 1;
}
if (cmp(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = child * 2 + 1;
}
else
break;
}
}
public:
void swap(T&v1,T&v2)
{
T tmp = v1;
v1 = v2;
v2 = tmp;
}
void push(const T&val)
{
_con.push_back(val);
AdjustUp(_con.size() - 1 );
}
void pop()
{
assert(!_con.empty());
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdJustDown(0);
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
const T& top()
{
return _con.front();
}
private:
contanier _con;
};测试：
int main()
{
ldc::priority_queue<int > pq1; //ldc是我自己定义的命名空间
pq1.push(2);
pq1.push(12);
pq1.push(23);
pq1.push(5);
pq1.push(115);
pq1.push(23);
pq1.push(9);
pq1.push(1);
pq1.push(8);
pq1.push(78);
while (!pq1.empty())
{
int top = pq1.top();
pq1.pop();
cout << top << " ";
}
cout << endl;
return 0;
}
以上是一些简单的容器的使用和模拟实现，如果对你有帮助记得点赞收藏＋关注哦！！谢谢！！！
咱下期见！！！