【C++】栈和队列(stack and queue)语法使用及实现原理

这篇具有很好参考价值的文章主要介绍了【C++】栈和队列(stack and queue)语法使用及实现原理。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++】栈和队列(stack and queue)语法使用及实现原理,C++,c++,开发语言  

  本篇文章会对C++中的容器stack和queue用法进行详解,也包含对优先队列(priority_queue)的讲解。同时会模拟实现stack、queue和priority_queue底层。希望本篇文章会对你有所帮助!

目录

一、stack 栈

1、1 什么是适配器

1、2 stack 语法讲解

1、3 stack 底层实现

1、4 deque 双端队列简单介绍

1、5 为什么选择deque作为stack和queue的底层默认容器

二、queue or priority_queue 队列和优先队列

2、1 queue 队列

2、1、1 queue 语法讲解

2、1、2  queue 底层实现

2、2 priority_queue 优先队列

2、2、1 priority_queue 底层实现原理

2、2、2 仿函数

2、2、3  priority_queue 底层代码实现


🙋‍♂️ 作者:@Ggggggtm 🙋‍♂️

👀 专栏:C++  👀

💥 标题:stack、queue和priority_queue讲解💥

 ❣️ 寄语:与其忙着诉苦,不如低头赶路,奋路前行,终将遇到一番好风景 ❣️  

【C++】栈和队列(stack and queue)语法使用及实现原理,C++,c++,开发语言

一、stack 栈

  stack(堆栈)是一种后进先出(Last-In-First-Out,LIFO)的数据结构。数据项只能从栈的顶部插入和删除。在C++中,stack、queue和priority_queue是一种容器适配器可以使用<stack>头文件来包含stack的定义。

1、1 什么是适配器

  我们在上述中说到stack是一种容器适配器。容器我们都知道,那什么是适配器呢?

  适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结),该种模式是将一个类的接口转换成客户希望的另外一个接口。通俗来说,在C++中适配器就是一种编程模式, 用于将一个类的接口适配成另一个类的接口,以满足不同的需求。
  我们所需要讲解stack、queue和priority_queue底层就是有用适配器来实现的。当然,只对语法有所需求的,不了解适配器也并无太大影响。
  只有概念太过抽象。我们不妨先来学一下语法使用,再了解底层实现原理后,就可很好的理解适配器是什么了。

