C++:stack和queue的使用以及底层实现

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

1.适配器模式

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


2.stack的介绍和使用

2.1stack的介绍

  1. stack是栈。

  2. stack是一种容器适配器,特点是后进先出,其删除只能从容器的一端进行元素的插入与提取操作

  3. stack是一个类模板(template <class T, class Container = deque<T> > class stack),stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:
    (1)empty:判空操作
    (2)back:获取尾部元素操作
    (3)push_back:尾部插入元素操作
    (4)pop_back:尾部删除元素操作

  4. 标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque(双端队列,后面再讲)。

  5. 使用要包含头文件<stack>。
    C++:stack和queue的使用以及底层实现,C++初阶,c++,开发语言,stl,学习方法,笔记

2.2stack的使用

常用接口说明:

函数 说明
stack() 构造函数,构造空栈
empty() 判断栈是否为空,空返回真,否则返回假
size() 返回栈中的元素个数
top() 取到栈顶数据的引用
push(val) 把元素val压入栈中
pop() 弹出栈顶元素

练习:
最小栈

//这个题目的要点是记录最小值,但出栈后可能最小值可能变化,只用一个变量记录不够
//我们可以设计两个栈:
//(1)s栈,正常出入数据
//(2)min栈,在s栈入栈时进行判断,如果自身为空或者新入栈的元素小于等于min栈顶就入栈
//在s栈出栈时也进行判断,如果出栈的元素等于min栈顶,min也要出栈

//不过这个题目还有优化的空间,那就是[1,1,1,1,1]这样多个相同数的情况
//为避免空间浪费,可以设计一个count计数记录每个数,多次出现的数入、出栈只需要减计数
//计数归0才真正的出栈
class MinStack {
public:
    MinStack() 
    {}
    
    void push(int val) 
    {
        if(min.empty() || min.top() >= val)
        {
            min.push(val);
        }
        s.push(val);
    }
    
    void pop() 
    {
        if(s.top() == min.top())
        {
            min.pop();
        }
        s.pop();
    }
    
    int top() 
    {
        return s.top();
    }
    
    int getMin() 
    {
        return min.top();
    }
private:
    stack<int> s;
    stack<int> min;
};

栈的弹出压入序列

//这个题目最好的办法就是模拟栈的压入弹出过程
//比如pushv[1,2,3,4,5]这个序列得到popv[4,5,3,2,1]
//先入栈s,1,1 != popV.top(),继续入栈
//入栈s,2, 2 != popV.top(),继续入栈
//入栈s,3,3 != popV.top(),继续入栈
//入栈s,4, 4 == popV.top(),同时出栈,popV是一个数组,下标加1视为出栈
//出栈结束栈s.top() = 3 != popV.top() = 5,继续入栈
//入栈, 5, 5 == popV.top(),同时出栈
//出栈结束s.top() = 3 == popV.top() = 3,同时出栈
//………………………………………………………………………………
//最后pushV的所有元素都入栈,并且s栈刚好出空,说明pushV可以得到popV
//如果pushV所有元素入栈,s栈没法出空,说明pushV无法得到popV
class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
    {
        size_t pushi = 0;
        //popi下标加1视为popV出栈
        size_t popi = 0;
        stack<int> s;

        while (pushi < pushV.size()) 
        {
            s.push(pushV[pushi++]);
            while(!s.empty() && s.top() == popV[popi])
            {
                s.pop();
                popi++;
            }
        }

        return s.empty();
    }
};

逆波兰表达式求值

//这个题目思路并不难,借助一个栈s即可
//(1)遇到数字:直接入s栈
//(2)遇到运算符,把栈中的两个左右数出栈,计算完把结果入s栈即可
//重复上面的步骤,一直到遍历完tokens即可,最后s栈顶即为结果
class Solution {
public:
    int evalRPN(vector<string>& tokens) 
    {
        stack<int> s;
        for(auto str : tokens)
        {
            if(!(str == "+" || str == "-" || str == "*" || str == "/"))
            {
               s.push(atoi(str.c_str()));
            }
            else
            {
                int right = s.top();  s.pop();
                int left = s.top();  s.pop();
                switch(str[0])
                {
                    case '+':
                        s.push(left + right);
                        break;
                    case '-':
                        s.push(left - right);
                        break;
                    case '*':
                        s.push(left * right);
                        break;
                    case '/':
                        s.push(left / right);
                        break;
                }
            }
        }
        return s.top();
    }
};

3.queue的介绍和使用

