C++ 超详细讲解stack与queue的使用

目录
  • stack
    • 介绍和使用
    • 模拟实现
    • stack的使用例题
      • 最小栈
      • 栈的弹出压入序列
      • 逆波兰表达式求值
  • queue
    • 模拟实现
  • 容器适配器
    • deque简介
  • priority_queue优先级队列
    • priority_queue的使用
    • priority_queue的模拟实现
    • 通过仿函数控制比较方式

stack

介绍和使用

stack文档介绍

stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。

stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出。

stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:

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

标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque。

模拟实现

从栈的接口可以看出,栈实际是一种特殊的vector,直接使用vector即可模拟实现stack

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

namespace s {
	//stack是一个Container适配(封装转换)出来的
	template<class T,class Container = std::deque<T>>
	class stack {
	public:
		stack() {

		}

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

		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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

	private:
		Container _con;
	};

	void test_stack1()
	{
		s::stack<int,vector<int>> st;
		//s::stack<int, list<int>> st;
		//s::stack<int> st;
		st.push(1);
		st.push(2);
		st.push(3);
		st.push(4);

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

stack的使用例题

最小栈

题目描述:设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。push(x) —— 将元素 x 推入栈中。pop() —— 删除栈顶的元素。top() —— 获取栈顶元素。getMin() —— 检索栈中的最小元素。

解题思路:定义两个成员变量(栈),当插入数据时,_st正常插入,如果要插入的数据比_st的栈顶元素小时,就把该数据也插入_minst。出数据时,取出_st栈顶元素,如果该数据和_minst栈顶数据相等,就把_minst的栈顶元素也取出,这样_minst的栈顶元素就始终是栈中存在元素的最小值。

class MinStack {
public:
    MinStack() {

    }

    void push(int val) {
        _st.push(val);
        if(_minst.empty() || val<=_minst.top())
        {
            _minst.push(val);
        }
    }

    void pop() {
        if(_st.top()==_minst.top())
        {
            _minst.pop();
        }
        _st.pop();
    }

    int top() {
        return _st.top();
    }

    int getMin() {
        return _minst.top();
    }

    stack<int> _st;
    stack<int> _minst;
};

栈的弹出压入序列

题目描述:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。

解题思路:定义一个栈,把pushV中的数据依次放入栈中。如果遇到放入的pushV中的数据和popV中数据相等,那么把st栈顶元素取出。最后st如果为空,则符合要求。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size()==0)
            return true;
        stack<int> st;
        int pushi=0,popi=0;
        while(pushi<pushV.size()){
            st.push(pushV[pushi]);
            //如果pushV[pushi]和popV[popi]匹配上了
            while(!st.empty() && st.top()==popV[popi]){
                st.pop();
                ++popi;
            }
            ++pushi;
        }
        if(st.empty())
            return true;
        return false;
    }
};

逆波兰表达式求值

题目描述:根据 逆波兰表示法,求表达式的值。有效的算符包括 +、-、*、/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。说明:整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

