十七、模拟 实现栈和队列类

2024-08-27 20:04
文章标签 实现 模拟 队列 十七

本文主要是介绍十七、模拟 实现栈和队列类,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Ⅰ . 模拟实现 stack

01 实现思路

插入数据删除数据这些逻辑其实没有必要自己实现,而是采用转换的方式

之前我们讲解了适配器的知识,这里采用的就是一些其他的适配的容器去实现

至于转换什么,我们可以进一步想到,好像有很多容器适合去转换

所以 STL 中增加了一个模板参数 Container,利用 Container 来进行转换

上一章末尾,我们利用了 deque 去实现栈和队列

template<class T, class Container = deque<T>>

对于栈而言, push 插入数据就是尾插 push_back,pop 删除数据就是尾删 pop_back

void push(const T& x) {_con.push_back(x);    // 对于栈而言,入栈就是尾插
}
void pop() {_con.pop_back();      // 对于栈而言,出栈就是尾删
}

返回堆顶数据我们可以用 back,即可返回尾上数据,本质是一种封装

const T& top() {return _con.back();  // 返回尾上数据
}

代码实现:

#include<iostream>
#include<deque>
using namespace std;namespace yxt
{template<class T,class Container = deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}

02 代码测试

先使用 deque 去存储

namespace yxt
{void test_stack1(){stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;}
}

运行结果:

如果不想用 deque ,可以自由的去传

	void test_stack2(){stack<int, vector<int>> st;st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;}

运行结果如下:

我们试试用 list 可不可行

	void test_stack3(){stack<int, list<int>> st;st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;}

运行结果如下:

那么是否可以用 string 呢?

勉强可以,但有溢出的风险

	void test_stack4(){stack<int, string> st;st.push(1);st.push(2);st.push(3);st.push(400);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;}

运行结果如下:存在截断问题,发生数据丢失

总结:从上层角度看,其默认是一个双端队列,底层用什么去实现并不重要,只要符合要求即可,保存栈的性质,复用容器的代码

我们可以用 const 来限定成员函数,这意味着不能在类对象上调用这些函数来修改内部状态,避免了潜在的危险

namespace yxt
{template<class T,class Container = deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

const T& top() const 中的两个 const 限定符分别适用于不同的情况

① 第一个 const 限定符表示 top 函数不会修改调用它的对象的内部状态,这意味着你可以在一个常量对象上调用 top,而且它不会导致对象的状态被修改,这是对对象的只读

② 第二个 const 限定符表示这个函数返回的引用不能用于修改底层容器 _con 中的元素,这个 const 限定符是用于确保函数不会意外地修改堆栈的底层数据,在这种情况下,它适用于返回类型,表示返回的引用是一个常量引用,不允许修改

这两个 const 限定符的组合是为了提供对堆栈对象的只读访问,并且保护了堆栈的内部数据免受意外的修改

像 size 函数只是返回堆栈的大小,不会修改堆栈的状态或底层容器的内容,因此,只需要在函数声明和定义中使用一个 const 限定符,来确保这个函数不会修改对象的内部状态,足以满足只读访问的要求

Ⅱ . 模拟实现 queue

01 实现思路

其默认容器也是 deque

template<class T, class Container = deque<T>>

queue 是先进先出的,queue 的 push 就是尾插,pop 需要支持头删

void push(const T& x) 
{ _con.push_back(x);  // 进队
}
void pop() 
{ _con.pop_front();   // 出队
}

值得注意的是,queue 不能使用 vector 去适配,因为 vector 没有 push_front 这个接口

front 和 back 直接调对应的接口即可

代码实现:

namespace yxt
{template<class T, class Container = deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& front(){return _con.front();}const T& back(){return _con.back();}size_t size() const {return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

02 代码测试

先使用 deque 去存储

	void test_queue1(){queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;}

运行结果如下:

使用 list 去存储:

	void test_queue2(){queue<int, list<int>> q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;}

运行结果如下:

我们试一下,如果使用 vector 会怎么样:

	void test_queue3(){queue<int, vector<int>> q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;}

运行结果如下:

error C2039: "pop_front": 不是 "std::vector<int,std::allocator<T>>" 的成员
1>        with
1>        [
1>            T=int
1>        ]
1>D:\360MoveData\Users\Chaos\Desktop\code2022\2022_7_17\2022_7_17\test.cpp(62): message : 参见“std::vector<int,std::allocator<T>>”的声明
1>        with
1>        [
1>            T=int
1>        ]
1>D:\360MoveData\Users\Chaos\Desktop\code2022\2022_7_17\2022_7_17\test.cpp(14): message : 在编译 类 模板 成员函数“void foxny::queue<int,std::vector<int,std::allocator<T>>>::pop(void)”时……

Ⅲ . 模拟实现 priority_queue

01 实现思路

在优先级队列中,插入数据和删除数据的时间复杂度为 O(logN) 。

默认情况下的优先级队列是大堆,我们先不考虑用仿函数去实现兼容大堆小队排列问题,

我们先去实现大堆,先把基本的功能实现好,带着讲解完仿函数后再去进行优化实现

优先级队列相较于普通的队列,区别主要在 push 和 pop 上

需要在插入和删除的同时,增添调整的功能,并且 STL 的优先级队列是由堆来维护的

void push(const T& x) 
{_con.push_back(x);AdjustUp(_con.size() - 1);
}

入队时将数据插入后,从最后一个元素开始往上调整

出队时采用堆的删除手法,将根元素(即队头)和最后一个元素进行交换,并调用尾删

既然使用了头尾交换,我们就不得不对队列进行重新调整,所以从根位置进行下调,即可完成出队

void pop() 
{assert(!_con.empty());swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);
}

既然需要上调和下调操作,我们这里先暂时写死,设计成大堆的 AdjustUp 和 AdjustDown

/* 向上调整算法 */
void AdjustUp(size_t child) {size_t father = (child - 1) / 2;while (child > 0) {if (_con[father] < _con[child]) {swap(_con[father], _con[child]);child = father;father = (child - 1) / 2;}else {break;}}
}
/* 向下调整算法 */
void AdjustDown(size_t father) {size_t child = father * 2 + 1; // 默认认为左孩子大while (child < _con.size()) {// 判断右孩子是否存在,并且是否比左孩子大?if (child + 1 < _con.size() && _con[child] < _con[child + 1]) {child += 1;}if (_con[father] < _con[child]) {swap(_con[father], _con[child]);father = child;child = father * 2 + 1;}else {break;}}
}