3.1queue的介绍

  1. queue是队列。

  2. queue是一种容器适配器,特点为先进先出,其中从容器一端插入元素,另一端提取元素。

  3. queue是一个类模板(template <class T, class Container = deque<T> > class queue;),底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
    (1)empty:检测队列是否为空
    (2)size:返回队列中有效元素的个数
    (3)front:返回队头元素的引用
    (4)back:返回队尾元素的引用
    (5)push_back:在队列尾部入队列
    (6)pop_front:在队列头部出队列

  4. 标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。

  5. 使用要包含头文件<queue>。

C++:stack和queue的使用以及底层实现,C++初阶,c++,开发语言,stl,学习方法,笔记

3.2queue的使用

常用接口说明:

函数 说明
queue() 构造函数,构造一个空队列
empty() 判断队列是否为空,空返回真,否则返回假
size() 返回队列的元素个数
front() 返回队头元素的引用
back() 返回队尾元素的引用
push(val) 队尾入元素val
pop() 队头元素出队

练习:
用队列实现栈

//这个题目的思路是有两个队列实现栈(其实也可以单队列实现,这里主要不是讲题目)
//需要始终有一个队列为空,比如[1,2,3]这个顺序队列
//队列q1为1 -> 2 - > 3,q2为空,top()只需要返回不为空的队列的队尾即可
//难点在出栈,出栈的话把1 -> 2转移到另一个队列q2,剩余一个元素即为栈顶,保存了再出栈即可
class MyStack {
public:
    MyStack() {}
    
    void push(int x) {
        if(q2.empty())
            q1.push(x);
        else
            q2.push(x);
    }
    
    int pop() {
        //默认q1为空栈
        queue<int>* empty_q = &q1;
        queue<int>* non_empty_q = &q2;
        if(q2.empty())
        {
            empty_q = &q2;
            non_empty_q = &q1;
        }
        while(non_empty_q->size() > 1)
        {
            empty_q->push(non_empty_q->front());
            non_empty_q->pop();
        }
        int ret = non_empty_q->front();
        non_empty_q->pop();
        return ret;
    }
    
    int top() {
        if(q1.empty())
            return q2.back();
        else
            return q1.back();
    }
    
    bool empty() {
        return q1.empty() && q2.empty();
    }
    queue<int> q1;
    queue<int> q2;
};

4.仿函数介绍

后面需要用到,就先简单介绍一下,以后会详细的讲各种用途。

//仿函数,又称函数对象,其实就是一个类,重载了operator()
// 使得类对象可以像函数一样使用
// 相比传函数指针,传仿函数要更加灵活一些
//开一个命名空间,和库里面的区分开
namespace my_compare
{
	template<class T>
	class less
	{
	public:
		bool operator()(const T& x, const T& y)const
		{
			return x < y;
		}
	};

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

5.priority_queue的介绍和使用

5.1priority_queue的介绍

  1. priority_queue(优先级队列)是堆。

  2. 优先级队列是一种容器适配器,如果根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。

  3. 在优先级队列中可以随时插入元素,并且只能检索最大(小)元素(优先队列中位于顶部的元素)

  4. 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该支持随机访问(下标加[]),并支持以下操作:
    (1)empty():检测容器是否为空
    (2)size():返回容器中有效元素个数
    (3)front():返回容器中第一个元素的引用
    (4)push_back():在容器尾部插入元素
    (5)pop_back():删除容器尾部元素

  5. 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。

  6. 需要支持随机访问,以便始终在内部保持堆结构。

  7. priority_queue是一个模板类,template <class T, class Container = vector<T>, class Compare = less< typename Container::value_type>> class priority_queue;

  8. 使用前要包含<queue>头文件

5.2priority_queue的使用

常用接口说明:

函数 说明
priority_queue() 构造一个空的优先级队列
priority_queue(begin(), end()) 传迭代器区间初始化
empty() 判断优先级队列是否为空,空返回真,否则返回假
top() 返回优先级队列中最大(小)元素,即堆顶元素
push(val) 在优先级队列中插入元素val
pop() 删除优选级队列中最大(小)元素,即堆顶元素

注意:

  1. 默认情况下priority_queue为大堆。
#include <vector>
#include <queue>
#include <functional> // greater算法的头文件
void TestPriorityQueue()
{
	 // 默认情况下,创建的是大堆,其底层按照小于号比较
	 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;
}
  1. 如果在priority_queue中放自定义类型的数据,用户需要在自定义类型中提供> 或者< 的重载。

练习:

数组中的第K个最大元素

//对于取数组中前K个最大的元素(TOPK),很容易就能想到利用堆
//先把原数组构造一个堆,要求第K大的元素
//只需要pop() K - 1次即可,最后堆顶一定是第k个大的元素
//其中建堆的时间复杂度为O(N),K - 1次的删除后调整为 (K-1) * logN
//在 K比较小的情况下,时间复杂度接近于O(N)
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        //其实这个题目也可以利用快速排序,不过必须选择性的排序区间
        priority_queue<int> p(nums.begin(), nums.end());
        for(int i = 0; i < k - 1; i++)
        {
            p.pop();
        }
        return p.top();
    }
};