解题思路:遍历,如果是字符串中是数字,将字符数字转化为数字后放入栈中,如果遇到运算符,取出两个栈顶元素,先取出的栈顶元素作为运算符右边的数字,后取出的作为运算符左边的数字,按照字符串中的运算符做运算,得到的数字再放入栈中,再遍历数组放入数字,以此类推。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        int left=0,right=0;
        for(const auto& str:tokens)
        {
            if(str=="+" ||str=="-"||str=="*"||str=="/")
            {
                right=st.top();
                st.pop();
                left=st.top();
                st.pop();
                switch(str[0])
                {
                case '+':
                    st.push(left+right);
                    break;
                case '-':
                    st.push(left-right);
                    break;
                case '*':
                    st.push(left*right);
                    break;
                case '/':
                    st.push(left/right);
                    break;
                }
            }
            else
            {
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};

queue

queue的文档介绍

和栈一样,队列是一种容器适配器。该底层容器至少支持以下操作:

empty:检测队列是否为空

size:返回队列中有效元素的个数

front:返回队头元素的引用

back:返回队尾元素的引用

push_back:在队列尾部入队列

pop_front:在队列头部出队列

标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。vector类的头删效率太低,不能头删,所以不适配。

模拟实现

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

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

namespace q {

	template<class T,class Container=std::deque<T>>
	class queue {
	public:
		queue() {

		}

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

		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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

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

	void test_queue1()
	{
		//q::queue<int,list<int>> q1;
		//q::queue<int, vector<int>> q1;//vector头删效率低,不适配,报错

		q::queue<int> q1;
		q1.push(1);
		q1.push(2);
		q1.push(3);
		q1.push(4);

		while (!q1.empty())
		{
			cout << q1.front();
			q1.pop();
		}
		cout << endl;

	}
}

容器适配器

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

虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和queue默认使用deque

deque简介

deque(双端队列):是一种双开口的"连续"空间的数据结构,即可以在头尾两端进行插入删除操作,且时间复杂度为O(1)。

deque不是真正完全连续的空间,而是由一段段连续的小空间拼接而成,类似于一个动态的二维数组。

deque底层是一段假想的连续空间,实际上是分段连续的,它借助迭代器来维护其假想连续的结构,因此deque的迭代器设计也比较复杂。

vector的缺点是当空间不够时要扩容,会存在一定的空间浪费,头插或中间插入需要挪动数据,效率低。优点是可以随机访问,cpu高速缓存命中率很高。list的缺点是无法随机访问,cpu高速缓存命中率低(地址不连续)。优点是可按需申请释放空间,任意位置的插入删除数据时间复杂度为O(1),效率高。而deque折中了vector和list,从使用的角度,避开了它们的缺点,可以支持随机访问,头尾插入效率也较高,扩容时不需要挪动大量数据,效率较vector高。但deque不够极致,随机访问效率不如vector,任意位置插入删除不如list,且中间插入删除数据也很麻烦,效率不高,需要挪动整体数据,或是挪动目标buff数组,并记录每个buff数组的大小。在遍历时,deque的迭代器需要频繁检测是否移动到某段小空间的边界,效率低下。所以deque比较适合头插尾插多的情况,比如作为stack和queue的底层数据结构。stack和queue不需要遍历(所以没有迭代器),只需要在固定的两端进行操作。stack中元素增长时,如果需要扩容,deque的效率比vector高;queue同理,且内存使用率高。

priority_queue优先级队列

priority_queue文档介绍

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

类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。

优先队列被实现为容器适配器,即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的尾部弹出,其成为优先队列的顶部。

底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:

  • empty():检测容器是否为空
  • size():返回容器中有效元素个数
  • front():返回容器中第一个元素的引用
  • push_back():在容器尾部插入元素
  • pop_back():删除容器尾部元素

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

需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了对算法将vector中元素构造成堆的结构,因此priority_queue就是堆。注意:默认情况下priority_queue是大堆。

在OJ中的使用:

数组中的第k个最大元素

题目描述:给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(),nums.end());
        //默认大堆,取出前k-1个元素后的第k个堆顶元素就是第k大的元素
        while(--k)
        {
            pq.pop();
        }

        return pq.top();
    }
};

