【C++】——Stack与Queue(含优先队列(详细解读)

前言

之前数据结构中是栈和队列,我们分别用的顺序表和链表去实现的,但是对于这里的栈和队列来说,他们是一种容器,更准确来说是一种容器适配器

✨什么是容器适配器?

 从他们的模板参数可以看出,第二个参数模板是一个容器,并不像vector和list一样是一个内存池

至于deque后面会介绍

这里写传容器的原因就是,栈和队列是直接复用了其他的容器,用他们的功能实现自己的功能,就比如每家的电压和自己手机充电器的电压是不一样的,但是我用一个适配器就可以转换出来

 

一  Stakc的介绍和使用

1.1 Stakc介绍

  1. stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。
  2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出。
  3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:
empty:判空操作
back:获取尾部元素操作
push_back:尾部插入元素操作
pop_back:尾部删除元素操作
  4. 标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque。

Stack是没有迭代器的,因为栈不能说是去遍历每个元素,而是后进先出的结构,所以设计迭代器没有任何意义,虽然可以去设计

 

1.2  栈的使用 

 对于之前数据结构来说,我们需要自己写一个栈,这里就直接引入头文件就行。

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<list>
#include<stack>
using namespace std;
int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	st.push(5);
	int n = st.size();
	while (n--)
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl;
}

 

这里只是一个简单的演示

下面来做一个题目:

155. 最小栈

提示

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

输入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出:
[null,null,null,null,-3,null,0,-2]

解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示:

  • -231 <= val <= 231 - 1
  • poptop 和 getMin 操作总是在 非空栈 上调用
  • pushpoptop, and getMin最多被调用 3 * 104 次

 思路:

对于这道题目来说,要拿出最小的那个元素,那么我们必须去记录,如果我们用一个变量去保存这个最小值肯定是不行的,因为我们用这个变量保存一个最小值以后,然后我们再删这个最小值,那当前最小就不知道是谁了,得重新来一遍,这样虽然可行,但是在时间效率上可能会很低

所以解决这道题可以用两个栈去模拟,一个栈存最小值,一个栈做为入栈,只要比最小栈的最小元素还小的时候(就是栈顶元素)就可以加入到这个最小栈里面,我们删除数据的时候,如果删除的数据和栈顶元素相等,那么我们把最小栈的元素删除,否则不动。

有了思路,现在来写代码就简单很多了

class MinStack {
public:
    MinStack() {

    }
    
    void push(int val) {
        _elem.push(val);//先入
        if(_min.empty()||val<=_min.top())//如果最小栈是空或者当前值比最小栈的栈顶元素还小就加入
        {
            _min.push(val);
        }
    }
    
    void pop() {
        if(_elem.top()==_min.top())//相等就一起删,最后最小栈栈顶元素就是最小的
        {
            _min.pop();
        }
        _elem.pop();
    }
    
    int top() {
        return _elem.top();//其他函数按规则来就行
    }
    
    int getMin() {
        return _min.top();
    }
    private:
    std::stack<int> _elem;//设置两个栈
    std::stack<int> _min;
    
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

  二  Queue的介绍和使用

2.1 队列的介绍

1. 队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。
2. 队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队头出队列
3. 底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作 :
empty:检测队列是否为空
size:返回队列中有效元素的个数
front:返回队头元素的引用
back:返回队尾元素的引用
push_back:在队列尾部入队列
pop_front:在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。

 

2.2  队列的使用 

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<queue>
using namespace std;
int main()
{
	queue<int>q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	int n = q.size();
	while (n--)
	{
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;
	return 0;
}

三  优先级队列的介绍和使用

3.1 优先队列介绍

   1. 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
    2. 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元 素)。
    3. 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。
    4. 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:
    empty():检测容器是否为空
    size():返回容器中有效元素个数
    front():返回容器中第一个元素的引用
    push_back():在容器尾部插入元素 

    pop_back():删除容器尾部元素
   5. 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定priority_queue类实例化指定容器类,则使用vector。
6. 需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

优先队列有三个模板参数,一个是 数据类型,一个是容器,一个是比较模板

到这里我们可以得知优先队列默认就是一个大堆

其中比较这里的比较采用的是模板,并不是之前的函数,但是这里可以用比较函数去进行,也就是用一个函数指针,但是c++不喜欢这种做法,并引伸出了仿函数

✨仿函数

仿函数就是把一个写成函数的形式

template<class T>
class less
{
public:
	bool operator(const T&x,const T& y)
	{
		return x < y;
	}
};

这里是一个比较大小的仿函数,同时也是一个模板类型, 如果确定类型也可以不用写成模板类型

我们可以直接用这个作为比较函数,完成比较。

3.2 优先队列的使用

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include <functional>
using namespace std;
// greater算法的头文件
int main()
{
	// 默认情况下,创建的是大堆,其底层按照小于号比较
	vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
	priority_queue<int> q1;
	for (auto& e : v)  q1.push(e);
	cout << q1.top() << endl;
	// 如果要创建小堆,将第三个模板参数换成greater比较方式
	priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
	cout << q2.top() << endl;
	return 0;
}
	

优先队列优先是大堆,这里第三个模板参数的改变也就意味比较函数的改变

四 三种容器的模拟实现

4.1 stack模拟实现

#pragma once
template<class T,class Container=deque<T>>
class Stack
{
public:
	Stack()
	{}
	void push(const T&x)
	{
		_con.push_back(x);
	}
	void pop()
	{
		_con.pop_back();
	}