6.deque的介绍

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

6.1deque的实现原理

deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组,其底层结构如下图所示:

C++:stack和queue的使用以及底层实现,C++初阶,c++,开发语言,stl,学习方法,笔记

6.2deque的缺陷

  1. 不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list。deque的应用并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构
    (实在要使用的话包含头文件< deque >)
  2. 头插尾插入效率高,中间插入还是要移动数据的(子数组长度恒定),并且频繁的下标加[]访问有很大的计算消耗,这个时候效率远远不如vector和list。

6.3选择deque作为stack和queue的底层默认容器的原因

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

7.模拟实现

7.1stack的模拟实现

namespace my_std
{
	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();
		}

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

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

	private:
		container _con;
	};
}

7.2queue的模拟实现

namespace my_std
{
	template<class T, class container = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_front();
		}

		T& front()
		{
			return _con.front();
		}

		T& back()
		{
			return _con.back();
		}

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

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

	private:
		container _con;
	};
}

7.3priority_queue的模拟实现

本文主要讲的不是堆相关的算法,如果大家对建堆和调整有疑问,可以看往期的堆讲解:
堆的实现
堆实际应用和时间复杂度分析文章来源地址https://www.toymoban.com/news/detail-704625.html

namespace my_std
{
	//优先级队列
	template<class T, class container = vector<T>, class comparation = less<T>>
	class priority_queue
	{
	public:
		//向上调整
		void adjust_up(size_t child)
		{
			comparation com; //用于比较的仿函数
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				// _con[parent]  < _con[child]
				//默认大堆,如果孩子大,就交换和父亲的值
				//然后更新孩子和父亲的下标
				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)
		{
			size_t child = parent * 2 + 1;
			comparation com;
			while (child < _con.size())
			{
				//_con[child] < _con[child + 1]
				//默认左孩子大,如果右孩子大就让孩子下标加1,注意右孩子不存在的情况
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					child++;
				}
				//_con[parent] < _con[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.front(), _con.back());
			_con.pop_back();
			adjust_down(0);
		}


		//无参构造,这个必须写,不然就没有默认构造用了
		priority_queue()
		{}

		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}

			// 建堆,自下而上建堆
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				adjust_down(i);
			}
		}

		
		/// ///
		
		T& top()
		{
			return _con.front();
		}

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

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

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

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

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

相关文章

  • C++初阶:容器适配器介绍、stack和queue常用接口详解及模拟实现

    介绍完了list类的相关内容后:C++初阶:适合新手的手撕list(模拟实现list) 接下来进入新的篇章,stack和queue的介绍以及模拟: stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。 stack是作为容器适配器

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

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

    2024年02月12日
    浏览(33)
  • 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)
  • 【C++初阶10-stack&queue】STL中的栈和队列(附优先级队列

    本期分享:STL中的栈和队列。 在数据结构初阶时,我们已经学习这来那个两种数据结构,如今来看STL中的,不过是更加标准化。而实现起来,会简单得超乎你想象! 文中不足错漏之处望请斧正! STL中的栈和队列是容器适配器。容器适配器是对某种已有容器的再次封装。 比如

    2024年02月06日
    浏览(43)
  • 【STL】stack与queue的底层原理及其实现

    (图片来自知乎) 1.stack是一种 容器适配器 ,模拟了栈的数据结构。数据只能从一端进去,另一端出来( 先进后出 )。 2.stack适配器 默认是由 deque 容器实现 的,也可以显示要求stack的底层封装的容器类型。由于栈的特性, array 和 forward_list 不能用来构造stack适配器 。 3.st

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

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

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

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

    2024年02月14日
    浏览(60)
  • 【C++】栈和队列(stack and queue)语法使用及实现原理

         本篇文章会对C++中的容器stack和queue用法进行详解,也包含对优先队列(priority_queue)的讲解。同时会模拟实现stack、queue和priority_queue底层。希望本篇文章会对你有所帮助! 目录 一、stack 栈 1、1 什么是适配器 1、2 stack 语法讲解 1、3 stack 底层实现 1、4 deque 双端队列简单

    2024年02月15日
    浏览(35)
  • 【C++】STL中stack,queue容器适配器的模拟实现(使用deque容器)

    🌏博客主页: 主页 🔖系列专栏: C++ ❤️感谢大家点赞👍收藏⭐评论✍️ 😍期待与大家一起进步! 虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和

    2024年02月15日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包