priority_queue的模拟实现

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

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;
		}
	};

	//模板参数--类型
	//函数参数--对象

	//less 大堆
	template<class T,class Container=::vector<T>,class Compare=Less<typename Container::value_type>>
	class priority_queue
	{
	public:
		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--)
			{
				AdjustDown(i);
			}
		}

		void AdjustDown(size_t parent)
		{
			Compare com;
			int child = parent * 2+1;
			while (child <_con.size())
			{
				if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))
				{
					child++;
				}
				//_con[parent] < _con[child]
				if (com(_con[parent] , _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void AdjustUp(size_t child)
		{
			Compare com;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_con[parent] , _con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void push(const T& x)
		{
			_con.push_back(x);
			AdjustUp(_con.size() - 1);
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}

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

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

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

	private:
		Container _con;
	};

	void test_priority_queue()
	{
		list<int> lt = { 1,2,3,4,5, };
		priority_queue<int, vector<int>, Greater<int>> pq(lt.begin(), lt.end());

		pq.push(10);
		pq.push(20);
		pq.push(30);
		pq.push(40);
		pq.push(50);
		pq.push(60);

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

通过仿函数控制比较方式

如果在priority_queue中放自定义类型的数据,我们需要在自定义类型中重载>或<。如以下情形,类型T是Date*,如果不重载<或>,比较的就是地址大小。

//仿函数的变异玩法--通过仿函数控制比较方式
class Date
{
public:
	Date(int year=1900,int month=1,int day=1)
		:_year(year)
		,_month(month)
		,_day(day)
	{}

	bool operator < (const Date& d) const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}

	friend ostream& operator<<(ostream& _cout, const Date& d);
	friend class PDateLess;

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

ostream& operator<<(ostream& _cout, const Date& d)
{
	_cout << d._year << "-" << d._month << "-" << d._day << endl;
	return _cout;
}

class PDateLess
{
public:
	bool operator()(const Date* p1, const Date* p2)
	{
		return *p1 < *p2;
	}
};

int main()
{
	priority_queue<Date*, vector<Date*>, PDateLess> pq;
	pq.push(new Date(2023, 11, 24));
	pq.push(new Date(2021, 10, 24));
	pq.push(new Date(2023, 11, 14));
	pq.push(new Date(2022, 1, 24));

	cout << (*pq.top()) << endl;
	pq.pop();

	return 0;

}

到此这篇关于C++ stack和queue的文章就介绍到这了,更多相关C++ stack内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++ STL容器stack和queue详解

    stack是一个比较简单的容器,它的使用也很简单,stack是LIFO容器,就是后进先出,最后添加进去的元素,第一个取出来 stack初始化 std::stack<int> first; std::stack<int> second(first); std::stack<int, std;:vector<int>> third; //使用vector初始化stack ### stack常用方法### empty();//判断是否为空 push(Elem e)

  • C++中stack、queue、vector的用法详解

    一.栈(stack) 引入头文件 #include<stack> 常用的方法 empty() 堆栈为空则返回真 pop() 移除栈顶元素 push() 在栈顶增加元素 size() 返回栈中元素数目 top() 返回栈顶元素 3.实例代码 #include<iostream> #include<stack> using namespace std; int main(){ //创建栈 s stack<int> s; //将元素压入栈 for(int i=0;

  • c++中stack、queue和vector的基本操作示例

    前言 这几天在接触搜索的题目,用bfs时基本都用到队列,就顺便学习了数据结构的栈.队列.本文将详细给大家介绍关于c++中stack.queue和vector的基本操作,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. stack 的基本操作有: 入栈,如例:s.push(x); 出栈,如例:s.pop();注意,出栈操作只是删除栈顶元素,并不返回该元素. 访问栈顶,如例:s.top() 判断栈空,如例:s.empty() ,当栈空时,返回true. 访问栈中的元素个数,如例:s.

  • C++stack与queue模拟实现详解

    目录 stack与queue模拟实现 stack queue 为什么选择deque作为stack和queue的底层默认容器 总结 stack与queue模拟实现 在stl中,stack(栈)与queue(队列)都是容器适配器. 什么是容器适配器呢? 适配器(adaptor)是标准库中通用的概念,包括容器适配器.迭代器适配器和函数适配器.本质上,适配器是使一事物的行为类似于另一事物的行为的一种机制.容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现.简单来说其实就是利用现有的容

  • C++ 超详细讲解stack与queue的使用

    目录 stack 介绍和使用 模拟实现 stack的使用例题 最小栈 栈的弹出压入序列 逆波兰表达式求值 queue 模拟实现 容器适配器 deque简介 priority_queue优先级队列 priority_queue的使用 priority_queue的模拟实现 通过仿函数控制比较方式 stack 介绍和使用 stack文档介绍 stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作. stack是作为容器适配器被实现的,容器适

  • C++ 详细讲解stack与queue的模拟实现

    目录 容器适配器 双端队列 概念 结构 deque迭代器 优缺点 stack模拟 queue模拟实现 容器适配器 适配器是一种设计模式(设计模式是一套反复使用的.大部分人知道的代码设计经验的总结),该模式试讲一个类的接口转化为用户希望的另一个接口,虽然stack与queue中也可以存放元素,但在STL中并没有将其划分为容器,而是成为容器适配器,这是因为stack与队列只是堆其他容器进行了包装,STL中的stack和queue是使用双端队列进行封装的. 双端队列 概念 它是一种双开口的连续空间数据

  • C语言超详细讲解栈与队列实现实例

    目录 1.思考-1 2.栈基本操作的实现 2.1 初始化栈 2.2 入栈 2.3 出栈 2.4 获取栈顶数据 2.5 获取栈中有效元素个数 2.6 判断栈是否为空 2.7 销毁栈 3.测试 3.1测试 3.2测试结果 4.思考-2 5.队列的基本操作实现 5.1 初始化队列 5.2 队尾入队列 5.3 队头出队列 5.4 队列中有效元素的个数 5.5 判断队列是否为空 5.6 获取队头数据 5.7 获取队尾的数据 5.8 销毁队列 6.测试 6.1测试 6.2 测试结果 1.思考-1 为什么栈用

  • C++ Boost Lockfree超详细讲解使用方法

    目录 一.说明 二.示例和代码 Boost.Lockfree 一.说明 Boost.Lockfree 提供线程安全和无锁容器.可以从多个线程访问此库中的容器,而无需同步访问. 在 1.56.0 版本中,Boost.Lockfree 只提供了两个容器:boost::lockfree::queue 类型的队列和 boost::lockfree::stack 类型的栈.对于队列,可以使用第二个实现:boost::lockfree::spsc_queue.此类针对只有一个线程写入队列和只有一个线程从队列

  • C++ Boost Assign超详细讲解

    目录 说明 Exercise 说明 Boost.Assign Boost.Assign 库提供了帮助函数来初始化容器或向容器添加元素.如果需要将许多元素存储在一个容器中,这些函数尤其有用.多亏了 Boost.Assign 提供的函数,您不需要重复调​​用像 push_back() 这样的成员函数来将元素一个一个地插入到容器中. 如果您使用支持 C++11 的开发环境,则可以从初始化列表中获益.通常您可以将任意数量的值传递给构造函数来初始化容器.多亏了初始化列表,你不必依赖 C++11 的 Boo

  • Java 超详细讲解数据结构中的堆的应用

    目录 一.堆的创建 1.向下调整(以小堆为例) 2.创建堆 3.创建堆的时间复杂度 二.堆的插入和删除 1.堆的插入 2.堆的删除 三.堆的应用 1.堆排序 2.top-k问题 [求最小的K个数] 四.常用接口的介绍 1.PriorityQueue的特性 2.优先级队列的构造 一.堆的创建 1.向下调整(以小堆为例) 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子) 如果parent的左孩子存在,即:child < size,

  • Java 超详细讲解十大排序算法面试无忧

    目录 排序算法的稳定性: 一.选择排序 二.冒泡排序 三.插入排序 四.希尔排序 五.堆排序 六.归并排序 七.快速排序 八.鸽巢排序 九.计数排序 十.基数排序 排序算法的稳定性: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,如果排序以后,保证这些记录的相对次序保持不变,即在原序列中,a[i]=a[j],且 a[i] 在 a[j] 之前,排序后保证 a[i] 仍在 a[j] 之前,则称这种排序算法是稳定的:否则称为不稳定的. 一.选择排序 每次从待排序的元素中选择最小的元素,依次

  • Java 超详细讲解数据结构的应用

    目录 一.bfs 二.双端队列 三.算法题 1.kotori和迷宫 2.小红找红点 3.小红玩数组  一.bfs bfs(广度优先搜索),类似二叉树的层序遍历,利用队列完成.一般用于求最短路. 图的最短路问题: 给定一个无向图,每条边的长度都是1.求1号点到x号点的最短距离. 顶点数n  边数为m q次询问  输入x 输出1到x的最短距离. 若1号点到x不连通,则输出-1 二.双端队列 双端队列的应用(区间翻转): 对于长度为n的数组,给定一个长度为m的区间,区间初始位置为a[1]到a[m].

  • 四个实例超详细讲解Java 贪心和枚举的特点与使用

    目录 贪心: 枚举: 1.朴素枚举 2.状压枚举    算法题1: 示例 算法题2: 示例 算法题3:  示例1 示例2 算法题4:  示例1 笔试技巧:学会根据数据范围猜知识点          一般1s 时间限制的题目,时间复杂度能跑到 1e8 左右( python 和 java 会少一些,所以建议大家使用c/c++ 做笔试题). n 范围 20 以内: O(n*2^n) 状压搜索 /dfs 暴搜 n 范围 200 以内: O(n^3) 三维 dp n 范围 3000 以内: O(n^2)

  • C语言超详细讲解栈的实现及代码

    目录 前言 栈的概念 栈的结构 栈的实现 创建栈结构 初始化栈 销毁栈 入栈 出栈 获取栈顶元素 获取栈中有效元素个数 检测栈是否为空 总代码 Stack.h 文件 Stack.c 文件 Test.c 文件 前言 栈的概念 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则.有点类似于手枪弹夹,后压进去的子弹总是最先打出,除非枪坏了. 压栈:栈的插入

随机推荐