C++入门之stl六大组件--stack和queue源码深度剖析及模拟实现

这篇具有很好参考价值的文章主要介绍了C++入门之stl六大组件--stack和queue源码深度剖析及模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言

一、stack的介绍和使用

1.stack的介绍

2.stack的使用

3.stack的模拟实现

二、queue的介绍和使用

1.queue的介绍

2.queue的使用

3.queue的模拟实现

三、priority_queue的介绍和使用

1.priority_queue的介绍

2.priority_queue的使用

3.priority_queue的模拟实现

3.1解决一个topK问题

四、容器适配器

1.什么是容器适配器

2.stl中stack和queue的底层结构

3.deque的简单介绍(vector +list)

总结


前言

本文中的源码均在本地vs2019下测试无误,上传文件至gitee,地址为:https://gitee.com/a_young/stack_queue_-priority_queue


一、stack的介绍和使用

1.stack的介绍

通过阅读官方文档:

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

2.stack的使用

  • stack() 构造空的栈
  • bool empty() const { return c.empty(); }检查stack是否为空
  •  size_type size() const { return c.size(); } 返回stack中元素个数
  •  reference top() { return c.back(); } 返回栈顶元素
  •  const_reference top() const { return c.back(); } 返回栈顶元素
  •  void push(const value_type& x) { c.push_back(x); } 将元素val压栈
  •  void pop() { c.pop_back(); }  将stack尾部元素弹出

3.stack的模拟实现

源码中使用的deque来作为栈的适配器,所以我们使用deque来模拟stack

template<class T, class Contanier = 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:
		Contanier _con;
	};
	void test_stack()
	{
		//stack<int, vector<int>>st;  //数组栈
		// stack<int,list<int>> st; 链式栈
		stack<int, deque<int>>st;
		st.push(1);
		st.push(2);
		st.push(3);
		st.push(4);

		while (!st.empty())
		{
			cout << st.top() << " ";
			st.pop();

		}

		cout << endl;
	}
}

二、queue的介绍和使用

1.queue的介绍

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

2.queue的使用

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

3.queue的模拟实现

#pragma once
#pragma once
#include<iostream>
#include<vector>
#include<stack>
#include<list>

using namespace std;

namespace jellytest
{
	//适配器模式/配接器 
	//队列 先进先出
	template<class T, class Contanier = 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();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Contanier _con;
	};
	void test_queue()
	{
		//stack<int, vector<int>>st;  //数组栈
		// stack<int,list<int>> st; 链式栈
		queue<int, deque<int>> q;
		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);

		while (!q.empty())
		{
			cout << q.front() << " ";
			q.pop();
		}

		cout << endl;
	}
}

三、priority_queue的介绍和使用

1.priority_queue的介绍

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 来自动完成此操作。

2.priority_queue的使用

优先级队列默认使用 vector 作为其底层存储数据的容器,在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构,因此 priority_queue 就是堆,所有需要用到堆的位置,都可以考虑使用 priority_queue 。注意: 默认情况下 priority_queue 是大堆
priority_queue()/priority_queue(fifirst,last)   构造一个空的优先级队列
empty( ) 检测优先级队列是否为空,是返回true,否则返回 false
top( )  返回优先级队列中最大(最小元素),即堆顶元素
push(x)  在优先级队列中插入元素x
pop()  删除优先级队列中最大(最小)元素,即堆顶元素

3.priority_queue的模拟实现

通过上面的介绍,priority_queue的底层结构就是堆,因此此处只需对堆进行封装即可。stl中默认实现的是大堆。

这里先介绍一个新的概念--仿函数,使用仿函数定义的对象可以像函数一样使用,本质是调用运算符重载,如下定义:

struct less
{
    bool operator()(int x, int y)
    {
        return x<y;
    }
}

struct greater
{
    bool operator()(int x,int y)
    {
        return x>y;
    }
}


int main()
{
    Less lessfun; //声明一个对象
    cout<<lessfun(1,2)<<endl; // 1
}

stl中使用模板类,可以比较不止内置类型

3.1解决一个topK问题

topK问题实际上是找出文件中所有数的最大的前K个.

方法1:可以构造一个大堆,pop出前K个。

分析方法1:假设N很大,K很小,N个数都需要存到内存中,很浪费资源。

方法2:构造一个K个数的小堆,后面的数依次和堆顶元素进行比较,大于堆顶元素就进堆,替换堆顶元素,然后向下调整。最后前K大的数所有的就在堆中。

分析方法2:时间复杂度O(N*logK),空间复杂度O(K)

综上对两种方法比较,选择方法2来实现

template<class T>
struct less
{
    bool operator()(T & x, T& y)
    {
        //如果是自定义类型这里需要自己实现运算符重载
        return x<y;
    }
}

//创建一个小堆
template<class T,class Container = deque<T> ,class Compare = greter<T>>
class priority_queue
{
    
    public:
    //向下调整
    void adjust_down(int parent)
    {
        Compare com;
        int child = 2*parent +1;
        while(chile < _con.size())
        {
          //  if(child+1 <_con.size() && _con[child] < _con[child+1])
              if(child+1 <_con.size() && com(_con[child] , _con[child+1]))
                {
                    ++child;
                }
          //  if(_con[parent] < _con[child])
            if( com(_con[parent] , _con[child])
            {
                swap(_con[child] , _con[parent]);
                child = parent;
                parent = 2*child+1;
            }
        
            else
            {
                break;
             }
        }
            
    }
    //向上调整
    void adjust_up(int child)
    {
        	Comapre com;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (com(_con[parent], _con[child]))
				//if (Comapre()(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}

    }

    //堆的一些成员函数 封装一些接口
    void push()
    {
        _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];
    }
    
