[C++13]:stack queue priority_queue 模拟实现

stack && queue && priority_queue 模拟实现

  • 一.stack
    • 1.概念：
    • 2.使用：
    • 3.模拟实现：
    • 一些题目：
      • 1.最小栈：
      • 2.栈的压入弹出序列：
      • 3.逆波兰表达式求值：
  • 二.queue
    • 1.概念：
    • 2.使用：
    • 3.模拟实现：
    • 一个题目：
      • 1.层序遍历：
      • GIF解析
  • 三.priority_queue
    • 1.概念：
    • 2.一个题目：
      • 思路一：建堆+堆元素删除
      • 思路二：优化
    • 3.模拟实现：
    • 4.仿函数的应用：
      • 1.priority_queue()
      • 2.sort

一.stack

1.概念：

在这里插入图片描述

1.我们从stack的模板参数中看到第一个是stack中元素的类型。
2.第二个参数是一个有缺省值的参数类型，类型是一个deque类型。
3.deque是一个双端队列的一个容器(有list和vector的所有优点)
4.总结：stack其实不是一个容器，它叫做容器适配器，底层是对他使用的一个容器的接口的再封装。
5.底层的容器要满足以下接口：
push_back()
pop_back()
size()
empty()
back()

2.使用：

在这里插入图片描述

void test_1()
{
	stack<int> s_1;
	stack<int> s_2;

	s_1.push(1);
	s_1.push(2);
	s_1.push(3);
	s_1.push(4);
	s_1.pop();

	cout << s_1.top() <<endl;//3
	if (s_1.empty())
		cout << "当前栈为空！" << endl;//当前栈不为空
	else
		cout << "当前栈不为空！" << endl;

	s_2 = s_1;
	s_2.pop();
	s_1.swap(s_2);

	while (!s_1.empty())
	{
		cout << s_1.top() << " ";
		s_1.pop();
	}
	//2 1
	cout << endl;
	while (!s_2.empty())
	{
		cout << s_2.top() << " ";
		s_2.pop();
	}
	//3 2 1
	cout << endl;
}

1.容器适配器是没有迭代器的，容器适配器不是容器，容器才有迭代器。
2.遍历容器适配器的元素有自己对应的方法。
3.没有给模板传第二个参数所以使用默认的双端队列作为底层容器。
4.使用vector作为底层的容器也是可以的！

在这里插入图片描述

3.模拟实现：

1.有了上面的stack基本概念和使用的介绍，我们想要去模拟实现一个stack。
2.有了底层的容器在底层容器的基础之上进行封装是非常方便的。

#include<iostream>
#include<vector>
using namespace std;

namespace sfpy {
	//1.默认使用的vector作为我们的底层容器：
	template<class T , class Container = vector<T>>
	class stack {
		//1.需要提供构造函数？
		//回答：不需要没有提供构造函数自定义类型回去调用它的默认构造。
	public:
		size_t size()
		{
			return vessel.size();
		}
		bool empty()
		{
			return vessel.empty();
		}
		void push(T x)
		{
			vessel.push_back(x);
		}
		void pop()
		{
			vessel.pop_back();
		}
		T top()
		{
			return vessel.back();
		}
	private:
		Container vessel;
	};
}

一些题目：

在这里插入图片描述

最小栈

1.最小栈：

思路一：
1.定义两个栈第一个栈(Stack)用来正常保存数据，第二个栈(StackMin)用来保存较小的数据值。
2.特殊情况：
2-1：马上要push的数据小于等于StackMIn栈顶的值就两个栈都push。
2-1：pop数据需要判断Stack.top()和StackMIn.top()值相等就都pop.
2-1: 不这样处理的话出现连续相同的较小值对于pop来说，如果StackMin只记录较小值一次的话。Stack还有这个数据但是StackMIn中这个值就没有了getmin方法就不对了。

class MinStack {
public:
    MinStack() {
        
    }
    
