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

【C++】了解stack和queue

article 2025/1/20 8:45:16

目录

stack介绍

栈的结构

栈接口的使用

栈的基本题目

最小栈

栈的弹出压入序列

二叉树的分层遍历

栈的模拟实现

stack.h文件

队列的介绍

队列的结构

队列接口的使用

队列的模拟实现

priority_queue的介绍和使用

接口使用

优先级队列的题目应用

数组中第k大的数字

优先级队列的模拟实现

priority_queue.h文件

deque的介绍

deque的缺陷

stack介绍

我们可以搜一些资料学习栈：栈文档

栈的结构

我们很熟悉了，栈的结构：

栈接口的使用

这些接口比较简单，这里不过多赘述！

栈的基本题目

最小栈

地址：最小栈

思路：

题目的本质是，我们要得到一个栈中的最小元素！

我们可以用两个栈实现一个栈的功能：

定义一个栈_st,里面存储所有插入进来的数据，定义另一个栈_minst,存储小数据，不管在什么时候我们都保证它的栈顶元素是所有数据最小的数。

于是，我们拿栈中的最小元素，只需要返回_minst的栈顶元素即可！

那么关键就在于怎么进行插入和删除的操作而已！

插入时，无论什么数据，_st都要插入，当_minst是空的时候，或者插入的元素小于_minst的栈顶元素时，_minst也插入！

删除时，无论什么数据，_st都要删除，当要删除的元素等于_minst的栈顶元素时，_minst也删除！

代码：

class MinStack {
public:
    MinStack() {
        
    }
    
    void push(int val) {
        //无论如何_st，_st都要push
        _st.push(val);
        //当_minst为空，或者栈顶元素小于或等于val，_minst也push
        if(_minst.empty()||val<=_minst.top())
           _minst.push(val);
    }
    
    void pop() {
        //当_st栈顶的元素和_minst栈顶元素相等，_minst也pop
        if(_st.top()==_minst.top())
            _minst.pop();
        //无论如何，_st都要pop
        _st.pop();
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minst.top();
    }
private:
    stack<int> _st;//存储所有数据
        //存储小数据，无论什么时候，它的栈顶一定是所有数据最小的那个
        stack<int> _minst;
};

栈的弹出压入序列

地址：栈的弹出压入序列

思路：

我们需要模拟入栈出栈即可！

遍历压入序列，入栈，用 i 记录出栈序列的下标，当栈顶元素和出栈序列相等时，出栈，同时 i++，往前走，当栈顶元素和出栈序列不相等时，继续遍历入栈！

有一种情况：比如压入序列：2，1，0,弹出序列：1，2，0。

当入栈到1时，一直出栈到空，此时0还没有入栈，然后判断条件栈顶元素和出栈序列相等，判断不了，因为此时栈是空的，没有栈顶元素，所以我们需要加一个判断条件：栈不为空！

代码：

bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        stack<int> _st;
        size_t i=0;//遍历popV
        //遍历插入
        for(auto& e:pushV)
        {
            _st.push(e);
            //当栈顶元素和popV的元素相等，栈pop
            while(!_st.empty()&&_st.top()==popV[i])
            {
                _st.pop();
                i++;
            }
        }
        return _st.empty();
    }

二叉树的分层遍历

地址：二叉树的层序遍历

思路：

我们首先让根节点先进入队列，根据对头左右节点有就继续进队列，然后队头出队列，循环往复。

只是我们需要插入进一个二维数组，我们可以将这颗树的每一层有多少个节点记录下来！

代码：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> vv;
        int lsize;
        if(root)
        {
            q.push(root);
            lsize=1;
        }
        while(!q.empty())
        {
            vector<int> v;
            while(lsize--)
            {
                if(q.front()->left)
                    q.push(q.front()->left);
                if(q.front()->right)
                    q.push(q.front()->right);
                v.push_back(q.front()->val);
                q.pop();
            }
            lsize=q.size();
            vv.push_back(v);
        }
        return vv;
    }
};

栈的模拟实现

我们仔细观察栈的结构（先进后出），仔细想一下，发现我们可以用一个动态数组来实现它（也可以用链表），

所以我们可以用vector来包装它！

这样就简单很多！

stack.h文件

#include<iostream>
#include<vector>
namespace ywc
{
	template<class T>
	class stack
	{
	public:
		bool empty()
		{
			return _s.empty();
		}
		size_t size()
		{
			return _s.size();
		}
		const T& top()
		{
			return _s.back();
		}
		void push(const T& x)
		{
			_s.push_back(x);
		}
		void pop()
		{
			_s.pop_back();
		}
	private:
		std::vector<T> _s;
	};
}

当然，也能用链表实现！这里不过多赘述！

队列的介绍

文档：队列文档

队列的结构

队列接口的使用

这里也不过多赘述，比较简单！

队列的模拟实现

队列是先进先出，需要头删，用一个动态数组效率太慢，所以我们采用链表！

我们可以用一个list来包装！

代码：

