前言: 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;}elsebreak;}}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;}elsebreak;}}
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;
}
以上是一些简单的容器的使用和模拟实现,如果对你有帮助记得点赞收藏+关注哦!!谢谢!!!
咱下期见!!!