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

C++ 复习总结记录十

article 2025/1/28 18:56:56

C++ 复习总结记录十

主要内容

1、stack 介绍和使用

2、queue 介绍和使用

3、priority_queue 介绍和使用

4、容器适配器

一 stack 的介绍和使用

stack 文档介绍

1、 stack 是容器适配器，专用于后进先出的操作，只能从容器尾端进行元素插入和提取

2、 容器适配器是对特定类封装作为底层容器，并提供一组特定的成员函数

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

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

4、标准容器 vector、deque、list 均符合上述需求，stack 的默认底层容器是 deque

image-20250124112549918

1.1 stack 的使用

函数说明 						接口说明
stack() 					构造空的栈
empty() 					检测 stack 是否为空
size() 						返回 stack 中元素的个数
top() 						返回栈顶元素的引用
push() 						将元素 val 压入 stack 中
pop() 						将 stack 中尾部的元素弹出

1.2 练习

最小栈

class MinStack {
public:
    MinStack() {}
    
    void push(int val) 
    {
        if(minStack.size() == 0 || val <= minStack.top()) //若最小栈为空或插入数据小于或等于栈顶元素
            minStack.push(val); //入最小栈
        src.push(val); //所有数据栈, 则直接入栈
    }
    
    void pop() 
    {
        if(minStack.size() != 0 && src.top() == minStack.top()) //若最小栈不为空且删除数据所有数据栈顶元素等于最小栈顶元素
            minStack.pop(); //删除最小栈顶元素
        src.pop(); //所有数据栈, 则直接删除栈顶元素
    }
    
    int top() 
    {
        return src.top(); //返回所有数据栈顶元素
    }
    
    int getMin() 
    {
        return minStack.top(); //返回最小栈顶元素
    }
    
private:
    stack<int> src; //所有数据的栈
    stack<int> minStack; //最小栈
};

栈的弹出压入序列

bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
{
    stack<int> data; //data 模拟进出栈过程
    int p1 = 0, p2 = 0; //p1, p2 是对用 vector 的下标

    while(p1 < pushV.size()) //入栈顺序数据不为空
    {
        data.push(pushV[p1]); //直接入栈
        while (p2 < popV.size() && 
               data.size() !=0 && 
               data.top() == popV[p2]) //判断栈顶元素是否和出栈数据相同(注意边界条件)
        {
            data.pop(); //出栈
            ++p2; //移动下标
        }
        ++p1; //移动下标
    }
    return data.size() == 0; //校验栈内是否还有数据
}

逆波兰表达式求值

int evalRPN(vector<string>& tokens) {
    stack<int> ans;
    int left = 0, right = 0;
    for (auto& str : tokens)
    {
        if (!("+" == str || "-" == str || "*" == str || "/" == str)) //注意这里的判断条件不能用 str[0] >= '0', 因为可能有负数
        {
            ans.push(stoi(str)); //C++11, C 风格转换 atoi(str.c_str());
        }
        else
        {
            right = ans.top(); //注意这里栈顶元素是右操作数
            ans.pop();
            left = ans.top();
            ans.pop();

            switch(str[0])
            {
                case '+':
                    ans.push(left + right);
                    break;
                case '-':
                    ans.push(left - right);
                    break;
                case '*':
                    ans.push(left * right);
                    break;
                case '/':
                    ans.push(left / right);
                    break;
            }
        }            
    }
    return ans.top();
}

用两个栈实现队列

class MyQueue {
public:
    MyQueue() {}
    
    void push(int x) 
    {
        s1.push(x);
    }
    
    int pop() 
    {
        int res = peek();
        s2.pop();
        return res;
    }
    
    int peek() 
    {
        if (s2.size() == 0) //若 s2 为空, 需要把 s1 数据搬至 s2
        {
            while(s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
        }
        return s2.top();  //s2 栈顶元素即为队列头元素
    }
    
    bool empty() 
    {
        return s1.size() == 0 && s2.size() == 0;
    }

private:
    stack<int> s1;
    stack<int> s2;
};

1.3 stack 模拟实现

使用 vector 模拟实现 stack

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

二 queue 的介绍和使用

queue 文档介绍

1、队列是一种容器适配器，用于 FIFO ( 先进先出 ) 操作，从容器一端插入元素，另一端提取元素

2、底层容器可以是标准容器类模板之一，也可是其它专门设计的容器类。该底层容器应至少支持以下操作

