当前位置： 首页 > article >正文

22. C++STL 8(stack与queue的使用与模拟，STL容器适配器，vector与deque的效率比较)

article 2025/1/24 11:34:06

⭐本篇重点：

1 STL中stack与queue的使用与模拟

2 使用适配器来实现stack和queue

3 deque与vector的效率比较

⭐本篇代码：c++学习 · 橘子真甜/c++-learning-of-yzc - 码云 - 开源中国 (gitee.com)

⭐标⭐是比较重要的部分

目录

一. 前言

二. STL中栈和队列的使用

2.1 stack的使用

2.2 queue的使用 

三. STL中stack与queue的模拟实现 

3.1 stack和queue是STL中的适配器

3.2 通过适配来模式实现stack

3.3 测试模拟适配实现的stack 

 3.4 通过适配来模拟实现queue及其测试

四. 对于STL使用deque来适配stack与queue的思考*

五. 下篇重点：priority_queue(优先级队列)的使用和模拟实现 

一. 前言

        栈和队列是编程中常用的数据结构。栈和队列都是线性结构，栈的特点是后进先出，队列的特点是先进先出。

        一般来说，我们的栈使用一个数组来实现，队列则用一个链表来实现。

        栈和队列的实现可以看我的这两篇文章。

3.数据结构-c/c++实现栈（详解，栈容量可以动态增长）_c++中什么数据结构能一直增加数据-CSDN博客

4.数据结构-c/c++实现队列（链表实现）-CSDN博客

二. STL中栈和队列的使用⭐

//使用STL中queue和stack所需的头文件
#include <queue>
#include <stack>

2.1 stack的使用

常用的接口说明
push在栈顶中插入数据
pop删除栈顶元素
empty判断栈是否为空
size获取栈中元素的数量
top获取栈顶元素

注意：栈没有迭代器！

测试代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <queue>
#include <stack>

using namespace std;

//用于测试的自定义类
class Date
{
public:
	Date(int year = 0, int month = 0, int day = 0)
		:_year(year)
		, _month(month)
		, _day(day)
	{};

	void print()
	{
		cout << _year << "/" << _month << "/" << _day << endl;
	}

private:
	int _year;
	int _month;
	int _day;
};

void TestStack()
{
	//1 测试基本类型
	stack<int> s1;
	for (int i = 0; i < 5; i++)	// 4 3 2 1 0
		s1.push(i);
	s1.pop(); // 3 2 1 0
	s1.pop(); // 2 1 0

	s1.push(5);	//5 2 1 0
	//栈没有迭代器！遍历栈只能获取栈顶元素，然后删除栈顶元素。
	while (!s1.empty())
	{
		cout << s1.top() << " ";
		s1.pop();
	}
    cout << endl;

	//2 测试自定义类型
	stack<Date> s2;
	Date d1(2024, 12, 8);
	Date d2(2025, 6, 7);
	Date d3(1, 1, 1);
	Date d4(9999, 12, 31);
	Date d5(1, 2, 3);

	s2.push(d1);
	s2.push(d2);
	s2.push(d3);	//d3 d2 d1
	s2.pop();		//d2 d1
	s2.push(d4);
	s2.push(d5);	//d5 d4 d2 d1

	while (!s2.empty())
	{
		Date tmp = s2.top();
		tmp.print();
		s2.pop();
	}
}

int main()
{
	TestStack();
	return 0;
}

测试结果如下：

2.2 queue的使用 

常用的接口说明
push在队尾中插入数据
pop删除队首元素
empty判断队列是否为空
size获取队列中元素的数量
front获取队首元素

与栈一样，队列没有迭代器！

 测试代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <queue>
#include <stack>

using namespace std;

//用于测试的自定义类
class Date
{
public:
	Date(int year = 0, int month = 0, int day = 0)
		:_year(year)
		, _month(month)
		, _day(day)
	{};

	void print()
	{
		cout << _year << "/" << _month << "/" << _day << endl;
	}

private:
	int _year;
	int _month;
	int _day;
};