#include<iostream>
#include<list>
namespace ywc
{
  template<class T>
   class queue
   {
public:
	bool empty()
	{
		return _lt.empty();
	}
	size_t size()
	{
		return _lt.size();
	}
	const T& front()
	{
		return _lt.front();
	}
	const T& back()
	{
		return _lt.back();
	}
	void push(const T& x)
	{
		_lt.push_back(x);
	}
	void pop()
	{
		_lt.pop_front();
	}
private:
	std::list<T> _lt;
   };
}

priority_queue的介绍和使用

优先级队列的文档：优先级队列文档

简单介绍一下优先级队列：

不管什么时候，它的第一个元素总是最大的！也能随时插入元素，且只能检索顶部数据，且要删除数据也是删除顶部数据！

所以：

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue。注意：默认情况下priority_queue是大堆。

简单赘述：

优先级队列是底层是一个动态数组（堆），在数组尾部插入，然后利用向上调整法调整数据的分布从而符合堆的特性（大小堆），删除数据时，删除第一个数据，然后利用向下调整法调整数据的分布从而符合堆的特性！

接口使用

接口比较简单，这里不过多赘述！

我们来看一下它的大小堆特性：

但当我们的类型是自定义类型的话：

如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重 载。

如：

优先级队列的题目应用

数组中第k大的数字

地址：数组中第k个大的数字​​​​​​

思路：

我们可以将数组中的数全部放进一个大堆中，然后将前k-1个数删掉，然后栈顶就是我们的第k个大的数字！

代码：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //将数组中的数全部放在一个大堆中
        priority_queue<int> q;
        for(auto& e:nums)
           q.push(e);
        while(--k)//将前k-1个数字pop掉
            q.pop();
        return q.top();
    }
};

优先级队列的模拟实现

根据刚才我们所说的它的特点来包装它，并且参照STL库中的方式！

我们的思路：

priority_queue.h文件

#pragma once

#include<iostream>
#include<vector>
#include<algorithm>
namespace ywc
{
	template<class T>
	struct less
	{
		bool operator()(const T& a, const T& b)
		{
			return a < b;
		}
	};
	template<class T>
	struct greater
	{
		bool operator()(const T& a, const T& b)
		{
			return a > b;
		}
	};
	template<class T,class Container=std::vector<T>,class Compare=less<T>>
	class priority_queue
	{
	public:
		void push(const T& x)
		{
			_c.push_back(x);
			//向上调整
			AdjustUp(size() - 1);
		}
		void pop()
		{
			std::swap(_c[0], _c[size() - 1]);
			_c.pop_back();
			//向下调整
			AdjustDown(0);
		}
		bool empty()
		{
			return size() == 0;
		}
		const T& top()
		{
			return _c.front();
		}
		size_t size() const
		{
			return _c.size();
		}
	private:
		//向上调整
		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)//当孩子等于0时跳出
			{
				if (Compare()(_c[parent],_c[child]))
				{
					std::swap(_c[child], _c[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		//向下调整
		void AdjustDown(int parent)
		{
			int child = parent * 2 + 1;
			while (child < size())
			{
				//假设法，假设左右孩子大小
				if (child + 1 < size() && Compare()(_c[child ] , _c[child+1]))
				{
					child++;
				}
				if (Compare()(_c[parent] , _c[child]))
				{
					std::swap(_c[child], _c[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		Container _c;
	};
}

deque的介绍

先前讲过stack底层是vector,queue底层是list，但其实在STL库中，stack和queue底层默认的容器是deque.

我们现在来介绍一下deque:

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

结构：

注意：deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个 动态的二维数组。

如图：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问 的假象，落在了deque的迭代器身上。

deque的缺陷

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩 容时，也不需要搬移大量的元素，因此其效率是必vector高的。

与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

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

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

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

我们下期见！！！


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

相关文章：

  • 【Django开发】django美多商城项目完整开发4.0第12篇：商品部分,表结构【附代码文档】
  • 机器学习中的方差与偏差
  • 微服务入门：从零开始构建你的微服务架构
  • 麒麟操作系统服务架构保姆级教程（十一）https配置
  • 移动端布局 ---- 学习分享
  • 6、原来可以这样理解C语言_函数（1/8）函数的概念
  • nlp培训重点-3
  • Coder星球-测试用例设计
  • 【脑机接口数据处理】 如何读取Trode 的.rec文件 原始数据？
  • Linux虚拟机安装与FinalShell使用：探索Linux世界的便捷之旅
  • 机器学习：监督学习与非监督学习
  • 【Rust自学】13.8. 迭代器 Pt.4：创建自定义迭代器
  • 解锁C#语法的无限可能：从基础到进阶的编程之旅
  • YOLOv10-1.1部分代码阅读笔记-loss.py
  • 达梦数据库经验笔记
  • React第二十三章(useId)
  • 深度学习 DAY2：Transformer（一部分）
  • BPF CO-RE（三）——在用户开发中的应用
  • 开源AI图像工具—Stable Diffusion
  • ubuntu 22 安装vmware 17.5
  • SSL/TLS的数据压缩机制
  • PCL 部分点云视点问题【2025最新版】
  • IO进程----进程
  • 【Python】函数
  • git 查看修改和 patch
  • Flutter 和 Compose Multiplatform对比