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

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。

相关文章

Redis分片集群的实现

Redis分片集群的实现

《Redis分片集群的实现》Redis分片集群是一种将Redis数据库分散到多个节点上的方式,以提供更高的性能和可伸缩性,本文主要介绍了Redis分片集群的实现,具有一定的参考价值,感兴趣的可以了解一... 目录1. Redis Cluster的核心概念哈希槽（Hash Slots）主从复制与故障转移2.
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
使用Python实现一键隐藏屏幕并锁定输入

使用Python实现一键隐藏屏幕并锁定输入

《使用Python实现一键隐藏屏幕并锁定输入》本文主要介绍了使用Python编写一个一键隐藏屏幕并锁定输入的黑科技程序,能够在指定热键触发后立即遮挡屏幕,并禁止一切键盘鼠标输入,这样就再也不用担心自己... 目录1. 概述2. 功能亮点3.代码实现4.使用方法5. 展示效果6. 代码优化与拓展7. 总结1.
阅读更多...
Mybatis 传参与排序模糊查询功能实现

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》：本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的
阅读更多...
Docker镜像修改hosts及dockerfile修改hosts文件的实现方式

Docker镜像修改hosts及dockerfile修改hosts文件的实现方式

《Docker镜像修改hosts及dockerfile修改hosts文件的实现方式》：本文主要介绍Docker镜像修改hosts及dockerfile修改hosts文件的实现方式,具有很好的参考价... 目录docker镜像修改hosts及dockerfile修改hosts文件准备 dockerfile 文
阅读更多...
基于SpringBoot+Mybatis实现Mysql分表

基于SpringBoot+Mybatis实现Mysql分表

《基于SpringBoot+Mybatis实现Mysql分表》这篇文章主要为大家详细介绍了基于SpringBoot+Mybatis实现Mysql分表的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录基本思路定义注解创建ThreadLocal创建拦截器业务处理基本思路1.根据创建时间字段按年进
阅读更多...
SpringBoot3实现Gzip压缩优化的技术指南

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N
阅读更多...
SpringBoot实现数据库读写分离的3种方法小结

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一：基于AbstractRoutingDataSource实现动态
阅读更多...
Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整
阅读更多...
Java枚举类实现Key-Value映射的多种实现方式

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2