void TestQueue()
{
	//1 测试基本类型
	queue<int> s1;
	for (int i = 0; i < 5; i++)	// 0 1 2 3 4
		s1.push(i);
	s1.pop(); // 1 2 3 4
	s1.pop(); // 2 3 4

	s1.push(5);	//2 3 4 5
	//和栈一样，队列没有迭代器。只能删除元素然后继续访问
	while (!s1.empty())
	{
		cout << s1.front() << " ";
		s1.pop();
	}
	cout << endl;

	//2 测试自定义类型
	queue<Date> s2;
	Date d1(2024, 12, 8);
	Date d2(2025, 6, 7);
	Date d3(1, 1, 1);
	Date d4(9999, 12, 31);
	Date d5(1, 2, 3);

	s2.push(d1);
	s2.push(d2);
	s2.push(d3);	
	s2.pop();		
	s2.push(d4);
	s2.push(d5);	//d2 d3 d4 d5

	while (!s2.empty())
	{
		Date tmp = s2.front();
		tmp.print();
		s2.pop();
	}
}

int main()
{
	TestQueue();
	return 0;
}

测试结果如下：

三. STL中stack与queue的模拟实现 

3.1 stack和queue是STL中的容器适配器⭐

        我们知道STL有六大组件：容器，算法，迭代器，适配器，仿函数，空间配置器

        stack和queue是适配器中的一种。stack和queue是通过封装（或者说适配）vector，list，deque来转化实现的。

        我们看一下文档对stack和queue的解释 。

3.2 通过适配来模式实现stack

        需要实现pop, push, empty, top, size等函数。stack代码框架如下

    //T是数据类型，Container是适配的容器
	template<class T,class Container>
	class MyStack
	{
	public:
		void push(const T& x)
		{}

		T pop()
		{}

		T top()
		{}

		size_t size()
		{}

		bool empty()
		{}
	private:
		Container _con;
	};

然后我们根据栈的特点封装好函数即可

        栈后进先出。每次都尾插尾删即可