  • empty 检测队列是否为空
  • size 返回队列中有效元素个数
  • front 返回队头元素引用
  • back 返回队尾元素引用
  • push_back 在队列尾部入队列
  • pop_front 在队列头部出队列

4、标准容器类 deque 和 list 满足了这些要求。默认情况下 queue 指定使用标准容器 deque

image-20250124140046765

2.1 queue 的使用

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

用队列实现栈

class MyStack {
public:
    MyStack() {}
    
    void push(int x) 
    {
        q2.push(x); //元素先入 q2
        while(!q1.empty()) //若 q1 不为空, 拷 q1 数据至 q2
        {
            q2.push(q1.front()); //将 q1 首元素拷至 q2
            q1.pop(); //删除队列首元素
        }
        q1.swap(q2); //数据交换
    }
  
    int pop() 
    {
        int res = q1.front();
        q1.pop(); //删除 q1 队列首元素
        return res;
    }
    
    int top() { return q1.front(); }
    
    bool empty() { return q1.empty(); }

private:
    queue<int> q1;
    queue<int> q2;
};

2.2 queue 模拟实现

queue 接口中存在头删和尾插，使用 vector 封装效率太低，借助 list 模拟实现 queue

#include <list>
namespace lucky
{
    template<class T>
    class queue
    {
    public:
        queue() {}
        
        void push(const T& x) { _c.push_back(x); }
        
        void pop() { _c.pop_front(); }
        
        T& back() { return _c.back(); }
        
        const T& back() const { return _c.back(); }
        
        T& front() { return _c.front(); }

        const T& front() const { return _c.front(); }
        
        size_t size() const { return _c.size(); }
        
        bool empty() const { return _c.empty(); }
        
    private:
        std::list<T> _c;
    };
}

三 priority_queue 的介绍和使用

priority_queue 文档介绍

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

2、数据结构类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素 ( 优先队列中位于顶部的元素 )

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

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

4、标准容器类 vector 和 deque 满足上述需求；默认情况下，priority_queue 类实例化的容器类是 vector

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

3.1 priority_queue 的使用

优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将 vector 中元素构造成堆结构。

因此 priority_queue 就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue，注意：默认情况下 priority_queue 是大堆

函数声明 					接口说明
priority_queue() 		构造一个空的优先级队列
priority_queue(first,last)  构造一个优先级队列
empty() 		检测优先级队列是否为空, 是返回 true, 否则返回 false
top() 			返回优先级队列中最大(最小元素)，即堆顶元素
push(x) 		在优先级队列中插入元素 x
pop() 			删除优先级队列中最大(最小)元素，即堆顶元素

默认情况下，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;
}

如果在 priority_queue 中放自定义类型数据，需在自定义类型中提供 > 或 < 重载

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);
    }
    
    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)
    {
        _cout << d._year << "-" << d._month << "-" << d._day;
        return _cout;
    }
    
private:
    int _year;
    int _month;
    int _day;
};

void TestPriorityQueue()
{
    // 大堆需要自定义类型中提供 < 重载
    priority_queue<Date> q1;
    q1.push(Date(2018, 10, 29));
    q1.push(Date(2018, 10, 28));
    q1.push(Date(2018, 10, 30));
    cout << q1.top() << endl;
    
    // 创建小堆提供 > 重载
    priority_queue<Date, vector<Date>, greater<Date>> q2;
    q2.push(Date(2018, 10, 29));
    q2.push(Date(2018, 10, 28));
    q2.push(Date(2018, 10, 30));
    cout << q2.top() << endl;
}

3.2 练习

数组中第 K 大的元素

方法一 最大堆 : 时间复杂度 N * logN，空间复杂度 log N