    size_t size()
    {
        return _con.size();
    }
    bool empty()
    {
        return _con.empty();
    }

private:
    Container _con;
}


void test_priority_queue()
{
    priority_queue<int,deque<int>,less<int>> pq;
    pq.push(0);
    pq.push(1);
    pq.push(2);
    pq.push(3);

    while(!pq.empty())
    {
        cout<<pq.top()<<" ";
        pq.pop();
    }

四、容器适配器

1.什么是容器适配器

2.stl中stack和queue的底层结构

3.deque的简单介绍(vector +list)

deque(双端队列):是一种双开口的“连续”空间的数据结构,双开口的含义是:可以在头尾两端进行插入删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不用挪动元素,与list比较,空间利用率较高。缺点就是:中间插入删除麻烦

deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组。头插的时候,就在中控数组前面插入一个指针,尾插在中控尾巴插入一个

双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护“整体连续”以及随机访问的假象,落在deque的迭代器上,因此deque的迭代器设计就比较复杂。

为什么选择 deque 作为 stack queue 的底层默认容器
stack 是一种后进先出的特殊线性数据结构,因此只要具有 push_back() pop_back() 操作的线性结构,都可以作为 stack 的底层容器,比如 vector list 都可以; queue 是先进先出的特殊线性数据结构,只要具有 push_back pop_front 操作的线性结构,都可以作为 queue 的底层容器,比如 list 。但是 STL 中对 stack queue 默认选择 deque 作为其底层容器,
主要是因为:
1. stack queue 不需要遍历 ( 因此 stack queue 没有迭代器 ) ,只需要在固定的一端或者两端进行操作。
2. stack 中元素增长时, deque vector 的效率高 ( 扩容时不需要搬移大量数据 ) queue 中的元素增长 时, deque 不仅效率高,而且内存使用率高。
结合了 deque 的优点,而完美的避开了其缺陷。

总结

本文主要模拟实现了stack,queue,priority_queue的一些接口,简单介绍了什么是容器适配器。文章来源地址https://www.toymoban.com/news/detail-631367.html

到了这里,关于C++入门之stl六大组件--stack和queue源码深度剖析及模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++入门之stl六大组件--String库函数的介绍

    文章目录 一、为什么学习string类 1.C语言中的字符串 二、标准库中的string类 1.string类 2.string类的常用接口 1.string类对象的常见构造 2.string类对象的容量操作 3.string类对象的访问以及遍历操作 4.string类对象的修改操作 5.string类的非成员函数 总结   C语言中,字符串是以\\0结尾的

    2024年02月16日
    浏览(44)
  • C++ STL stack & queue

    目录 一.stack 介绍  二.stack 使用 三.stack 模拟实现 普通版本: 适配器版本: 四.queue的介绍 五. queue使用 六.queue模拟实现 七.deque介绍 1.容器适配器 2.deque的简单介绍 3.deque的缺陷 4.为什么选择deque作为stack和queue的底层默认容器 stack------reference 1. stack是一种容器适配器,专门用在

    2024年02月12日
    浏览(41)
  • C++ STL--->stack和queue

    stack文档 stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行 元素的插入与提取操作。 stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定 的成员函数来访问其元素,将特定类作为

    2024年01月16日
    浏览(45)
  • [ C++ ] STL---stack与queue

    目录 stack简介 stack的常用接口 queue简介 queue的常用接口 stack的模拟实现 queue的模拟实现 1. stack是具有后进先出操作的一种容器适配器 ,其只能从容器的一端进行元素的插入与删除操作 ; 2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并

    2024年03月28日
    浏览(42)
  • 【c++】STL之stack和queue详解

    作者简介:დ旧言~,目前大二,现在学习Java,c,c++,Python等 座右铭:松树千年终是朽,槿花一日自为荣。 目标:掌握stack和queue库,了解deque库 毒鸡汤:小时候,哭是我们解决问题的绝招,长大后,笑是我们面对现实的武器。 望小伙伴们点赞👍收藏✨加关注哟💕💕  今天

    2024年02月19日
    浏览(41)
  • 【C++】学习STL中的stack和queue

            今天这篇博客的内容主要关于STL中的stack、queue和priority_queue三种容器。         stack和queue的使用方式非常简单,我们只要根据之前学习数据结构的经验和文档介绍就可以轻松上手。于是我们直接开始对它们的模拟实现。         stack和queue我们在数据结构阶段就曾经

    2024年02月10日
    浏览(41)
  • 【C++】透过STL源码深度剖析及模拟实现vector

    鉴于读者的响应,打算将文章拆分一下,方便观看,基本接口可看 深入浅出STL之vector类 以下我所介绍的都是基于【SGI】版本的STL,对源码有兴趣的同学可以去看看 侯捷老师的《STL源码剖析》 然后呢我们就去调出【vector】的一些核心源码,这里我们主要关注的就是这个使用原

    2024年02月14日
    浏览(43)
  • C++基础(13)——STL(stack、queue、list)

    本文主要介绍C++中STL中的stack、queue和list容器 栈中只有顶端元素才可以被外界调用,因此栈不允许有遍历的行为,其中string、vector、deque都可以遍历 队列中队头出数据,队尾进数据,且和栈一样不允许有遍历操作 queue容器装入自定义数据类型数据 链表由一系列的结点组成,结

    2024年02月10日
    浏览(39)
  • 【C++】STL——stack和queue使用及模拟实现

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸C++  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸君一同

    2024年02月13日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包