适配后的代码如下：

	//T是数据类型，Container是适配的容器
	template<class T,class Container>
	class MyStack
	{
	public:
		void push(const T& x)
		{
			//每次插入数据尾插，删除数据尾删除即可适配stack(即后进先出)
			_con.push_back(x);
		}

		T pop()
		{
			//每次插入数据尾插，删除数据尾删除即可适配stack
			_con.pop_back();
		}

		T top()
		{
			//返回最后一个元素
			return _con.back();
		}

		size_t size()
		{
			retunr _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

3.3 测试模拟适配实现的stack 

        我们分别使用vector和list来适配stack

测试代码如下：

头文件test.h

#pragma once
#include <iostream>
#include <vector>
#include <list>
using namespace std;


namespace YZC
{
	//T是数据类型，Container是适配的容器
	template<class T,class Container>
	class MyStack
	{
	public:
		void push(const T& x)
		{
			//每次插入数据尾插，删除数据尾删除即可适配stack(即后进先出)
			_con.push_back(x);
		}

		void pop()
		{
			//每次插入数据尾插，删除数据尾删除即可适配stack
			return _con.pop_back();
		}

		T top()
		{
			//返回最后一个元素
			return _con.back();
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

    void test1()
	{
		//1 使用vector适配
		MyStack<int, vector<int>> st1;
		for (int i = 0; i < 10; i++)
			st1.push(i);
		while (!st1.empty())
		{
			cout << st1.top() << " ";
			st1.pop();
		}
		cout << endl;

		//2 使用list适配
		MyStack<char, list<char>> st2;
		for (int i = 0; i < 10; i++)
			st2.push('a' + i);
		while (!st2.empty())
		{
			cout << st2.top() << " ";
			st2.pop();
		}
	}
}

源文件test.cpp

#include"test.h"

int main()
{
	YZC::test1();
	return 0;
}

测试结果如下：

 3.4 通过适配来模拟实现queue及其测试

        我们知道queue是先进先出。所以要尾插头删。但是vector没有pop_front这个接口，所以我们使用list和deque来适配队列

        vector没有头插头删的原因是，需要挪动大量数据，效率低！

测试代码如下：

test.h

#pragma once
#include <iostream>
#include <vector>
#include <list>
#include <deque>
using namespace std;


namespace YZC
{
	//T是数据类型，Container是适配的容器
	template<class T,class Container>
	class MyQueue
	{
	public:
		void push(const T& x)
		{
			//每次插入数据尾插，删除数据头删除即可适配stack(即先进先出)
			_con.push_back(x);
		}

		void pop()
		{
			//每次插入数据尾插，删除数据头删除即可适配stack
			return _con.pop_front();
		}

		T front()
		{
			//返回第一个元素
			return _con.front();
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

	void test1()
	{
		//1 使用vector适配?	无法使用，因为vector没有头插数据
		//MyStack<int, vector<int>> st1;

		//2 使用list适配
		MyQueue<int, list<int>> q1;
		for (int i = 0; i < 10; i++)
			q1.push(i);
		while (!q1.empty())
		{
			cout << q1.front() << " ";
			q1.pop();
		}
		cout << endl;

		//3 使用deque适配
		MyQueue<char, deque<char>> q2;
		for (int i = 0; i < 10; i++)
			q2.push('a' + i);
		while (!q2.empty())
		{
			cout << q2.front() << " ";
			q2.pop();
		}
	}
}

test.cpp

#include"test.h"

int main()
{
	YZC::test1();
	return 0;
}

测试结果如下：

四. 对于STL使用deque来适配stack与queue的思考⭐

        deque（双端队列）是STL提供的一个双端队列，它结合了vector和list的特点。既能在任意位置删除插入，也能够随机访问。

        这么来看，deque是不是就能够替代vector和list了？实则不然，因为deque的底层的中控器和迭代器导致其随机访问效率并没有vector高。

         上面都是理论，不如我们来测试一下。插入10000000个数据来比较一下vector和deque的效率。

测试代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include"test.h"
const int MAX_SIZE = 10000000;

int main()
{
	srand((unsigned int)(time(0)));
	vector<long long> arr1;
	deque<long long> arr2;


	time_t begin1 = clock();
	
	for (int i = 0; i < MAX_SIZE; i++)
		arr1.push_back(static_cast<long long>(rand()) * rand());
	
	clock_t end1 = clock();
	double time1 = static_cast<double>(end1 - begin1) / CLOCKS_PER_SEC;


	time_t begin2 = clock();

	for (int i = 0; i < MAX_SIZE; i++)
		arr2.push_back(static_cast<long long>(rand()) * rand());
	
	clock_t end2 = clock();
	double time2 = static_cast<double>(end2 - begin2) / CLOCKS_PER_SEC;
	

	cout << "vector time:" << time1 << endl;
	cout << "deque time:" << time2 << endl;
	return 0;
}

测试结果如下：

可以看到 vector的效率还是比deque高很多的！ 

        但是stack和queue都是在头部和尾部插入删除数据，并没有使用到deque的随机访问。所以使用deque作为适配器的效率并不会很低。

五. 下篇重点：priority_queue(优先级队列)的使用和模拟实现 


http://www.kler.cn/a/428423.html

相关文章：

  • vim在命令模式下的查找功能
  • Kafka后台启动命令
  • 【Linux】19.基础IO（1）
  • 【Knife4j与Swagger的区别是什么？】
  • 如何实现网页不用刷新也能更新
  • 论文笔记（六十二）Diffusion Reward Learning Rewards via Conditional Video Diffusion
  • springSecurity自定义登陆接口和JWT认证过滤器
  • go语言的sdk项目搭建与git 操作标签tag并推送至远程仓库
  • CDH 5.7集群部署完整指南
  • RPO: Read-only Prompt Optimization for Vision-Language Few-shot Learning
  • 情感分析研究综述：方法演化与前沿挑战
  • Cookies,Session Storage,Local Storage区别
  • SQL DML数据操作语言与DQL数据查询语言
  • 无公网IP实现飞牛云手机APP远程连接飞牛云NAS管理传输文件
  • 【数字电路与逻辑设计】实验三 8 位寄存器 74374
  • react 路由鉴权
  • TriCore架构-TC397将code从原来在P-Cache地址移到PSPR的地址，CPU的负载率为什么没影响
  • 使用C#开发VTK笔记(四)-创建文字及坐标轴导入点云
  • 每日一题 LCR 114. 火星词典
  • C#里怎么样使用where方法2？
  • 常见的 CSS 对齐方式介绍及代码示例
  • ros项目dual_arm_pick-place（编辑已有的moveit配置助手包）
  • 云数据库 HBase
  • Linux：软硬链接
  • 认识自定义协议
  • 英语写作中“错误”mistake error的用法