#include<functional>
int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, less<int>> p1(nums.begin(), nums.end()); //遍历时间复杂度 N, 调整最大堆时间复杂度 logN
    
    while (k-- > 1)
    {
    	p1.pop();
    }
    return p1.top();
}

方法二 排序 : 时间复杂度 N * logN，空间复杂度 O(1)

int findKthLargest(vector<int>& nums, int k) {
	sort(nums.begin(), nums.end());
    return nums[nums.size() - k];
}

方法三 最小堆 : 时间复杂度 N * logK，空间复杂度 logK

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> p1(nums.begin(), nums.begin() + k);

    for (int i = k; i < nums.size(); ++i)
    {
        if (nums[i] > p1.top())
        {
            p1.pop();
            p1.push(nums[i]);
        }
    }
    return p1.top();
}

3.3 priority_queue 模拟实现

priority_queue 的底层结构就是堆，此处只需对其进行通用封装即可

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

#include <vector>
// priority_queue ---> 堆
namespace lucky
{
	template<class T>
	struct less
	{
		bool operator()(const T& left, const T& right)
		{
			return left < right;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& left, const T& right)
		{
			return left > right;
		}
	};

	template<class T, class Container = std::vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		// 创造空的优先级队列
		priority_queue() : c() {}

		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
			: c(first, last)
		{
			// 将 c 中的元素调整成堆的结构
			int count = c.size();
			int root = ((count - 2) >> 1);
			for (; root >= 0; root--)
				AdjustDown(root);
		}

		void push(const T& data)
		{
			c.push_back(data);
			AdjustUP(c.size() - 1);
		}

		void pop()
		{
			if (empty())
				return;

			swap(c.front(), c.back());
			c.pop_back();
			AdjustDown(0);
		}

		size_t size() const
		{
			return c.size();
		}

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

		// 堆顶元素不允许修改，因为：堆顶元素修改可以会破坏堆的特性
		const T& top()const
		{
			return c.front();
		}
        
	private:
		// 向上调整
		void AdjustUP(int child)
		{
			int parent = ((child - 1) >> 1);
			while (child)
			{
				if (Compare()(c[parent], c[child]))
				{
					swap(c[child], c[parent]);
					child = parent;
					parent = ((child - 1) >> 1);
				}
				else
				{
					return;
				}
			}
		}