    void push(int val) {
        Stack.push(val);
        if(StackMin.empty() )
            StackMin.push(val);
        else
        {
            int top = StackMin.top();
            if(val <= top)
            {
                StackMin.push(val);
            }
        } 
    }
    
    void pop() {
        if(Stack.top() == StackMin.top())
            StackMin.pop();

        Stack.pop();
    }
    
    int top() {
        return Stack.top();
    }
    
    int getMin() {
        return StackMin.top();
    }

    stack<int> Stack;
    stack<int> StackMin;
};

2.栈的压入弹出序列：

请添加图片描述
栈的压入弹出序列

思路一：双指针模拟

在这里插入图片描述

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int整型vector
     * @param popV int整型vector
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        int pushi = 0, popi = 0;
        stack<int> st;
        while (popi < popV.size())
        {
            //2 1 0
            //1 2 0

            int tmp = popV[popi];
            while (pushi < pushV.size())
            {
                //1.出栈判断：
                if (!st.empty() && st.top() == tmp)
                {
                    st.pop();
                    popi++;
                    break;
                }
                else
                {
                    st.push(pushV[pushi++]);
                    continue;
                }
                //2.进入数据：
                st.push(pushV[pushi++]);
                popi++;
            }
            if (!st.empty() && pushi == pushV.size())
            {
                while (!st.empty() && st.top() == popV[popi])
                {
                    st.pop();
                    popi++;
                }
                break;
            }
                
        }
        return st.empty();
    }
};

3.逆波兰表达式求值：

在这里插入图片描述

逆波兰表达式求值

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s1;
        for(auto& tmp:tokens)
        {
            //1.字符栈:
            if(tmp=="+" || tmp=="-" || tmp=="*" || tmp=="/")
            {
                int right = s1.top();
                s1.pop();
                int left = s1.top();
                s1.pop();

                char ch = tmp[0];
                switch(ch)
                {
                    case '+':
                        s1.push(left+right);
                        break;
                    case '-':
                        s1.push(left-right);
                        break;
                    case '*':
                        s1.push(left*right);
                        break;
                    case '/':
                        s1.push(left/right);
                        break;
                }
            }
            //2.数值栈：
            else
            {
                s1.push(stoi(tmp));
            }
        }
        return s1.top();
    }   
};

二.queue

1.概念：

在这里插入图片描述

1.我们从queue的模板参数中看到第一个是queue中元素的类型。
2.第二个参数是一个有缺省值的参数类型，类型是一个deque类型。
3.deque是一个双端队列的一个容器(有list和vector的所有优点)
4.总结：queue其实不是一个容器，它叫做容器适配器，底层是对他使用的一个容器的接口的再封装。
5.底层的容器要满足以下接口：
push_back()
pop_front()
size()
empty()
back()
front()

2.使用：

void test_3()
{
	queue<int> q_1;

	//1.入数据并且获取队尾数据：
	for (int i = 0; i < 6; i++)
	{
		q_1.push(i);
		cout << q_1.back() << " ";
	}
	//0 1 2 3 4 5
	cout << endl;
	cout << "queue size:" << q_1.size() << endl;
	//queue size 5
	//2.提取队头数据并且出数据：
	while (!q_1.empty())
	{
		cout << q_1.front() << " ";
		q_1.pop();
	}
	//0 1 2 3 4 5 
	cout << endl;
}

3.模拟实现：

1.有了上面的stack基本概念和使用的介绍，我们想要去模拟实现一个stack。
2.有了底层的容器在底层容器的基础之上进行封装是非常方便的。

#include<iostream>
#include<list>

using namespace std;

namespace sfpy {
	template<class T , class Container = list<T>>
	class queue {
	public:
		//1.不需要实现构造函数，自定义类型会去调用自己的默认构造：

		bool empty()
		{
			return vessel.empty();
		}
		size_t size()
		{
			return vessel.size();
		}
		T front()
		{
			return vessel.front();
		}
		T back()
		{
			return vessel.back();
		}
		void push(T x)
		{
			vessel.push_back(x);
		}
		void pop()
		{
			vessel.pop_front();
		}


