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

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。

相关文章

Linux下删除乱码文件和目录的实现方式

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》：本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录
阅读更多...
SpringBoot+EasyExcel实现自定义复杂样式导入导出

SpringBoot+EasyExcel实现自定义复杂样式导入导出

《SpringBoot+EasyExcel实现自定义复杂样式导入导出》这篇文章主要为大家详细介绍了SpringBoot如何结果EasyExcel实现自定义复杂样式导入导出功能,文中的示例代码讲解详细,... 目录安装处理自定义导出复杂场景1、列不固定，动态列2、动态下拉3、自定义锁定行/列，添加密码4、合并
阅读更多...
mybatis执行insert返回id实现详解

mybatis执行insert返回id实现详解

《mybatis执行insert返回id实现详解》MyBatis插入操作默认返回受影响行数,需通过useGeneratedKeys+keyProperty或selectKey获取主键ID,确保主键为自... 目录 两种方式获取自增 ID：1. ​​useGeneratedKeys+keyProperty（推
阅读更多...
Spring Boot集成Druid实现数据源管理与监控的详细步骤

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控
阅读更多...
Linux在线解压jar包的实现方式

Linux在线解压jar包的实现方式

《Linux在线解压jar包的实现方式》：本文主要介绍Linux在线解压jar包的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux在线解压jar包解压 jar包的步骤总结Linux在线解压jar包在 Centos 中解压 jar 包可以使用 u
阅读更多...
c++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
Qt使用QSqlDatabase连接MySQL实现增删改查功能

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构
阅读更多...
基于Python实现一个图片拆分工具

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片，默认是输出到项目文件夹中，可以自己选择其他的文件夹，选择需要拆分的行数和列数，可以通过
阅读更多...
Python中将嵌套列表扁平化的多种实现方法

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表（即列表中包含列表）转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert
阅读更多...
Python使用pip工具实现包自动更新的多种方法

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2