		// 向下调整
		void AdjustDown(int parent)
		{
			size_t child = parent * 2 + 1;
			while (child < c.size())
			{
				// 找以 parent 为根的较大的孩子
				if (child + 1 < c.size() && Compare()(c[child], c[child + 1]))
					child += 1;

				// 检测双亲是否满足情况
				if (Compare()(c[parent], c[child]))
				{
					swap(c[child], c[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					return;
			}
		}
        
	private:
		Container c;
	};
}

void TestQueuePriority()
{
	lucky::priority_queue<int> q1;
	q1.push(5);
	q1.push(1);
	q1.push(4);
	q1.push(2);
	q1.push(3);
	q1.push(6);
	cout << q1.top() << endl;

	q1.pop();
	q1.pop();
	cout << q1.top() << endl;

	vector<int> v{ 5,1,4,2,3,6 };
	lucky::priority_queue<int, vector<int>, lucky::greater<int>> q2(v.begin(), v.end());
	cout << q2.top() << endl;

	q2.pop();
	q2.pop();
	cout << q2.top() << endl;
}

四 容器适配器

适配器是一种设计模式 ( 设计模式是一套被反复使用的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类接口转换成期望的另一个接口

image-20250124152438232

STL 标准库中 stack 和 queue 的底层结构

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

image-20250124152638179

image-20250124152704783

image-20250124152720624

4.1 deque 介绍

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

image-20250124152918989

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

image-20250124153023654

双端队列的连续空间，实际是分段连续的，其整体连续以及随机访问的功能，主要因为 deque 的迭代器，设计如下

image-20250124153207756

image-20250124153234340

4.2 deque 缺陷

与 vector 相比，deque 优势是头部插入和删除时，不需要搬移元素，效率特别高且扩容时，也不需要搬移元素，效率 vector 高

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

deque 的缺陷是不适合遍历，因为在遍历时，deque 迭代器要频繁的去检测其是否移动到某段小空间边界，导致效率低下。而序列式场景中，可能需要经常遍历，因此在大多数线性结构情况下，使用的是 vector 和 list，deque 应用并不多

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

stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back 和 pop_back 操作的线性结构，都可以作为 stack 的底层容器，比如 vector 和 list 等

queue 是先进先出的特殊线性数据结构，只要具有 push_back 和 pop_front 操作的线性结构，都可以作为 queue 的底层容器，比如 list 等

STL 中对 stack 和 queue 默认选择 deque 作为其底层容器，主要因为

① stack 和queue 不需要遍历 (因此 stack 和 queue 没有迭代器)，只需要在固定的一端或者两端进行操作

② 在 stack 中元素增长时，deque 比 vector 的效率高 ( 扩容时不需要搬移大量数据 ) queue 中的元素增长时，deque 不仅效率高，且空间利用率高

4.4 STL 中对 stack 和 queue 模拟实现

stack 模拟实现

#include<deque>
namespace lucky
{
    template<class T, class Con = deque<T>>
    //template<class T, class Con = vector<T>>
    //template<class T, class Con = list<T>>
    class stack
    {
    public:
        stack() {}
        
        void push(const T& x) { _c.push_back(x); }
        
        void pop() { _c.pop_back(); }
        
        T& top() { return _c.back(); 1}
        
        const T& top() const {return _c.back();}
        
        size_t size() const {return _c.size();}
        
        bool empty() const {return _c.empty();}
        
    private:
        Con _c;
    };
}

queue 模拟实现

#include<deque>
#include <list>
namespace lucky
{
    template<class T, class Con = deque<T>>
    //template<class T, class Con = list<T>>
    class queue
    {
    public:
        queue() {}
        
        void push(const T& x) { _c.push_back(x); }
        
        void pop() { _c.pop_front(); }
        
        T& back() { return _c.back(); }
        
        const T& back() const { return _c.back(); }
        
        T& front() { return _c.front(); }
        
        const T& front() const { return _c.front(); }
        
        size_t size() const { return _c.size(); }
        
        bool empty() const { return _c.empty(); }
        
    private:
        Con _c;
    };
}

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

相关文章：

  • DeepSeek-R1 蒸馏模型及如何用 Ollama 在本地运行DeepSeek-R1
  • JAVA 接口、抽象类的关系和用处 详细解析
  • 2024年除夕
  • 多模态论文笔记——TECO
  • 2.策略模式（Strategy）
  • 高德开放平台：红绿灯倒计时与车车协同安全预警，开启出行新时代
  • transformers报错：‘GenerationConfig‘ object has no attribute ‘_eos_token_tensor‘
  • INCOSE需求编写指南-第1部分：介绍
  • 基于Hadoop的汽车大数据分析系统设计与实现【爬虫、数据预处理、MapReduce、echarts、Flask】
  • 【GO】Context
  • 亚博microros小车-原生ubuntu支持系列：11手指控制与手势识别
  • 活动回顾和预告｜微软开发者社区 Code Without Barriers 上海站首场活动成功举办！
  • Queries Acceleration -Tuning- Tuning Execution 学习笔记
  • 在Android中通过JNI实现Java与C++的交互：Hello World示例
  • C++中static和const的区别和用法
  • leetcode——相交链表（java）
  • Spring Boot - 数据库集成02 - 集成JPA
  • DSP实验七 综合实验与考查
  • 数据库之PostgreSQL详解
  • 构建基于知识图谱的语义化问答系统
  • ray.rllib 入门实践-2：配置算法
  • Lua 初级教程
  • Android BitmapShader简洁实现马赛克，Kotlin（二）
  • Java设计模式 三十 状态模式 + 策略模式
  • ProfiNet转CANopen应用于汽车总装生产线输送设备ProfiNet与草棚CANopen质量检测系统
  • C++ —— vector 容器