 剩下的直接使用已有的接口即可

const T& top() {return _con[0];
}size_t size() const
{return _con.size();
}bool empty() const
{return _con.empty();
}

那这里的 top 接口,我们为什么要写成 const T&呢?

① 考虑到这里如果是 string,或更大的对象,传值返回就有一次拷贝构造,减少拷贝构造

② 如果允许随意修改堆顶数据,这是很危险的

02 大堆优先级队列

代码实现:

 

namespace yxt
{template<class T, class Container = vector<T>>class priority_queue{public:/* 向上调整算法 */void AdjustUp(size_t child) {size_t father = (child - 1) / 2;while (child > 0) {if (_con[father] < _con[child]) {swap(_con[father], _con[child]);child = father;father = (child - 1) / 2;}else {break;}}}/* 向下调整算法 */void AdjustDown(size_t father) {size_t child = father * 2 + 1; // 默认认为左孩子大while (child < _con.size()){// 判断右孩子是否存在,并且是否比左孩子大?if (child + 1 < _con.size() && _con[child] < _con[child + 1]) {child += 1;}if (_con[father] < _con[child]) {swap(_con[father], _con[child]);father = child;child = father * 2 + 1;}else {break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void pop(){assert(!_con.empty());swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

测试:

	void test_priority_queue1(){priority_queue<int> pq;pq.push(2);pq.push(5);pq.push(1);pq.push(6);pq.push(8);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;}

运行结果如下:

我们写死的话,如果想按升序排列,就没办法排了

如果想排升序我们需要写小堆

C++ 在这里有一种叫仿函数的东西,可以帮我们控制这些东西

03 仿函数

使一个类的使用看上去像一个函数,可以像函数一样使用的对象,称为函数对象

其实现就是在类中重载 operator() ,使得该类具备类似函数的行为,就是一个仿函数类了

代码实现:我们写一个最简单的仿函数

namespace yxt 
{struct less {// 仿函数(函数对象)———— 对象可以像调用函数一样去使用bool operator()(int x, int y) {return x < y;}};void test_functor() {less lessCmp;   // 定义一个对象(这里我用小驼峰,能看上去更像函数)cout << lessCmp(10, 20) << endl;   // 是对象,但是却能像函数一样去使用}
}

运行结果:1

我们定义的 lessCmp 是一个对象,但是我们却可以像使用函数一样给它传递参数

我们还可以使其能够支持泛型,我们加一个 template 模板:

// 支持泛型
template<class T> struct less {bool operator()(const T& x, const T& y) const {return x < y;}
};void test_functor() {less<int> lessCmp;cout << lessCmp(10, 20) << endl;
}

less 是用来比较谁小的,对应的,我们再实现一个比较谁大的 greater:

// less: 小于的比较
template<class T> struct less {bool operator()(const T& x, const T& y) const {return x < y;}
};
// greater: 大于的比较
template<class T> struct greater {bool operator()(const T& x, const T& y) const {return x > y;}
};void test_functor() {less<int> lessCmp;cout << lessCmp(10, 20) << endl;greater<int> GreaterCmp;cout << GreaterCmp(10, 20) << endl;
}

运行结果:1 0

一个对象能像函数一样用,看上去很神奇,实际上调用的只是我们重载的 operator() 而已。

这些操作都是归功于运算符重载功能,这就是仿函数!

04 优化后的优先级队列

代码实现:

namespace yxt
{// less:小于的比较template<class T>struct less{bool operator() (const T& x, const T& y) const{return x < y;}};// greater:大于的比较template<class T>struct greater{bool operator() (const T& x, const T& y) const{return x > y;}};template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{public:/* 向上调整算法 */void AdjustUp(size_t child) {Compare comFunc;size_t father = (child - 1) / 2;while (child > 0) {//if (_con[father] < _con[child]) if(comFunc(_con[father], _con[child])){swap(_con[father], _con[child]);child = father;father = (child - 1) / 2;}else {break;}}}/* 向下调整算法 */void AdjustDown(size_t father) {Compare comFunc;size_t child = father * 2 + 1; // 默认认为左孩子大while (child < _con.size()){// 判断右孩子是否存在,并且是否比左孩子大?//if (child + 1 < _con.size() && _con[child] < _con[child + 1]) if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1])){child += 1;}//if (_con[father] < _con[child]) if(comFunc(_con[father], _con[child])){swap(_con[father], _con[child]);father = child;child = father * 2 + 1;}else {break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void pop(){assert(!_con.empty());swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

测试:

	void test_priority_queue2(){priority_queue<int, vector<int>, greater<int>> pq;pq.push(2);pq.push(5);pq.push(1);pq.push(6);pq.push(8);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;}

运行结果如下:

这里的仿函数在编译器视角是这样的:

if (cmpFunc(_con[father], _con[child]))👇
if (cmpFunc.operator()(_con[father], _con[child]))👇// 以 less 为例template<class T> struct less {bool operator()(const T& x, const T& y) const {return x < y;}};最后返回 _con[father] < _con[child] ,true 还是 false

05 迭代器的实现

        // 创造空的优先级队列priority_queue():_con(){}// 迭代器template<class InputIterator>priority_queue(InputIterator first, InputIterator last): _con(first, last){while (first != last){_con.push_back(*first++);}for (int father = (_con.size() - 1 - 1) / 2; father >= 0; father++){AdjustDown(father);}}

可以拿这个来解决一些问题,比如 Top K

    void test_priority_queue3() {// TOP Kint arr[] = {1,4,2,7,8,9};priority_queue<int> pQ(arr, arr + 6);  // 传一个迭代器区间}

Ⅳ . 完整代码

01 stack

#pragma once
#include<deque>
using namespace std;namespace yxt
{template<class T,class Container = deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

02 queue

#pragma once
#include<deque>
using namespace std;namespace yxt
{template<class T, class Container = deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& front(){return _con.front();}const T& back(){return _con.back();}size_t size() const {return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

03 priority_queue

#pragma once
#include<assert.h>
#include<vector>
#include<functional>
using namespace std;namespace yxt
{// less:小于的比较template<class T>struct less{bool operator() (const T& x, const T& y) const{return x < y;}};// greater:大于的比较template<class T>struct greater{bool operator() (const T& x, const T& y) const{return x > y;}};template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{public:// 创造空的优先级队列priority_queue():_con(){}// 迭代器template<class InputIterator>priority_queue(InputIterator first, InputIterator last): _con(first, last){while (first != last){_con.push_back(*first++);}for (int father = (_con.size() - 1 - 1) / 2; father >= 0; father++){AdjustDown(father);}}/* 向上调整算法 */void AdjustUp(size_t child) {Compare comFunc;size_t father = (child - 1) / 2;while (child > 0) {//if (_con[father] < _con[child]) if(comFunc(_con[father], _con[child])){swap(_con[father], _con[child]);child = father;father = (child - 1) / 2;}else {break;}}}/* 向下调整算法 */void AdjustDown(size_t father) {Compare comFunc;size_t child = father * 2 + 1; // 默认认为左孩子大while (child < _con.size()){// 判断右孩子是否存在,并且是否比左孩子大?//if (child + 1 < _con.size() && _con[child] < _con[child + 1]) if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1])){child += 1;}//if (_con[father] < _con[child]) if(comFunc(_con[father], _con[child])){swap(_con[father], _con[child]);father = child;child = father * 2 + 1;}else {break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void pop(){assert(!_con.empty());swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

这篇关于十七、模拟 实现栈和队列类的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1112645

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注,收藏不迷路💖 Kubernetes的PodSecurityPolicy(PSP)是一个关键的安全特性,它在Pod创建之前实施安全策略,确保P

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s