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

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。

相关文章

SpringBoot集成redisson实现延时队列教程

SpringBoot集成redisson实现延时队列教程

《SpringBoot集成redisson实现延时队列教程》文章介绍了使用Redisson实现延迟队列的完整步骤,包括依赖导入、Redis配置、工具类封装、业务枚举定义、执行器实现、Bean创建、消费... 目录1、先给项目导入Redisson依赖2、配置redis3、创建 RedissonConfig 配
阅读更多...
Python的Darts库实现时间序列预测

Python的Darts库实现时间序列预测

《Python的Darts库实现时间序列预测》Darts一个集统计、机器学习与深度学习模型于一体的Python时间序列预测库,本文主要介绍了Python的Darts库实现时间序列预测,感兴趣的可以了解... 目录目录一、什么是 Darts？二、安装与基本配置安装 Darts导入基础模块三、时间序列数据结构与
阅读更多...
Python使用FastAPI实现大文件分片上传与断点续传功能

Python使用FastAPI实现大文件分片上传与断点续传功能

《Python使用FastAPI实现大文件分片上传与断点续传功能》大文件直传常遇到超时、网络抖动失败、失败后只能重传的问题,分片上传+断点续传可以把大文件拆成若干小块逐个上传,并在中断后从已完成分片继... 目录一、接口设计二、服务端实现（FastAPI）2.1 运行环境2.2 目录结构建议2.3 serv
阅读更多...
C#实现千万数据秒级导入的代码

C#实现千万数据秒级导入的代码

《C#实现千万数据秒级导入的代码》在实际开发中excel导入很常见,现代社会中很容易遇到大数据处理业务,所以本文我就给大家分享一下千万数据秒级导入怎么实现,文中有详细的代码示例供大家参考,需要的朋友可... 目录前言一、数据存储二、处理逻辑优化前代码处理逻辑优化后的代码总结前言在实际开发中excel导入很
阅读更多...
SpringBoot+RustFS 实现文件切片极速上传的实例代码

SpringBoot+RustFS 实现文件切片极速上传的实例代码

《SpringBoot+RustFS实现文件切片极速上传的实例代码》本文介绍利用SpringBoot和RustFS构建高性能文件切片上传系统,实现大文件秒传、断点续传和分片上传等功能,具有一定的参考... 目录一、为什么选择 RustFS + SpringBoot？二、环境准备与部署2.1 安装 RustF
阅读更多...
Nginx部署HTTP/3的实现步骤

Nginx部署HTTP/3的实现步骤

《Nginx部署HTTP/3的实现步骤》本文介绍了在Nginx中部署HTTP/3的详细步骤,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录前提条件第一步：安装必要的依赖库第二步：获取并构建 BoringSSL第三步：获取 Nginx
阅读更多...
MyBatis Plus实现时间字段自动填充的完整方案

MyBatis Plus实现时间字段自动填充的完整方案

《MyBatisPlus实现时间字段自动填充的完整方案》在日常开发中,我们经常需要记录数据的创建时间和更新时间,传统的做法是在每次插入或更新操作时手动设置这些时间字段,这种方式不仅繁琐,还容易遗漏,... 目录前言解决目标技术栈实现步骤1. 实体类注解配置2. 创建元数据处理器3. 服务层代码优化填充机制详
阅读更多...
Python实现Excel批量样式修改器(附完整代码)

Python实现Excel批量样式修改器(附完整代码)

《Python实现Excel批量样式修改器(附完整代码)》这篇文章主要为大家详细介绍了如何使用Python实现一个Excel批量样式修改器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录前言功能特性核心功能界面特性系统要求安装说明使用指南基本操作流程高级功能技术实现核心技术栈关键函
阅读更多...
Java实现字节字符转bcd编码

Java实现字节字符转bcd编码

《Java实现字节字符转bcd编码》BCD是一种将十进制数字编码为二进制的表示方式,常用于数字显示和存储,本文将介绍如何在Java中实现字节字符转BCD码的过程,需要的小伙伴可以了解下... 目录前言BCD码是什么Java实现字节转bcd编码方法补充总结前言BCD码（Binary-Coded Decima
阅读更多...
SpringBoot全局域名替换的实现

SpringBoot全局域名替换的实现

《SpringBoot全局域名替换的实现》本文主要介绍了SpringBoot全局域名替换的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录 项目结构⚙️ 配置文件application.yml️ 配置类AppProperties.Ja
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2