现在建设一个基础的网站多少钱,公司网站建设模块简介,wordpress 显示标题,证书在线制作生成器为了更好的理解优先级队列priority_queue#xff0c;这里会同时进行栈和队列的提及 文章目录 简要概念#xff08;栈和队列#xff09;栈和队列的模拟实现与使用stack#xff08;栈#xff09;deque的理解和操作queue priority_queue#xff08;优先级队列#xff09;框… 为了更好的理解优先级队列priority_queue这里会同时进行栈和队列的提及 文章目录 简要概念栈和队列栈和队列的模拟实现与使用stack栈deque的理解和操作queue priority_queue优先级队列框架具体实现push()adjust_up()向上调整pop()adjust_down()向下调整top()empty()size() priority_queue 的 验证 / 使用 简要概念栈和队列
栈后进先出的结构通常使用数组栈的形式队列先进先出的结构通常使用链表式的队列 优先级队列优先级队列是基于堆实现的一种数据结构。在 C STL 中我们将实现的priority_queue 类就是通过堆来实现的。这里不再对堆进行详细介绍具体在这堆详解
栈和队列的模拟实现与使用
stack栈
模拟实现
进行stack的实现前先介绍一下dequeT
deque的理解和操作
概念简单看看
概念简单看看就行
deque 是 C STL 中的一种双端队列double-ended queue它允许在队列两端高效地添加、删除元素同时支持随机访问。与vector的不同deque 具有良好的内存分配策略可以避免 vector 扩容时带来的大量元素复制操作。此外deque 也具有更好的迭代器安全性因为它不能像 vector 那样通过引起扩容而使得旧迭代器失效。deque 内部使用了一个中央控制器管理了一系列固定大小的连续空间块每个块内部存储多个元素。当 deque 需要增加或删除元素时中央控制器会根据需要进行块的扩容或收缩。
操作重要
这里介绍deque与stack queue的不同处介绍为什么要用deque实现栈和队列
插入和删除方式不同栈只能在栈顶进行插入和删除元素而队列只能在队尾插入在队头删除而 deque 可以在队列的两端都插入和删除元素。访问方式不同栈只能访问栈顶元素队列只能访问队头元素而 deque 可以随机访问任意位置的元素。功能上不同栈的主要功能是实现“后进先出”LIFO队列的主要功能是实现“先进先出”FIFO而 deque 不仅可以实现这两种功能还能够满足双向遍历、支持随机插入和删除等操作。 继续对stack进行模拟实现
这里需要注意的
对于模板template T 表示栈中元素的类型Container 表示底层容器的类型默认为 dequeT成员变量 _con为Container类型如果调用者不给Container类型_con默认为deque剩下的增删查改调用_con的操作函数即可
namespace aiyimu
{//Container 表示用于存储队列元素的底层容器类型默认值为 dequeTtemplateclass T, class Container dequeTclass stack{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}T top(){return _con.back();}const T top() const{return _con.back();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
}queue
同理stack这里不作过多赘述使用_con的操作函数实现即可
namespace aiyimu
{templateclass T, class Container dequeTclass queue{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_front();}T back(){return _con.back();}T front(){return _con.front();}const T back() const{return _con.back();}const T front() const{return _con.front();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
}priority_queue优先级队列
框架
Container在上文stack有解同理Compare用于选择该堆为大堆还是小堆默认为std::less则为小堆std::less 是一个函数对象用于比较两个参数的大小关系。重载了小于运算符用于比较两个类型为 T 的对象的大小。当 a b 时std::less()(a, b) 返回 true否则返回 false。构造函数操作函数
templateclass T, class Container vectorT, class Compare std::lessTclass priority_queue{public:// 默认构造priority_queue(){}// 利用迭代器构造函数template class InputIteratorpriority_queue(InputIterator first, InputIterator last){}// O(logN)// 向上调整void adjust_up(size_t child){}//向下调整void adjust_down(size_t parent){}// 其余操作函数void push(const T x){}void pop(){}const T top(){}bool empty() const{}size_t size() const{}private:Container _con;};具体实现
push()
插入操作即为堆的插入操作所以执行_con.push_back()后进行向上调整从尾部_con.size()-1进行调整
void push(const T x)
{_con.push_back(x);adjust_up(_con.size() - 1);
}adjust_up()向上调整
向上调整即堆heap的操作具体思路在上文给到的堆详解中主要对if语句中的内容进行解释
小堆向上调整过程中当父节点的值小于子节点时交换父子节点
原始方法直接进行判断if (_con[parent] _con[child])但这种写法此时就锁定小堆了 为了使调用者可以根据需要进行大堆小堆的更改所以这里创建一个Compare对象com将比较改写为if(com(_con[parent], _con[child]))该写法当调用者不做更改时默认为小堆std::less当调用者给出std::greater比较大于此时的priority_queue就变为大堆
void adjust_up(size_t child)
{Compare com; // size_t parent (child - 1) / 2;while (child 0){//if (_con[parent] _con[child])if(com(_con[parent], _con[child]))// 默认为less调用者可以自行指定{std::swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}
}pop()
交换堆顶和堆底的元素删除堆顶元素向下调整
void pop()
{// 交换堆顶和堆底的元素删除堆顶元素向下调整std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);
}adjust_down()向下调整
向下调整需要注意的仍为com(_con[child], _con[child 1])写法的意义具体内容在adjust_up中已经提到
void adjust_down(size_t parent)
{Compare com;size_t child parent * 2 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 (_con[parent] _con[child])if(com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}
}top()
返回堆顶元素即_con[0]
const T top()
{return _con[0];
}empty()
bool类型判断堆是否为空
bool empty() const
{return _con.empty();
}size()
返回堆大小堆元素个数
size_t size() const
{return _con.size();
}priority_queue 的 验证 / 使用
插入元素 打印priority_queue
// 头文件void test_priority_queue1()
{aiyimu::priority_queueint pq;//priority_queueint pq;// 插入元素pq.push(3);pq.push(2);pq.push(5);pq.push(9);pq.push(4);pq.push(6);pq.push(1);// 打印pq的所有元素while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;
}输出结果
降序 / 升序
int arr[] { 3,5,6,8,19,7,1,0,9,1,20,4,12 };// 不传入Compare类型默认less类型小于即降序aiyimu::priority_queueint heap_less(arr, arr sizeof(arr) / sizeof(arr[0]));// 传入Compare类型为greater类型大于即升序aiyimu::priority_queueint, vectorint, greaterint heap_greater(arr, arr sizeof(arr) / sizeof(arr[0]));while (!heap_less.empty()){cout heap_less.top() ;heap_less.pop();}cout endl;while (!heap_greater.empty()){cout heap_greater.top() ;heap_greater.pop();}cout endl;输出结果 由此可以看出当使用std::less时堆为降序std::greater时堆为升序
