【C++】stack，queue和priority_queue（优先级队列）

发布于：2025-05-27 ⋅ 阅读:(20) ⋅ 点赞:(0)

文章目录

前言

哈喽，各位小可爱们。咋们今天来学学栈（stack），队列（queue）和优先级队列（priority_queue）的相关知识。由于栈和队列小编之前讲过了嘛，所以这里大概的过一遍就ok了，但是模拟实现呢我们就不用之前学的那种形式了。我们换另一种方式来实现。当然这章主要是讲优先级队列的模拟实现。那就跟着小编一起俩看看都有哪些知识吧！
在这里插入图片描述

一、栈（stack）和队列（queue）的相关接口

1.栈的相关接口

stack的文档介绍

函数说明 接口说明
stack() 构造空的栈
empty() 检测stack是否为空
size() 返回stack中元素的个数
top() 返回栈顶元素的引用
push() 将元素val压入stack中
pop() 将stack中尾部的元素弹出

2.队列的相关接口

queue的文档介绍

函数说明 接口说明
queue() 构造空的队列
empty() 检测队列是否为空，是返回true，否则返回false
size() 返回队列中有效元素的个数
front() 返回队头元素的引用
back() 返回队尾元素的引用
push() 在队尾将元素val入队列
pop() 将队头元素出队列

二、栈（stack）和队列（queue）的模拟实现

上面我们说过，栈和对队列呢我们不用之前的类模板来实现了，这里我们用之前学的vector以及list来封装的方法来实现他们。

1.stack的模拟实现

从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。我们只需要对vector的部分接口进行封装即可。

namespace Stack//栈的模板
{
	//container适配转换出stack，
	template<class T, class container= vector<T>>//container是容器，这里我们默认给的vector的,当然用list也是可以的。不过STL标准库给的是deque
	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;
	};
}
int main ()
{
Stack::Stack <int,vector<int>>v; 
v.push(1); 
v.push(2);
v.push(3);
v.push(4);
while (!v.empty())
{
	cout << v.top() << " ";
	v.pop();
}
return 0;
}

2.queue的模拟实现

因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list来模拟实现queue，具体如下：

namespace queu
{
	template<class T, class container=list<T>>  //这里默认是list，当然不可以用vector哦，因为vector里面不支持front这个函数，不过STL标准库给的是deque
	class queue
	{
	public:
		void push(const T& x)//从队尾入数据
		{
			_con.push_back(x);
		}
		void pop()//删除队头数据
		{
			_con.pop_front();  
		}
		const T&front()const //返回队头数据
		{
			return  _con.front();
		}
		size_t size()const//返回队列数据的长度 
		{
			return _con.size(); 
		}
		bool empty()const//盘带是否为空队列
		{
			return _con.empty(); 
		}
	private:
		container _con; 
	};
}
int main ()
{
queu::queue <int> v; 
	v.push(1);
	v.push(2);
	v.push(3);
	v.push(4);
	while (!v.empty()) 
	{
		cout << v.front() << " "; 
		v.pop(); 
	}
 return 0;	
}

//stack和vector是is-a关系
#include<iostream>
#include<stdbool.h> 
#include<vector>
using namespace std;
class stack:public std::vector<int>  
{
public:
	void push(const int& x)
	{
		vector<int> ::push_back(x);
	}
	void pop()
	{
		vector<int> ::pop_back();
	}
	const int& top()const
	{
		return vector<int> ::back();
	}
	bool empty()
	{
		return vector<int> ::empty(); 
	}
};
int main()
{
	stack s; 
	s.push(1); 
	s.push(2);
	s.push(3); 
	while (!s.empty()) 
	{
		cout << s.top() << " "; 
		s.pop();
	}
	return 0;
}

三、priority_queue的相关接口介绍

priority_queue的文档介绍

函数声明 接口说明
priority_queue()/priority_queue(first,last) 构建一个空优先级队列和区间构建优先级队列
empty( ) 检测优先级队列是否为空，是返回true，否则返回false
top( ) 返回优先级队列中最大(最小元素)，即堆顶元素
push(x) 在优先级队列中插入元素x
pop() 删除优先级队列中最大(最小)元素，即堆顶元素

注意：
优先级队列（priority_queue）默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆（默认情况下，priority_queue是大堆），所有需要用到堆的位置，都可以考虑使用priority_queue。

四、priority_queue的模拟实现

因为priority_queue的底层就是堆，所以这里我只需要对相关接口进行封装即可

