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

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。

相关文章

HTML5实现的移动端购物车自动结算功能示例代码

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.
阅读更多...
基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码，该代码实现了图片的旋转（90度和180度）以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中，
阅读更多...
SpringBoot中使用Flux实现流式返回的方法小结

SpringBoot中使用Flux实现流式返回的方法小结

《SpringBoot中使用Flux实现流式返回的方法小结》文章介绍流式返回（StreamingResponse）在SpringBoot中通过Flux实现,优势包括提升用户体验、降低内存消耗、支持长连... 目录背景流式返回的核心概念与优势1. 提升用户体验2. 降低内存消耗3. 支持长连接与实时通信在Sp
阅读更多...
Conda虚拟环境的复制和迁移的四种方法实现

Conda虚拟环境的复制和迁移的四种方法实现

《Conda虚拟环境的复制和迁移的四种方法实现》本文主要介绍了Conda虚拟环境的复制和迁移的四种方法实现,包括requirements.txt,environment.yml,conda-pack,... 目录在本机复制Conda虚拟环境相同操作系统之间复制环境方法一：requirements.txt方法
阅读更多...
Spring Boot 实现 IP 限流的原理、实践与利弊解析

Spring Boot 实现 IP 限流的原理、实践与利弊解析

《SpringBoot实现IP限流的原理、实践与利弊解析》在SpringBoot中实现IP限流是一种简单而有效的方式来保障系统的稳定性和可用性,本文给大家介绍SpringBoot实现IP限... 目录一、引言二、IP 限流原理2.1 令牌桶算法2.2 漏桶算法三、使用场景3.1 防止恶意攻击3.2 控制资源
阅读更多...
springboot下载接口限速功能实现

springboot下载接口限速功能实现

《springboot下载接口限速功能实现》通过Redis统计并发数动态调整每个用户带宽,核心逻辑为每秒读取并发送限定数据量,防止单用户占用过多资源,确保整体下载均衡且高效,本文给大家介绍spring... 目录 一、整体目标 二、涉及的主要类/方法✅ 三、核心流程图解（简化） 四、关键代码详解1️⃣ 设置
阅读更多...
Nginx 配置跨域的实现及常见问题解决

Nginx 配置跨域的实现及常见问题解决

《Nginx配置跨域的实现及常见问题解决》本文主要介绍了Nginx配置跨域的实现及常见问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来... 目录1. 跨域1.1 同源策略1.2 跨域资源共享（CORS）2. Nginx 配置跨域的场景2.1
阅读更多...
Python中提取文件名扩展名的多种方法实现

Python中提取文件名扩展名的多种方法实现

《Python中提取文件名扩展名的多种方法实现》在Python编程中,经常会遇到需要从文件名中提取扩展名的场景,Python提供了多种方法来实现这一功能,不同方法适用于不同的场景和需求,包括os.pa... 目录技术背景实现步骤方法一：使用os.path.splitext方法二：使用pathlib模块方法三
阅读更多...
CSS实现元素撑满剩余空间的五种方法

CSS实现元素撑满剩余空间的五种方法

《CSS实现元素撑满剩余空间的五种方法》在日常开发中，我们经常需要让某个元素占据容器的剩余空间，本文将介绍5种不同的方法来实现这个需求，并分析各种方法的优缺点，感兴趣的朋友一起看看吧... css实现元素撑满剩余空间的5种方法 在日常开发中，我们经常需要让某个元素占据容器的剩余空间。这是一个常见的布局需求
阅读更多...
HTML5 getUserMedia API网页录音实现指南示例小结

HTML5 getUserMedia API网页录音实现指南示例小结

《HTML5getUserMediaAPI网页录音实现指南示例小结》本教程将指导你如何利用这一API，结合WebAudioAPI，实现网页录音功能,从获取音频流到处理和保存录音，整个过程将逐步... 目录1. html5 getUserMedia API简介1.1 API概念与历史1.2 功能与优势1.3
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2