	private:
		Container vessel;
	};
}

在这里插入图片描述

一个题目：

1.层序遍历：

在这里插入图片描述

二叉树的层序遍历

思路一：使用队列模拟每一层数据的遍历：

在这里插入图片描述

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vv;
        if(root == nullptr)
            return vv;

        queue<TreeNode*> s;
        s.push(root);
        int num = s.size();
        vector<int> tmp;
        while(!s.empty())
        {
            TreeNode* top = s.front();
            tmp.push_back(top->val);
            s.pop();
            num--;

            if(top->left!=nullptr)
                s.push(top->left);
            if(top->right!=nullptr)
                s.push(top->right);

            if(num==0)
            {
                num = s.size();
                vv.push_back(tmp);
                tmp.resize(0);
            }
        }
        return vv;
    }
};

GIF解析

在这里插入图片描述

三.priority_queue

1.概念：

在这里插入图片描述

1,priority_queue是一个容器适配器。
2.priority_queue底层是一个顺序表容器，并且同时使用了堆的算法实现了一个堆的结构。
3.默认情况下priority_queue是一个大堆。

2.一个题目：

在这里插入图片描述

数组中第k大的元素

思路一：建堆+堆元素删除

1.用所有的元素进行建堆。
2.删除k-1个元素当前的堆顶就是第k大的元素。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> heap(nums.begin() , nums.end());
        while(--k)
        {
            heap.pop();
        }
        return heap.top();
    }
};

在这里插入图片描述

思路二：优化

1.如果N(nums这个顺序表中的总元素的个数)和k的数值比较接近的话那么时间复杂度度是比较高的。
2.使用topk算法的思路衍生。
3.开始建立k个元素的一个小堆遍历剩下所有数据到小堆中遍历完成后堆顶就是第k大的元素。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //1.建立一个小堆：最后一个模板参数换成greater比较方法
        priority_queue<int,vector<int>,greater<int>> heap(nums.begin() , nums.begin()+k);
        //2.遍历剩下的数据：
        for(int i = k ; i<nums.size() ; i++)
        {
            int n = nums[i];
            if(heap.top() < n)
            {
                heap.pop();
                heap.push(n);
            }
        }
        //3.返回堆顶数据：
        return heap.top();
    }
};

在这里插入图片描述

3.模拟实现：

1.priority_queue的底层是一个顺序表。
2.提供了堆的算法实现了一个堆结构。
3.提供两个比较类类中实现对operator()的定义，实现比较函数，提供不同的比较函数，创造不同的堆类型。
4.模板参数提供了一个仿函数的东西，仿函数不是函数是一个模板参数，是一个自定义类型的模板参数，并且类型中重载了operator(),这样在方法中实例化一个对象之后就可以使用通过重载（）实现的一个方法。

#include<iostream>
#include<vector>
using namespace std;

namespace sfpy {
	template<class T>
	class less
	{
	public:
		bool operator()(T x , T b)
		{
			return x > b;
		}
	};
	template<class T>
	class greater
	{
	public:
		bool operator()(T x, T b)
		{
			return x < b;
		}
	};

	template<class T , class Container = vector<T> , class Compare = less<int>>
	class priority_queue {
	private:
		void adjust_up(int n)
		{
			Compare com;

			int child = n;
			int parent = (n - 1) / 2;

			while (child > 0)
			{
				if(com(heap[child], heap[parent]))
					swap(heap[child], heap[parent]);

				child = parent;
				parent = (child - 1) / 2;
			}
		}
		void adjust_down()
		{
			Compare com;

			//1.使用假设法：
			int parent = 0;
			int child = (parent * 2) + 1;

			while (child < heap.size())
			{
				if (child + 1 < heap.size() && com(heap[child + 1], heap[child]))
					child++;
				
				if (com(heap[child], heap[parent]))
					swap(heap[child], heap[parent]);
				else
					break;

				parent = child;
				child = (parent * 2) + 1;
			}
		}
	public:
		//1.push
		void push(T x)
		{
			//1.插入数据到顺序表中：
			heap.push_back(x);
			//2.走向上调整算法：
			adjust_up(heap.size() - 1);
		}
		//2.pop
		void pop()
		{
			//1.首位交换：
			swap(heap[0], heap[heap.size() - 1]);
			//2.删除尾数据：
			heap.pop_back();
			//3.向下调整算法把交换好的值调整到合适的位置。
			adjust_down();
		}
		bool empty() { return heap.empty(); }
		size_t size() { return heap.size(); }
		T top() { return heap.front(); }
	private:
		Container heap;
	};
}