namespace priority 
{
	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; 
		}
	};
	template<class T,class container=vector<T>,class compare=less<T>>  
	class priority_queue
	{
	public:
		compare com; //实例化pare，因为他是一个类 
		void Adjustup(size_t chiled)//向上调整建堆
		{
			size_t parent = (chiled - 1) / 2; 
			while (chiled > 0) 
			{
				if (com(_con[parent], _con[chiled]))  
				{
					swap(_con[parent], _con[chiled]);  
					chiled = parent; 
					parent = (chiled - 1) / 2;
				}
				else break;
			}
		}
		size_t size()const//堆的大小
		{
			return _con.size(); 
		} 
		void push(const T& x)//插入元素
		{
			_con.push_back(x);        
			Adjustup(_con.size()-1);  
		}
		const T& top()//返回堆顶元素
		{
			return _con[0]; 
		}
		void AdjustDown(size_t parent)//向下调整建堆
		{
			size_t chiled = 2 * parent + 1;
			while (chiled < _con.size())
			{
				//假设法
				if (chiled + 1 < _con.size() && com(_con[chiled] ,_con[chiled + 1])) 
					++chiled;
				if (com(_con[parent], _con[chiled])) 
				{
					swap(_con[parent], _con[chiled]); 
					parent = chiled;  
					chiled = 2 * parent + 1; 
				}
				else
					break;
			}
		}
		void pop()//删除堆顶元素
		{
			swap(_con[0], _con[_con.size() - 1]);     
			_con.pop_back();   
			AdjustDown(0);  
		}
		bool empty()const//判断是否为空
		{
			return _con.empty();
		}
	private:
		container _con;  
	};
}
#include<iostream> 
#include<vector>
using namespace std;
int main()
{
	//priority::priority_queue <int, vector<int>> x;//默认是less，大堆
	priority::priority_queue <int, vector<int>, greater<int>> x; //小堆     
	int arr[10] = { 0 };
	for (int i = 1; i <= 5; i++)
	{
		x.push(i);
	}
	while (!x.empty())
	{
		cout << x.top() << " ";
		x.pop();
	}
	return 0;
 }

五、仿函数

priority_queue的模拟实现其实是很简单的。不过，为了满足我们可以随便控制堆的大小，我们引入了一个仿函数。那什么事仿函数呢？顾名思义，就是看来是函数，但其实他是一个类，只不是这个类重载了operator（）。

#include<iostream>
#include<vector> 
using namespace std;
template<class T> 
class Less
{
public:
	bool operator()(const T& x, const T&y)  //重载了operator（）
	{
		return x < y;//这里我们以比大小为例
	}
};
int main()
{
	Less<int> Lessfun;    
	cout << Lessfun(1, 2) << endl;//实例化less看起来是不是像是一个函数的调用？Lessfun是函数名，后面是参数   
	cout << Lessfun.operator()(1,2) << endl; //Lessfun(1,2)的本质  
}

仿函数的运用
我们以冒号排序为例，如果我们要控制是排升序还是降序，以我们正常的写法来看的话，如果要排升序或者降序的话，是不是要改变元素之间的比较关系，这里就要改变代码。是很不方便的。所以这里我们就可以借助仿函数来完成大小的自由切换。

#include<iostream>
#include<vector> 
using namespace std;
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;
	}
};
template<class compare> 
void Bubblesort(int* arr, int n, compare com) 
{
	for (int i = 0; i < n; i++)
	{
		int flag = 1;//单趟
		for (int j = 1; j < n-i; j++) 
		{
			if (com(arr[j] , arr[j-1]))//通过compare来控制数据之间的比较关系   
			{
				swap(arr[j-1], arr[j]);
				flag = 0;
			}
		}
		if (flag == 1)
			break;
	}
	for (int i = 0; i < 9; i++)
	{
		cout << arr[i];
	}
	cout << endl;
}
int main()
{
	Less<int> Lessfun;
	Greater<int > Greaterfun;  
	int arr[] = { 5,6,7,8,2,4,1,3,9 };
	//这里我们就可以通过传不同的参数来控制排升序还是降序，从而来达到不修改代码的目的
	//正常调用
    Bubblesort(arr, 9, Lessfun);//升序
    Bubblesort(arr, 9, Greaterfun);//降序 
    //匿名调用
    Bubblesort(arr, 9, Less<int>());//升序
    Bubblesort(arr, 9, Greater<int>());//降序
	return 0;

}

六、容器适配器

1.什么是适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口

在STL中stack和queue被划分为容器适配器，即使stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列。这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque
在这里插入图片描述
在这里插入图片描述

2.deque的简介绍

deque(双端队列)：是一种双开口的"连续"空间的数据结构，这里的连续并不是真的连续，而是由一段段连续的小空间连接而成。实际类似一个二维数组；双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。然而deque的底层呢有点复杂，后面小编会专门写一篇来讲述deque的底层。这里我们只需要记住deque在功能上合并了vector和list。

3.deque的优缺陷

  • 与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
  • 与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
  • 但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

4.为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

  • stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
  • 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

总结

好啦，今天的分享就到这里吧。我们下期再见吧！
在这里插入图片描述

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布