1、2 stack 语法讲解

  我们早在学C语言时就学过栈。栈是一种先进后出的数据结构。在C++中,stack是一种容器。所以我们在使用时应引入相应头文件(#include<stack>),同时需要展开命名空间(namespace std)

  栈的操作很简单,一共就有如下几种:

  1. top:获取尾部元素操作;
  2. size:获取栈中的元素个数操作;
  3. pop:删除栈顶元素操作;
  4. push:栈顶插入元素操作;
  5. empty:判空操作;
  我们接下来看一下实例,结合理解一下,代码如下:
#include<iostream>
#include<stack>

using namespace std;

int main()
{
	//stack<data_type> stack_name;
	stack<int> st;  //声明一个stack对象,对象名为 st,存储数据类型为 int 

	//往栈中依次插入了1 2 3 三个元素
	st.push(1);
	st.push(2);
	st.push(3);
	cout << st.size() << endl; //打印栈中的元素个数

	cout << st.top() << endl;  //打印栈顶元素,栈顶元素为 3

	st.pop();
	cout << st.top() << endl;  //删除元素后,再次打印打印栈顶元素,栈顶元素为 2

	cout << st.empty() << endl; //判断栈是否为空,空返回 1 ,不为空返回 0。

	cout << st.size() << endl;
}

  我们再看输出结果如下:

【C++】栈和队列(stack and queue)语法使用及实现原理,C++,c++,开发语言

  栈的使用十分简单,我们直接看底层实现原理。 

1、3 stack 底层实现

  为了能够便利的存储各种类型,C++在底层实现中采用了类模板。通过声明或者传参,进而实例化出不同的类。

  stack的底层并不是自己定义了数组进行维护,而是引用了其他容器。引用的那个容器呢?我们先看一下底层模板定义:

【C++】栈和队列(stack and queue)语法使用及实现原理,C++,c++,开发语言

  模板的第一个参数即为我们所要存储的类型,第二个参数为我们所想使用的容器。我们也看到,其中有缺省参数。当你不传参时,默认为deque容器

  stack被称为容器适配器是因为它通过适配底层的容器实现了一种特定的接口和行为。而所谓的适配器,我们可以通俗理解就是可以根据实际需求选择适合的底层容器来实现Stack,并且可以在不影响代码的其他部分的情况下进行更改

  我们所选择的容器需要支持以下操作:

  • empty:判空操作;
  • pop_back:尾部删除元素操作;
  • push_back:尾部插入元素操作;
  • back:获取尾部元素操作;

  底层代码的实现原理就比较简单了,代码如下:

      template<class T, class Container=deque<T> >
      class stack
      {
      public:
          void push(const T& x)
          {
              _con.push_back(x);
          }
      
          void pop()
          {
              _con.pop_back();
          }
      
          T& top()
          {
              return _con.back();                                                                                                                            
          }    
              
          const T& top() const
          {    
              return _con.back();    
          }
      
          bool empty() const
          {
              return _con.empty();
          }
      
          int size() const
          {
              return _con.size();
          }
      private:
          Container _con;
      };

1、4 deque 双端队列简单介绍

  deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。
【C++】栈和队列(stack and queue)语法使用及实现原理,C++,c++,开发语言    deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组。
  双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,落 在了deque的迭代器身上,因此deque的迭代器设计就比较复杂其底层结构如下图所示:

【C++】栈和队列(stack and queue)语法使用及实现原理,C++,c++,开发语言

  当然,deque有其优势,也有其劣势。与vector比较,deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不 需要搬移大量的元素,因此其效率是必vector高的。与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。

  但是,deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构。

1、5 为什么选择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的优点,而完美的避开了其缺陷。

二、queue or priority_queue 队列和优先队列

2、1 queue 队列

2、1、1 queue 语法讲解

  queue队列是一种先进先出的数据结构。在C++中,也是一个容器适配器。其底层定义如下:

【C++】栈和队列(stack and queue)语法使用及实现原理,C++,c++,开发语言

  其主要的操作有如下几种:

  1. front:获取对列头部(第一个元素)操作;
  2. back:获取队列尾部(最后一个元素)操作;
  3. size:获取队列中的元素个数操作;
  4. pop:删除队列头部元素操作;
  5. push:队列尾部插入元素操作;
  6. empty:判空操作;
  我们来看实际例子,代码如下:
【C++】栈和队列(stack and queue)语法使用及实现原理,C++,c++,开发语言

2、1、2  queue 底层实现

  queue底层实现与stack大同小异。当我们学完stack的底层实现后,我们就很容易构思出queue的底层实现了。我们直接看代码:

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

   我们接下俩重点看一下优先队列priority_queue的底层实现。

2、2 priority_queue 优先队列

   优先队列(priority_queue)也是队列的一种,priority_queue的接口是和queue的接口是相同的。所以两者的使用语法也是相同的。我们直接看优先队列(priority——queue)的底层实现原理。

2、2、1 priority_queue 底层实现原理

  优先队列中顾名思义:优先级高的元素在队列中的位置靠前,优先级低的元素在队列中的位置靠后。优先级就是指的元素大小。

  优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:
  1. empty():检测容器是否为空;
  2. size():返回容器中有效元素个数;
  3. front():返回容器中第一个元素的引用;
  4. push_back():在容器尾部插入元素;
  5. pop_back():删除容器尾部元素
  标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。
  优先队列的底层是由堆来维护的。也就是我们所操作的元素都是在堆的基础上进行操作的。提到堆,我们就知道堆分为大根堆和小根堆。优先队列的底层默认是由大根堆来维护的。为了更好的去控制优先队列底层维护的是大根堆还是小根堆,这里就引入了仿函数。我们先来了解一下什么是仿函数,再来看一下底层的代码实现。

2、2、2 仿函数

  仿函数就是模仿函数,但它根本上就不是一个函数。我们先看下面一个例子,代码如下:

template<class T>
struct Less
{
	T l, r;
	bool operator()(const T& left, const T& right)
	{
		return left < right;
	}
};
int main()
{
	test_priority_queue();

	//仿函数
	Less<int> com;

    // com.operator() (1,2)
	cout << com(1, 2) << endl;
	cout << com(2, 1) << endl;
	return 0;
}

  我们看到上面的代码定义了一个结构体 Less,我们同时定义了一个com(Compare)对象。com(1,2)直接就对 1 和 2 进行了比较大小。是不是很像函数调用。但实际上是定义了一个结构体(或者类),该结构体(或者类)中重载了操作符 ()。从而达到了函数的效果。这就是所谓了仿函数。

2、2、3  priority_queue 底层代码实现

  我们通过把仿函数当作模板参数,就可以很好的控制底层是大根堆还是小根堆了。代码如下:

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)
		{
			while (first != last)
			{
				_con.push_back(*first);
				first++;
			}

			//建堆  向下调整算法O(n)
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				adjust_down(i);
			}
		}

		void adjust_up(size_t child)
		{
			Compare com;
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_con[parent] , _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}

		void adjust_down(size_t parent)
		{
			Compare com;
			size_t child = parent * 2 + 1;
			while (child<_con.size())
			{
				if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))
					child++;

				if (com(_con[parent] , _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}

		const T& top()const
		{
			return _con[0];
		}

		bool empty()  const
		{
			return _con.empty();
		}

		size_t size() const
		{
			return _con.size();
		}
	private:
		Container _con;
	};

   我们看到上述代码,删除元素就是删除的堆顶元素。每次删除都需要先与最后一个元素交换,再通过所引用的容器进行尾删,再向下调整算法进行维护队列。

  当然,上述代码只是实现了一部分主要接口。priority_queue(优先队列)的声明方式如下:

// 底层是大根堆
priority_queue<int> heap1;
// 底层是小根堆
priority_queue<int, vector<int>, greater<int>> heap2;

  到这里,希望你对优先队列有一个更好的认识。同时,对stack、queue和priority_queue的用法有一个很好的掌握。感谢阅读ovo~文章来源地址https://www.toymoban.com/news/detail-613838.html

到了这里,关于【C++】栈和队列(stack and queue)语法使用及实现原理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】栈和队列超详解!(Stack && Queue)

    栈 :一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则 压栈 : 栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。 出栈 : 栈的删除操

    2024年02月04日
    浏览(40)
  • C++:stack、queue、priority_queue增删查改模拟实现、deque底层原理

    我们先来看看 stack的相关接口有哪些: 从栈的接口,我们可以知道栈的接口是一种特殊的vector,所以我们完全可以使用vector来模拟实现stack。 因此我们可以将底层容器定义成模板,然后将容器类变量作为成员变量进行封装。在实现satck的各种接口时,通过成员变量来调用底层

    2024年02月03日
    浏览(42)
  • C++的stack和queue+优先队列

    适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结),该种模式是将一个类的接口转换成客户希望的另外一个接口。 stack和queue都是容器适配器,底层都是通过去适配双端队列deque去实现的,STL中没有把stack和queue划分在容

    2024年02月13日
    浏览(31)
  • 【C++初阶】12. Stack(栈)和Queue(队列)

    栈的介绍 队列的介绍 拓展:如何从中缀变为后缀 设计模式目前分为26种,这里就只介绍两种 适配器模式 迭代器模式 在日常生活中,我们常见的适配器通常为电源适配器(充电器) – 电源电压为220v,但是我们的设备并不需要这么高的电压(起保护作用) 需要将电源电压适配到我

    2024年02月12日
    浏览(33)
  • C++:stack和queue的使用以及底层实现

    适配器是一种设计模式 (代码设计经验),该种模式是把 一个类的接口转换成用户希望的另一个接口 。像本文介绍的容器底层其实是用其它容器实现的, 提供给用户的接口只是对其它容器接口的简单封装 。 2.1stack的介绍 stack是栈。 stack是一种容器适配器, 特点是后进先出 ,

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

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

    2024年02月13日
    浏览(42)
  • [C++] STL_priority_queue(优先级队列) 的使用及底层的模拟实现,容器适配器,deque的原理介绍

    priority_queue文档介绍 翻译: 1. 优先队列是一种 容器适配器 ,根据严格的弱排序标准, 它的第一个元素总是它所包含的元素中最大的。 2. 此上下文类似于 堆 , 在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。 3. 优先队列被实现为容器适配

    2024年02月04日
    浏览(40)
  • STL容器适配器 -- stack和queue(使用+实现)(C++)

    栈和队列数据结构+画图分析如果对栈和队列的结构不了解的,可以先看该链接的内容 使用stack时需要头文件 #includestack stack是一种容器适配器,用于具有 后进先出 (LIFO)的环境中。只能从容器的一端(栈顶),执行删除、插入和提取操作。 stack是作为容器适配器实现的,容器

    2024年02月14日
    浏览(60)
  • C++ deque/queue/stack的底层原理

    和 vector 容器采用连续的线性空间不同,deque 容器存储数据的空间是由一段一段等长的连续空间构成,各段空间之间并不一定是连续的,可以位于在内存的不同区域。 deque采用一块所谓的map数组(注意,不是STL的map容器)作为主控。 这里所谓map是一小块连续空间 (类似于ve

    2024年02月16日
    浏览(44)
  • 【C++历练之路】stack||queue||底层原理知多少

    W...Y的主页 😊 代码仓库分享💕  🍔前言: C++标准模板库(Standard Template Library,STL)是C++语言的一个重要组成部分,提供了一组通用的数据结构和算法,以便开发人员能够高效地编写可重用的代码。STL中的两个常用容器,即stack(堆栈)和queue(队列),在许多应用中都是非

    2024年02月04日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包