	size_t size()
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
	const T& top()const
	{
		return _con.back();
	}
	T& top()
	{
		return _con.back();
	}

private:
	Container _con;
};

4.2  queue模拟实现

 

#pragma once
template<class T,class Container=deque<T>>
class Queue
{
public:
	void push(const T&x)
	{
		_con.push_back(x);
	}
	void pop()
	{
		_con.pop_front();
	}
	size_t size()
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
	T& front()
	{
		return _con.front();
	}
	const T& front()const 
	{
		return _con.front();
	}
	T& back()
	{
		return _con.back();
	}
	const T& back()const
	{
		return _con.back();
	}
private:
	Container _con;
};

4.3  优先队列的模拟实现

#pragma once
template<class T,class Container=vector<T>>
class Priority_queue
{
public:
	Priority_queue()//无参构造
	{}
	//迭代器构造
	template<class InputIterator>
	Priority_queue(InputIterator first, InputIterator last):_con(first,last)
	{
		for (int i = (_con.size() - 1) / 2; i >= 0; i--)
		{
			adjust_down(i);
		}
	}
	//向上调整
	void adjust_up(int child)
	{
		int father = (child-1)/2;
		while (child > 0)
		{
			if (_con[father] < _con[child])
			{
				swap(_con[child], _con[father]);
				child = father;
				father = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}
	//向下调整
	void adjust_down(int father)
	{
		int child = father * 2 + 1;
		while (child < _con.size())
		{
			if (child + 1 < _con.size() && _con[child] < _con[child + 1])
			{
				child++;
			}
			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);
		adjust_up(_con.size() - 1);
	}
	void pop()
	{
		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		adjust_down(0);
	}
	const T& top()
	{
		return _con[0];
	}
	bool empty()
	{
		return _con.empty();
	}
	size_t size()
	{
		return _con.size();
	}
private:
	Container _con;//容器对象
};

测试

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include <functional>
using namespace std;
#include"priority_queue.h"
int main()
{
	vector<int>v = { 3,4,5,1,8,7,8 };
	Priority_queue<int>p(v.begin(), v.end());
	int n = p.size();
	while (n--)
	{
		cout << p.top() << " ";
		p.pop();
	}
	cout << endl;
	return 0;
}

 

 

上面的模拟构造并没有使用第三个参数,也就是没有仿函数,优先队列其实是复用了vector容器,看似是堆,但内部结构是一个可变的数组,其中的每个操作步骤也就是在操作数组里面的元素

还有一个加入仿函数的例子

#pragma once
template<class T,class Container=vector<T>,class Compare=Less<T>>
class Priority_queue
{
public:
	Priority_queue()//无参构造
	{}
	//迭代器构造
	template<class InputIterator>
	Priority_queue(InputIterator first, InputIterator last):_con(first,last)
	{
		for (int i = (_con.size() - 1) / 2; i >= 0; i--)
		{
			adjust_down(i);
		}
	}
	//向上调整
	void adjust_up(int child)
	{
		int father = (child-1)/2;
		while (child > 0)
		{
			if (_com(_con[father] , _con[child]))
			{
				swap(_con[child], _con[father]);
				child = father;
				father = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}
	//向下调整
	void adjust_down(int father)
	{
		int child = father * 2 + 1;
		while (child < _con.size())
		{
			if (child + 1 < _con.size() && _com(_con[child] , _con[child + 1]))
			{
				child++;
			}
			if (_com(_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);
		adjust_up(_con.size() - 1);
	}
	void pop()
	{
		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		adjust_down(0);
	}
	const T& top()
	{
		return _con[0];
	}
	bool empty()
	{
		return _con.empty();
	}
	size_t size()
	{
		return _con.size();
	}
private:
	Container _con;//容器对象
	Compare _com;//仿函数对象
};

 注意模板参数的变化和比较大小代码的变化,仿函数是写在外面的,具体怎么比,按自己的需求来

测试:

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include <functional>
using namespace std;
#include"priority_queue.h"

template<class T>
class Less
{
public:
	bool operator()(const T& x,const T& y)
	{
		return x < y;
	}
};
template<class T>
class Greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x >  y;
	}
};
int main()
{
	vector<int>v = { 3,4,5,1,8,7,8 };
	Priority_queue<int,vector<int>,Greater<int>>  p(v.begin(), v.end());
	int n = p.size();
	while (n--)
	{
		cout << p.top() << " ";
		p.pop();
	}
	cout << endl;
	return 0;
}

 

 五  deque

deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。

 和vector和list比起来,它比vector头插的效率高,和list比,它支持随机访问,且空间利用率比list高,但是它都无法替代他们两个,反倒成了stack和queue的底层容器

对于deque来说,它是一个指针数组,这些指针指向一片片空间,它并不真正的连续,而是由这些空间拼接而成

 从上面我们可知道的是,如果我们在中间插入数据,那么就会面临两种选择

1.扩容,这样减少了挪动数据,但是使得每个数组的空间大小不一样,这里数组空间的大小不一样就会导致我们在查找数据的时候需要一个个访问,这样就导致效率变得很低

2.挪动数据,也就是保持数组长度的不变,但是这样挪动的数据就太多了,也会导致效率变低,但是好处就是我们在访问元素的时候,效率会很高,假设每个数组都是10,我们要访问第i个元素,那么我先用i-=第一层的元素个数,然后x=i/10,这里的x就是第几层(层数从0开始),然后y=i%10这里的y是第几个,这样就可以快速的定位了

因为deque有这些缺点,所以也不能替代vector和list

总结

以上就是全部内容了,希望喜欢,多多支持

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

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

相关文章

摆脱Jenkins - 使用google cloudbuild 部署 java service 到 compute engine VM

在之前 介绍 cloud build 的文章中 初探 Google 云原生的CICD - CloudBuild 已经介绍过&#xff0c; 用cloud build 去部署1个 spring boot service 到 cloud run 是很简单的&#xff0c; 因为部署cloud run 无非就是用gcloud 去部署1个 GAR 上的docker image 到cloud run 容…

张大哥笔记:经济下行,这5大行业反而越来越好

现在人们由于生活压力大&#xff0c;于是就干脆降低自己的欲望&#xff0c;只要不是必需品就不买了&#xff0c;自然而然消费也就降低了&#xff0c;消费降级未必是不好的现象&#xff01; 人的生物本能是趋利避害&#xff0c;追求更好的生存和发展空间&#xff0c;回避对自己有…

C++使用thread_local实现每个线程下的单例

对于一个类&#xff0c;想要在每个线程种有且只有一个实例对象&#xff0c;且线程之间不共享该实例&#xff0c;可以按照单例模式的写法&#xff0c;同时使用C11提供的thread_local关键字实现。 在单例模式的基础上&#xff0c;使用thread_local关键字修饰单例的instance&…

Redis原理篇——哨兵机制

Redis原理篇——哨兵机制 1.Redis哨兵2.哨兵工作原理2.1.哨兵作用2.2.状态监控2.3.选举leader2.4.failover 1.Redis哨兵 主从结构中master节点的作用非常重要&#xff0c;一旦故障就会导致集群不可用。那么有什么办法能保证主从集群的高可用性呢&#xff1f; 2.哨兵工作原理 …

【Python】读取文件夹中所有excel文件拼接成一个excel表格 的方法

我们平常会遇到下载了一些Excel文件放在一个文件夹下&#xff0c;而这些Excel文件的格式都一样&#xff0c;这时候需要批量这些文件合并成一个excel 文件里。 在Python中&#xff0c;我们可以使用pandas库来读取文件夹中的所有Excel文件&#xff0c;并将它们拼接成一个Excel表…

AI助教时代:通义千问,让学习效率翻倍?

全文预计1100字左右&#xff0c;预计阅读需要5分钟。 关注AI的朋友知道&#xff0c;在今年5月份以及6月份的开端&#xff0c;AI行业可谓是风生水起&#xff0c;给了我们太多的惊喜和震撼&#xff01;国内外各家公司纷纷拿出自己憋了一年的产品一决雌雄。 国内有文心一言、通义千…

大模型相关:ChatGPT的原理与架构

一、大模型面临的挑战 1.1 Transformer模型的缺陷&#xff1a; 与RNN相比Transformer面临以下挑战&#xff1a; 并行计算能力不足。RNN需要按序处理序列数据中的每个时间步&#xff0c;这限制了它在训练过程中充分利用现代GPU的并行计算能力&#xff0c;从而影响训练效率。长…

FastAPI给docs/配置自有域名的静态资源swagger-ui

如果只是要解决docs页面空白的问题&#xff0c;可先看我的这篇博客&#xff1a;FastAPI访问/docs接口文档显示空白、js/css无法加载_fastapi docs打不开-CSDN博客 以下内容适用于需要以自用域名访问swagger-ui的情况&#xff1a; 1. 准备好swagger-ui的链接&#xff0c;如&am…

STM32H750启动和内存优化(分散加载修改)

前些日子有个朋友一直给我推荐STM32H750这款芯片&#xff0c;说它的性价比&#xff0c;说它多么多么好。于是乎&#xff0c;这两天试了试&#xff0c;嚯&#xff0c;真香&#xff01;我们先看看基本配置 这里简单总结下&#xff0c;cortex-m7内核&#xff0c;128k片内flash …

htb-linux-6-beep

nmap web渗透 目录扫描 漏洞关键词 shell py脚本执行 flag root 目前的权限 nmap root

Django 视图类

在Django框架中&#xff0c;视图类&#xff08;Class-based views&#xff0c;简称CBVs&#xff09;提供了一个面向对象的方式来定义视图。这种方式可以让你通过创建类来组织视图逻辑&#xff0c;而不是使用基于函数的视图&#xff08;Function-based views&#xff0c;简称FBV…

109、python-第四阶段-6-多线程编程

单线程&#xff1a; import threading import timedef sing():while True:print("我在唱歌")time.sleep(1) def dance():while True:print("我在跳舞")time.sleep(1) if __name__"__main__":sing()dance()多线程&#xff1a; import threading…

嵌入式学习——Linux高级编程复习(进程)——day39

1. 进程 进程是计算机科学中的一个核心概念&#xff0c;它是操作系统进行资源分配和调度的基本单位&#xff0c;代表了一个正在执行中的程序实例。当一个程序被加载到内存并开始执行时&#xff0c;它就变成了一个进程。 1. 程序&#xff1a;存放在外存中的一段代码的集合 2. 进…

Java并发编程:线程生命周期

Java并发编程专栏 文章收录于Java并发编程专栏 线程生命周期 线程是Java并发编程的核心概念&#xff0c;理解线程生命周期对于编写高效的并发程序至关重要。本文将详细介绍 Java 线程的六种状态以及状态之间的转换关系&#xff0c;帮助读者更好地理解线程的行为。   在Java中…

mysql8.0中的mysql.ibd

mysql8.0版本中多了一个mysql.ibd的文件。5.7版本则没有这个文件。 MySQL5.7: .frm文件 存放表结构信息 .opt文件&#xff0c;记录了每个库的一些基本 信息&#xff0c;包括库的字符集等信息 .TRN&#xff0c;.TRG文件用于存放触发器的信 息内容。 在MySQL 8.0之前&#xff0…

2002NOIP普及组真题 4. 过河卒

线上OJ 地址&#xff1a; 【02NOIP普及组】过河卒 核心思想&#xff1a; 对于此类棋盘问题&#xff0c;一般可以考虑 dp动态规划、dfs深搜 和 bfs广搜。 解法一&#xff1a;dp动态规划 方法&#xff1a;从起点开始逐步计算到达每个位置的路径数。对于每个位置&#xff0c;它…

数 据 类 型

概述 Java 是强类型语言。 每一种数据都定义了明确的数据类型&#xff0c;在内存中分配了不同大小的内存空间&#xff08;字节&#xff09;。 Java 中一共有 8 种基本类型&#xff08;primitive type&#xff09;&#xff0c;包括 4 种整型、2 种浮点型、1 种字符类型&#…

HikariCP连接池初识

HikariCP的简单介绍 hikari-光&#xff0c;hikariCP取义&#xff1a;像光一样轻和快的Connetion Pool。这个几乎只用java写的中间件连接池&#xff0c;极其轻量并注重性能&#xff0c;HikariCP目前已是SpringBoot默认的连接池&#xff0c;伴随着SpringBoot和微服务的普及&…

【ai】pycharm远程ssh开发

方式1: gateway的方式是远程放一个pycharm 专业版,经常下载失败 方式2: 类似vs,源码本地,同步到远程进行运行。 参考大神的分享: Pycharm远程连接服务器(2023-11-9) Pycharm远程连接服务器(windows下远程修改服务器代码)[通俗易懂] cpolar 建议同时内网穿透 选 远程开…

详解 Flink 的状态管理

一、Flink 状态介绍 1. 流处理的无状态和有状态 无状态的流处理&#xff1a;根据每一次当前输入的数据直接转换输出结果的过程&#xff0c;在处理中只需要观察每个输入的独立事件。例如&#xff0c; 将一个字符串类型的数据拆分开作为元组输出或将每个输入的数值加 1 后输出。…