4.仿函数的应用：

1.仿函数顾名思义不是一个函数仿照函数实现的一个类。
2.这个类提供一个operator()的成员方法去控制大小比较等内容。
3.对于模板参数来说传递类型。
4.对于函数参数来说传递对象。

1.priority_queue()

template<class T>
	class less
	{
	public:
		bool operator()(T x , T b)
		{
			return x > b;
		}
	};
	template<class T>
	class greater
	{
	public:
		bool operator()(T x, T b)
		{
			return x < b;
		}
	};
	
template<class T , class Container = vector<T> , class Compare = less<int>>
	class priority_queue {
	private:
		void adjust_up(int n)
		{
			Compare com;

			int child = n;
			int parent = (n - 1) / 2;

			while (child > 0)
			{
				if(com(heap[child], heap[parent]))
					swap(heap[child], heap[parent]);

				child = parent;
				parent = (child - 1) / 2;
			}
		}
		void adjust_down()
		{
			Compare com;

			//1.使用假设法：
			int parent = 0;
			int child = (parent * 2) + 1;

			while (child < heap.size())
			{
				if (child + 1 < heap.size() && com(heap[child + 1], heap[child]))
					child++;
				
				if (com(heap[child], heap[parent]))
					swap(heap[child], heap[parent]);
				else
					break;

				parent = child;
				child = (parent * 2) + 1;
			}
		}
……………………………………
……………………………………………………

1.通过函数模板参数传递类类型进来，类型有一个默认的类类型实现了堆默认是大堆的一个情况。
2.通过传递模板参数的类型可以实现大小堆的转换。
3.在类中通过实例化一个对象，调用对象方法可以实现不同的比较逻辑。
4.通过不同的比较逻辑实现不同类型的堆。

2.sort

1.这个地方是直接通过函数参数传递一个实参:类对象。
2.在sort函数里面调用类中的operator()方法实现对数据的比较。
3.从而达到一个排升序和降序的效果。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/351976.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

SpringBoot之时间数据前端显示格式化

SpringBoot之时间数据前端显示格式化

背景 在实际我们通常需要在前端显示对数据操作的时间或者最近的更新时间&#xff0c;如果我们只是简单的使用 LocalDateTime.now()来传入数据不进行任何处理那么我们就会得到非常难看的数据 解决方式&#xff1a; 1). 方式一 在属性上加上注解&#xff0c;对日期进行格式…
阅读更多...
Web3 游戏开发者的数据分析指南

Web3 游戏开发者的数据分析指南

作者&#xff1a;lesleyfootprint.network 在竞争激烈的 Web3 游戏行业中&#xff0c;成功不仅仅取决于游戏的发布&#xff0c;还需要在游戏运营过程中有高度的敏锐性&#xff0c;以应对下一次牛市的来临。 人们对 2024 年的游戏行业充满信心。A16Z GAMES 和 GAMES FUND ONE …
阅读更多...
探索IOC和DI：解密Spring框架中的依赖注入魔法

探索IOC和DI：解密Spring框架中的依赖注入魔法

IOC与DI的详细解析 IOC详解1 bean的声明2 组件扫描 DI详解 IOC详解 1 bean的声明 IOC控制反转&#xff0c;就是将对象的控制权交给Spring的IOC容器&#xff0c;由IOC容器创建及管理对象。IOC容器创建的对象称为bean对象。 要把某个对象交给IOC容器管理&#xff0c;需要在类上…
阅读更多...
深度学习知识

深度学习知识

context阶段和generation阶段的不同 context阶段&#xff08;又称 Encoder&#xff09;主要对输入编码&#xff0c;产生 CacheKV(CacheKV 实际上记录的是 Transformer 中 Attention 模块中 Key 和 Value 的值&#xff09;&#xff0c;在计算完 logits 之后会接一个Sampling 采…
阅读更多...
【MySQL进阶】InnoDB引擎存储结构和架构

【MySQL进阶】InnoDB引擎存储结构和架构

文章目录 逻辑存储结构架构内存结构Buffer Pool&Adaptive Hash IndexChange BufferLog Buffer 磁盘结构 逻辑存储结构 表空间&#xff08;Tablespaces&#xff09;&#xff1a;InnoDB使用表空间来管理存储表和索引的数据文件。每个表空间包含一个或多个数据文件&#xff0c…
阅读更多...
【学网攻】 第(9)节 -- 路由器使用以及原理

【学网攻】 第(9)节 -- 路由器使用以及原理

系列文章目录 目录 系列文章目录 文章目录 前言 一、路由器是什么&#xff1f; 二、实验 1.引入 总结 文章目录 【学网攻】 第(1)节 -- 认识网络【学网攻】 第(2)节 -- 交换机认识及使用【学网攻】 第(3)节 -- 交换机配置聚合端口【学网攻】 第(4)节 -- 交换机划分Vlan…
阅读更多...
解锁一些SQL注入的姿势

解锁一些SQL注入的姿势

昨天课堂上布置了要去看一些sql注入的案例&#xff0c;以下是我的心得&#xff1a; ​​​​​​​ ​​​​​​​ ​​​​​​​ 1.新方法 打了sqli的前十关&#xff0c;我发现一般都是联合查询&#xff0c;但是有没有不是联合查询的方法呢&#xf…
阅读更多...
Python基础学习 -05 基本类型

Python基础学习 -05 基本类型

Python3 基本数据类型 Python 中的变量不需要声明。每个变量在使用前都必须赋值&#xff0c;变量赋值以后该变量才会被创建。 在 Python 中&#xff0c;变量就是变量&#xff0c;它没有类型&#xff0c;我们所说的"类型"是变量所指的内存中对象的类型。 等号&…
阅读更多...
Nodejs前端学习Day1_补档

Nodejs前端学习Day1_补档

我给day1搞没了&#xff0c;还是觉得该补一个&#xff0c;有用 文章目录 前言一、学习目标二、学习目录三、为什么JavaScript代码可以在浏览器中运行四、为什么JavaScript可以操作DOM和BOM五、浏览器中的JavaScript运行环境总结 前言 补档 一、学习目标 二、学习目录 三、为什…
阅读更多...
苹果备忘录删除了怎么恢复？看这，5分钟学会4种方法

苹果备忘录删除了怎么恢复？看这，5分钟学会4种方法

在日常使用中&#xff0c;我们有时会不小心删除苹果备忘录中的重要内容。这些内容可能是重要的提醒、重要的日程安排&#xff0c;也可能是珍贵的回忆。一旦删除&#xff0c;可能会对我们的生活和工作带来很大的困扰。那么&#xff0c;苹果备忘录删除了怎么恢复呢&#xff1f;本…
阅读更多...
小屏幕大作用 电子墨水屏桌牌、门牌—构建绿色办公环境新途径

小屏幕大作用 电子墨水屏桌牌、门牌—构建绿色办公环境新途径

在当今信息化社会&#xff0c;电子设备已经深入到我们生活的方方面面。其中&#xff0c;电子墨水屏作为一种特殊的显示技术&#xff0c;因其低功耗、护眼、节能环保等特点&#xff0c;受到了广泛欢迎。本文将探讨电子墨水屏在构建绿色办公环境中的重要作用&#xff0c;特别是电…
阅读更多...
上位机图像处理和嵌入式模块部署（python opencv）

上位机图像处理和嵌入式模块部署（python opencv）

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 前面我们谈到了qt&#xff0c;谈到了opencv&#xff0c;也谈到了嵌入式&#xff0c;但是没有说明python在这个过程当中应该扮演什么样的角色。open…
阅读更多...
无线测温在线监测系统工作原理与产品选型

无线测温在线监测系统工作原理与产品选型

摘要&#xff1a;本文首先介绍了无线测温在线监测系统的基本工作原理以及软硬件组成&#xff0c;重点介绍了在线监测的无线测温技术特点。在此研究基础上&#xff0c;探讨了无线测温在线监测系统在实际工作场景中的应用案例&#xff0c;证明了其在温度检测方面的重要应用价值。…
阅读更多...
FlashInternImage实战：使用FlashInternImage实现图像分类任务（一）

FlashInternImage实战：使用FlashInternImage实现图像分类任务（一）

文章目录 摘要安装包安装timm 数据增强Cutout和MixupEMA项目结构编译安装DCNv4环境安装过程配置CUDAHOME解决权限不够的问题 按装ninja编译DCNv4 计算mean和std生成数据集 摘要 https://arxiv.org/pdf/2401.06197.pdf 论文介绍了Deformable Convolution v4&#xff08;DCNv4&…
阅读更多...
#include＜iomanip＞前不可以加#define int long long

#include＜iomanip＞前不可以加#define int long long

加了会报许多奇怪的错 但是放后面就可以了 尽量不要在头文件前宏定义原始类型
阅读更多...
防御保护---安全策略

防御保护---安全策略

文章目录 目录 一.安全策略概述 概述&#xff1a; 安全策略的作用&#xff1a; 安全策略与传统防火墙的区别 二.案例分析 练习 一.安全策略概述 概述&#xff1a; 防火墙安全策略的作用在于加强网络系统的安全性&#xff0c;保护网络免受恶意攻击、非法访问和数据泄露的威胁。…
阅读更多...
分享一个可以免费下载高清图片和视频的网站

分享一个可以免费下载高清图片和视频的网站

据说很多才华横溢的摄影作者在这里免费分享最精彩的素材图片和视频。 完全开放免费 来看其中的一些图片&#xff1a; 多的就不发了&#xff0c;视频素材也有&#xff01;都是一些顶尖摄影师上传的作品 这个宝藏网站是&#xff0c;现有需要的小伙伴可以收藏起来 https://www…
阅读更多...
【广度优先搜索】【拓扑排序】【C++算法】913. 猫和老鼠

【广度优先搜索】【拓扑排序】【C++算法】913. 猫和老鼠

作者推荐 【动态规划】【map】【C算法】1289. 下降路径最小和 II 本文涉及知识点 广度优先搜索 拓扑排序 逆推 LeetCode913. 猫和老鼠 两位玩家分别扮演猫和老鼠&#xff0c;在一张 无向 图上进行游戏&#xff0c;两人轮流行动。 图的形式是&#xff1a;graph[a] 是一个列…
阅读更多...
python-分享篇-使用海龟turtle模块实现幸福大转盘

python-分享篇-使用海龟turtle模块实现幸福大转盘

文章目录 准备代码效果 准备 一、根目录下放图片 代码 from turtle import * import turtle from random import randint import sys #屏幕初始化 screen turtle.Screen() screen.title("幸运大转盘 转转转~") screen.setup(480,450) screen.bgpic("转盘.png…
阅读更多...
基于机器学习的地震预测（Earthquake Prediction with Machine Learning）

基于机器学习的地震预测（Earthquake Prediction with Machine Learning）

基于机器学习的地震预测&#xff08;Earthquake Prediction with Machine Learning&#xff09; 一、地震是什么二、数据组三、使用的工具和库四、预测要求五、机器学习进行地震检测的步骤六、总结 一、地震是什么 地震几乎是每个人都听说过或经历过的事情。地震基本上是一种自…
阅读更多...
最新文章

Copyright @ 2022~2023