网站后台管理系统 英文,wordpress网址设置,做个 公司网站多少钱,wordpress做小程序商城公主请阅 容器适配器容器适配器的特点 栈和队列的模拟实现deque的介绍1. 内存开销较高2.随机访问性能略低于 vector3. 与指针或迭代器的兼容性r4. 不适合用于需要频繁中间插入和删除的场景5. 在特定平台上的实现不一致6. 缺乏shrink_to_fit支持总结 题目 priority_queue 优先级… 公主请阅 容器适配器容器适配器的特点 栈和队列的模拟实现deque的介绍1. 内存开销较高2.随机访问性能略低于 vector3. 与指针或迭代器的兼容性r4. 不适合用于需要频繁中间插入和删除的场景5. 在特定平台上的实现不一致6. 缺乏shrink_to_fit支持总结 题目 priority_queue 优先级队列使用最小优先队列使用场景 priority_queue的模拟实现 仿函数的介绍仿函数的基本概念仿函数的基本用法仿函数的优点常见的仿函数应用示例在STL中使用仿函数总结 题目155.最小栈JZ31 栈的压入、弹出序列150. 逆波兰表达式求值232. 用栈实现队列225. 用队列实现栈 容器适配器
容器适配器Container Adapter是C标准模板库STL中的一种设计模式专门用于提供一种经过简化和限制的接口使得不同的容器类型可以表现出类似的行为。容器适配器不会创建新的容器而是基于已有的容器如 deque、vector 等进行包装以改变或限制其接口从而提供不同的行为和使用方式。
STL 中常见的容器适配器有以下三种
栈Stack 使用 std::stack 类实现。 默认底层容器为 std::deque也可以用 std::vector 或 std::list 替换。 栈是“后进先出” (LIFO) 数据结构适配器屏蔽了底层容器的大部分接口提供 push、pop 和 top 操作。
队列Queue 使用 std::queue 类实现。 默认底层容器为 std::deque也可以使用其他序列容器如 std::list。 队列是“先进先出” (FIFO) 数据结构适配器仅保留 push、pop 和 front、back 等接口。
优先级队列Priority Queue 使用 std::priority_queue 类实现。 默认底层容器为 std::vector底层使用堆结构进行元素排序。 优先级队列允许快速访问和移除最高优先级的元素。适配器提供 push、pop 和 top 操作自动按照优先级排序。
容器适配器的特点 简化接口容器适配器通过隐藏底层容器的复杂接口使用户能够更专注于特定的数据结构如栈或队列的特性。 灵活底层容器容器适配器可以基于不同的底层容器构建但需满足特定的要求。例如栈可以用 deque 或 vector 作为底层容器。 与容器解耦通过使用适配器用户不需要关心底层容器的实现细节只需专注于适配器提供的接口。
总体而言容器适配器是一种设计模式通过包装现有容器来提供定制化的数据结构接口使程序设计更加简单和灵活。 栈和队列的模拟实现
我们通过适配器就能将栈和队列进行模拟实现了
stack.h
#pragma once
#includevector
#includelist
#includedeque
//templateclass T
//class stack
//{
//private:
// T* a;
// size_t _top;
// size_t _capacity;
//};// T栈中存储的数据类型和 Container底层容器类型
/*
当你在实例化这个模板类时例如 stackint, std::vectorint myStack;编译器就会根据传入的模板参数 int 和 std::vectorint 来推导出具体的 T 和 Container 类型。
模板实例化在编译阶段编译器会用传递的模板参数类型 T 和 Container 来实例化这个模板类 stack并生成相应的类定义。例如如果你传入的是 stackint, std::vectorint
编译器会生成一个 stackint, std::vectorint 的具体实例并将代码中所有的 T 替换为 intContainer 替换为 std::vectorint。
模板函数的调用在使用这个栈的成员函数时编译器也会根据实例化后的具体类型来判断类型。例如 _con.push_back(x); 调用时
编译器会检查 _con 是什么容器类型在这种情况下是 std::vectorint从而验证 push_back 是否可以接受 int 类型的参数 x。
*///T是元素的类型这个Container是容器的类型我们通过容器进行函数的调用操作
namespace kai
{//函数参数能加缺省值那么我们的模版参数也是可以加缺省值的//如果我们没传的话就用的是缺省值传了的话那么就用我们传的值//我们这里默认用的是一个deque的容器templateclass T, class ContainerdequeT//Container就是容器的意思,存的是底层的数据类型class stack{public:void push(const T x){_con.push_back(x);}void pop()//不需要加参数 {_con.pop_back();//将尾部的数据pop掉}const T top() const//返回栈顶位置数据{return _con.back();//直接返回尾部的数据通用接口}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}queue.h
#pragma once
#includevector
#includelist
#includedequenamespace kai
{//deque既可以做栈也可以做队列的适配容器templateclass T, class Container dequeT//Container就是容器的意思,存的是底层的数据类型class queue//队尾入数据队头出数据{//vector不能适配队列这里不能头删public:void push(const T x)//入队列--尾{_con.push_back(x);}void pop()// 出队列---头删{_con.pop_front();//将头部的数据pop掉}const Tfront() const{return _con.front(); //直接返回头部的数据通用接口}const T back() const//返回栈顶位置数据{return _con.back();//直接返回尾部的数据通用接口}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};}
test.h
#define _CRT_SECURE_NO_WARNINGS 1
#includeiostream
#includestack
#includequeue#includestack.h
#includeQueue.h
using namespace std;
int main()
{kai::stackint,listintst;//前面是数据的类型。后面是容器的类型st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty())//不断取值直到栈为空{cout st.top() ;st.pop();//头删替换下个数据}cout endl;//这里的vector是会报错的因为vector是不支持这里的pop的kai::queueint, listintq;//前面是数据的类型。后面是容器的类型q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty())//不断取值直到栈为空{cout q.front() ;q.pop();//头删替换下个数据}cout endl;return 0;
}当你在实例化这个模板类时例如 stackint, std::vector myStack;编译器就会根据传入的模板参数 int 和 std::vector 来推导出具体的 T 和 Container 类型。 模板实例化在编译阶段编译器会用传递的模板参数类型 T 和 Container 来实例化这个模板类 stack并生成相应的类定义。例如如果你传入的是 stackint, std::vector 编译器会生成一个 stackint, std::vector 的具体实例并将代码中所有的 T 替换为 intContainer 替换为 std::vector。 模板函数的调用在使用这个栈的成员函数时编译器也会根据实例化后的具体类型来判断类型。例如 _con.push_back(x); 调用时 编译器会检查 _con 是什么容器类型在这种情况下是 std::vector从而验证 push_back 是否可以接受 int 类型的参数 x。 deque的介绍 deque叫做双端队列两端都可以进行插入删除的操作
头尾都可以支持插入删除数据的
deque的技能树点的比较满啥都会
那么就说明deque就可以将list和vector的技能都带上
vector是一块连续的空间list是一个个小块的空间通过指针进行连接起来的 deque的缺陷在哪里呢
insert和erase
1.挪动后面所有数据效率低
2.只挪动当前buffer的数据每个buffer大小就不一样了insert 、 erase的效率不错但是[]的效率直线下降
deque的头尾插入删除的效率还是不错的
适当的下标访问可以使用deque
但是得大量的下标访问就不适合用deque了
所以栈和队列的适配容器是deque
deque的核心结构是迭代器进行支撑的 deque里面只有两个迭代器start和finish
在 C 中deque 是一种双端队列容器允许在两端高效地插入和删除元素。尽管 deque 在某些方面具有优势但在特定使用场景下仍然存在一些缺陷或限制
1. 内存开销较高 deque 的内存布局并不像 vector 一样是连续的内存块而是分段的。这使得 deque 会有额外的内存管理开销因此其内存利用率通常比 vector 低。 对于需要大量小型数据结构的应用deque 的内存分块可能带来一定的开销。
2.随机访问性能略低于 vector
虽然 deque 支持随机访问允许使用 operator[] 和 at但由于 deque 是分块存储的因此在访问元素时尤其是访问中间位置的元素时性能会略低于 vector因为它需要定位具体的分块位置。
3. 与指针或迭代器的兼容性r deque 的指针或迭代器在插入和删除操作后可能会失效尤其是在中间插入或删除元素时。 虽然 deque 的头尾插入操作不会像 vector 一样导致整个容器重新分配但在扩展容量时它可能会重新配置分块这会导致指针和迭代器失效。
4. 不适合用于需要频繁中间插入和删除的场景
deque 在头尾的插入和删除操作效率很高但在中间位置插入或删除元素时会导致较多的数据移动从而影响性能。因此如果需要频繁在中间位置进行插入或删除操作deque 不是最佳选择list 或 std::vector如果可以接受一定的重新分配开销可能会更合适。
5. 在特定平台上的实现不一致
不同的编译器和标准库实现可能会对 deque 采用不同的分块策略。这可能导致在不同平台上的性能和内存使用情况有所不同从而带来一些不可预测的行为。
6. 缺乏shrink_to_fit支持
C 标准中没有要求 deque 支持 shrink_to_fit即使进行了删除操作deque 可能不会自动释放不再使用的内存导致可能的内存浪费。
总结
deque 在需要高效的双端插入和删除操作时非常有用但在需要频繁的中间操作或更高的随机访问性能时它的效率可能不如 vector。选择容器时应根据具体需求进行权衡以最大限度地发挥各容器的优势。
题目
215. 数组中的第K个最大元素 class Solution {
public:int findKthLargest(vectorint nums, int k){//将数组中的元素先放入到优先级队列中,默认是大堆priority_queueint p(nums.begin(),nums.end());//我们删除k-1次那么循环结束的时候的堆顶的数据就是当前最大了的我们直接返回堆顶数据就行了while(--k)//--k是走k-1次,k--是走k次{p.pop();}return p.top();}
};priority_queue 优先级队列
默认是大的优先级最高
priority_queue 是一种基于优先级的队列数据结构通常实现为一个堆heap可以支持快速插入和删除优先级最高的元素。在 priority_queue 中元素的顺序不是按插入顺序排列的而是根据优先级排序。通常有两种类型的优先队列 最大优先队列优先级最高的元素位于队列顶部即最大值在最前面。 最小优先队列优先级最低的元素位于队列顶部即最小值在最前面。
以下是一些关于 priority_queue 的关键操作 插入元素将新元素插入到队列中优先级队列会自动调整元素的位置。 访问队首元素访问优先级最高的元素在最大优先队列中为最大值在最小优先队列中为最小值。 删除队首元素删除优先级最高的元素。 判断队列是否为空检查队列中是否有元素。
在 C 标准模板库STL中priority_queue 的使用非常常见以下是一个简单的代码示例
#include iostream
#include queueint main() {std::priority_queueint maxQueue; // 默认是最大优先队列// 插入元素maxQueue.push(10);maxQueue.push(30);maxQueue.push(20);maxQueue.push(5);// 输出并删除最大元素while (!maxQueue.empty()) {std::cout maxQueue.top() ;maxQueue.pop();}return 0;
}使用最小优先队列
在 C 中要创建最小优先队列可以使用以下方式
std::priority_queueint, std::vectorint, std::greaterint minQueue;使用场景 任务调度例如操作系统中的任务调度器根据任务的优先级调度执行任务。 路径查找如 Dijkstra 算法使用优先队列来找到最短路径。 事件驱动模拟在模拟系统中用来根据事件的优先级处理事件。
priority_queue 是一种非常高效的数据结构适合需要频繁处理优先级数据的场景。
int main()
{//优先级队列//优先级默认是大的优先级高//priority_queueint pq;//下面的就是小的优先级高了priority_queueint,vectorint,greaterint pq;//前面是数据的类型。后面是容器的类型pq.push(3);pq.push(2);pq.push(1);pq.push(4);while (!pq.empty())//不断取值直到栈为空{cout pq.top() ;pq.pop();//头删替换下个数据}return 0;
} priority_queue的模拟实现
#pragma once
#includevector//默认是vector进行适配的
//堆是将数组看成完全二叉树的
//假设p是父亲那么2*p1是左孩子2*p2是右孩子
//所以对于子节点的话-1然后/2就能算到父亲节点的下标了
namespace kai
{//仿函数
//对象可以像函数一样进行使用因为他重载了operator()template class Tstruct less{bool operator() (const T x, const T y)const{return x y;}};template class Tstruct greater//大堆大于的比较{bool operator() (const T x, const T y)const{return x y;}};//Compare是类型我们这里默认值是小堆templateclass T ,class ContainervectorT,class ComparelessT//优先级队列class priority_queue{public:priority_queue() default;//default是强制生成//我们不写默认构造的话那么就会调用对应类型的默认构造函数了templateclass InputIterator//构造函数priority_queue(InputIterator first, InputIterator last)//这里传的是迭代区间:_con(first,last)//直接用这个迭代区间进行初始化的操作{//进行建堆的操作/*在构建堆特别是最大堆或最小堆的过程中我们之所以从倒数第一个非叶子节点开始是因为叶子节点本身已经是一个有效的堆。下面是具体原因和背后的逻辑1. **叶子节点天然满足堆性质**堆的性质要求每个节点的值满足特定条件比如最大堆要求每个节点的值大于或等于其子节点的值最小堆要求每个节点的值小于或等于其子节点的值。叶子节点没有子节点自然满足堆的定义。所以我们无需对叶子节点进行任何调整。2. **从倒数第一个非叶子节点开始可以逐层调整堆**如果我们从倒数第一个非叶子节点开始进行“下沉”操作即调整该节点与其子节点的关系以满足堆的性质则可以逐步调整每一层节点从而最终得到一个完整的堆结构。这个过程叫做“自底向上”建堆从倒数的非叶子节点开始避免重复调整上层节点提高了构建效率。3. **提高构建效率**构建堆的时间复杂度是 \(O(n)\)而不是 \(O(n \log n)\)因为从倒数第一个非叶子节点开始向上调整比从根节点开始构建效率高得多。倒数的非叶子节点数量较少而且每个节点的调整次数随深度的增加而减少这种方式在平均情况下只需执行有限的调整操作。4. **构建过程的稳定性**自底向上从非叶子节点开始构建可以保证堆的结构稳定不会因为上层节点的调整而打乱下层已经满足堆性质的节点。这保证了最终得到的是一个合法的堆。因此从倒数第一个非叶子节点开始建堆是一种高效、合理的方式。*/for (int i (_con.size()-1-1)/2; i 0; i--){//这里的第一个-1是最后一个数的下标第二个-1配合外面的/2可以找到我们的父亲节点这个节点就是倒数第一个非叶子节点了我们从这个开始进行建堆的操作//我们从这个位置开始进行调整不断的调整到根节点//向下调整算法要求左右子树都是大堆的不然是无效的AdjustDown(i);}//我们从倒数第一个非叶子节点进行建堆的操作可以保证堆的结构正确}//向上调整算法void AdjustUp(int child){Compare com;int parent (child - 1) / 2;//算出父亲节点的下标位置while (child 0){//if (_con[parent]_con[child] )//父亲小于孩子实现大堆if (com( _con[parent],_con[child]))//利用com对象进行比较大小我们这里的默认传的是greater{//直接利用C中的swap函数进行交换就行了swap(_con[child], _con[parent]);//将父亲节点和子节点的值进行交换的操作child parent;//然后我们的孩子节点就跑到了父亲节点的位置了parent (parent - 1) / 2;//然后父亲节点的位置就跑到了当前父亲节点的父亲节点那里了}else{//如果调整的过程中孩子节点的值比父亲节点的值大了我们就直接跳出循环就行了不进行操作了break;} }}void push(const T x)//在堆中继续数据的插入的操作{//先插入x_con.push_back(x);//进行向上调整小堆AdjustUp(_con.size() - 1);//size-1就是最后一个数据的位置的下标然后我们利用向上调整算法进行调整的操作}void AdjustDown(int parent){Compare com;size_t child parent * 2 1;//通过给的父亲的位置算出左孩子的位置while (child_con.size()){//我们这里是小堆//假设选出左右孩子中小的那个孩子//if (child 1 _con.size() _con[child]_con[child 1] )//如果右孩子存在的话并且右孩子大于左孩子的话if (child 1 _con.size() com(_con[child],_con[child 1] ))//如果右孩子存在的话并且右孩子大于左孩子的话{child;//那么我们就将我们的孩子节点定位到右孩子的位置那里}if (com(_con[parent],_con[child] ))//如果当前孩子节点小于父亲节点的话{//我们就将小的节点往上面进行交换swap(_con[child], _con[parent]);parent child;//然后我们父亲节点就定位到当前的孩子节点了child parent * 2 1;//算出当前孩子节点的孩子节点}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);//交换堆顶数据和最后一个数据_con.pop_back();//然后将最后一个数据进行时删除的操作就行了//进行向下调整的操作从根位置开始向下进行调整的操作AdjustDown(0);}bool empty()//判空函数{return _con.empty();}const T top()//返回堆顶的数据{return _con[0];//就是返回根位置的数据就行了}size_t size(){return _con.size();}private:Container _con;//存放数据的容器};
}仿函数的介绍
//仿函数
//对象可以像函数一样进行使用因为他重载了operator()
template class T
struct Less
{bool operator() (const T x, const T y)const{return x y;}
};template class T
struct Greater
{bool operator() (const T x, const T y)const{return x y;}
};int main()
{Lessint lessFunc;cout lessFunc(1, 2) endl;cout lessFunc.operator()(1, 2) endl;return 0;
}仿函数Functor是一种在C和其他编程语言中使用的技术它使得对象可以像函数一样被调用。仿函数通常通过重载 operator() 操作符来实现使得一个对象可以像函数那样接受参数并返回结果。仿函数的主要优势在于它将函数的功能和状态封装到对象中使得函数调用更加灵活、模块化和可扩展。
仿函数的基本概念
在C中可以通过重载 operator() 操作符来定义一个仿函数使得一个对象可以像普通函数一样被调用。仿函数通常定义为一个类的成员函数允许该类的对象具备类似函数的行为。
仿函数的基本用法
下面是一个简单的仿函数示例通过重载 operator() 来实现一个加法仿函数
#include iostreamclass Adder {
public:int operator()(int a, int b) const {return a b;}
};int main() {Adder add;int result add(3, 4); // 对象像函数一样被调用std::cout Result: result std::endl; // 输出 Result: 7return 0;
}在这个例子中Adder 类重载了 operator() 操作符使得其对象 add 可以像一个函数一样通过 add(3, 4) 的形式来调用返回结果 7。
仿函数的优点 灵活性仿函数可以携带状态可以存储数据和维护状态适合需要保存计算状态的场景。 性能优化由于仿函数是类的一部分它们可以通过内联函数进行优化从而获得比普通函数指针更好的性能。 可定制性可以根据需求重载多个 operator()使得对象可以接收不同类型和数量的参数。 更符合面向对象设计仿函数可以使用类的其他成员和方法因此可以实现更复杂的操作和逻辑。
常见的仿函数应用 STL 算法配合使用标准库中的许多算法如 std::sort、std::for_each 等都可以接受仿函数作为参数。 Lambda表达式的替代在没有Lambda表达式的C版本中仿函数被广泛用于类似的场景。 策略模式在设计模式中仿函数常用于实现策略模式用于传递可定制的算法。
示例在STL中使用仿函数
#include iostream
#include vector
#include algorithmclass MultiplyBy {int factor;
public:MultiplyBy(int f) : factor(f) {}int operator()(int value) const {return value * factor;}
};int main() {std::vectorint values {1, 2, 3, 4, 5};std::transform(values.begin(), values.end(), values.begin(), MultiplyBy(3));for (int value : values) {std::cout value ; // 输出 3 6 9 12 15}return 0;
}在这个例子中我们定义了一个 MultiplyBy 仿函数类用于将每个元素乘以一个特定因子。然后使用 std::transform 将 MultiplyBy(3) 仿函数应用于容器中的每个元素。
总结
仿函数通过重载 operator() 来赋予对象函数的能力使得它们能够和函数指针、Lambda表达式等互相替代并发挥作用。在C编程中仿函数广泛应用于STL算法和其他需要灵活函数调用的场景。 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);private:int _year;int _month;int _day;
};
//声明和定义分离
ostream operator(ostream _cout, const Date d)
{_cout d._year - d._month - d._day;return _cout;
}struct DateLess
{bool operator() (const Date* d1, const Date* d2)//传过来的是两个指针我们希望的是两个指针指向的值进行比较{//我们直接进行解引用进行比较的操作return *d1 *d2;}
};int main()
{// 大堆需要用户在自定义类型中提供的重载kai::priority_queueDate*,vectorDate*,DateLess q1;//优先级队列q1.push(new Date{2024,10,23});q1.push(new Date{2024,5,27});q1.push(new Date{2024,11,7});while (!q1.empty())//不断取值直到栈为空{cout *q1.top() ;q1.pop();//头删替换下个数据}cout endl;return 0;return 0;
}
题目
155.最小栈
题目 class MinStack
{
public:MinStack(){}void push(int val){_st.push(val);//我们的st这个栈正常插入数据if(_minst.empty()||val_minst.top())//如果_minst这个栈为空的话或者传过来的val小于等于_minst栈顶的元素的话我们就将数据插入到minst中{//如果这个minst这个栈是空的话我们就进行数据的同步插入如果这个插入数据小于我们的minst栈顶的数据的话我们就进行最小元素的更新操作如果我们插入的元素等于我们的minst栈顶的元素的话就是等于我们当前minst这个栈栈顶的最小元素的话我们也是需要进行插入_minst.push(val);}}void pop(){if(_st.top()_minst.top()){//如果st这个栈和minst这个栈的栈顶元素都相等的话那么我们都需要进行删除操作的_minst.pop();}_st.pop();//st这个栈正常进行删除操作我们需要对minst这个栈进行一个判断操作如果当前两个栈的栈顶元素相同的话那么我们就进行minst这个栈的栈顶元素的删除操作}int top(){return _st.top();//返回我们的st这个栈的栈顶元素就行了}int getMin(){//获取最小值的话我们就将minst这个栈的栈顶元素进行返回就行了因为这个栈是进行插入元素中最小的元素的更新的return _minst.top();}
private:
//通过两个栈我们实现了找到最小元素的功能了
/*
如果我们的st存入5的话然后我们的minst记录当前的最小值存放栈中就是存放5
然后存入4那么st存入4minst也存入4更新最小值
然后我们st存放6那么我们的minst更新最小值还是4
然后我们放入1的话minst更新最小值那么就存入1了
如果我们要pop我们的st栈顶元素的话那么我们的minst同样更新最小值那么最小值就变成上一个最小值4了这个MinStack这个类我们是不需要写默认构造的编译器默认生成一个无参的构造
这里我们的自定义类型st和minst会自动调用自己的构造函数的我们是不需要显示写的
*/stackint _st;stackint _minst;
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj new MinStack();* obj-push(val);* obj-pop();* int param_3 obj-top();* int param_4 obj-getMin();*/通过两个栈我们实现了找到最小元素的功能了
如果我们的st存入5的话然后我们的minst记录当前的最小值存放栈中就是存放5
然后存入4那么st存入4minst也存入4更新最小值
然后我们st存放6那么我们的minst更新最小值还是4
然后我们放入1的话minst更新最小值那么就存入1了
如果我们要pop我们的st栈顶元素的话那么我们的minst同样更新最小值那么最小值就变成上一个最小值4了
在我们的st这个栈在插入的时候我们的minst不断进行最小元素的更新操作
但是如果我们想如果在st中插入的好几个数据都是重复的话那么我们的minst这个栈就显得很麻烦了
那么我们就可以将我们的minst这个栈改造下
我们可以在minst中对存入的数据进行最小值更新的同时并且进行计数的操作 JZ31 栈的压入、弹出序列
题目 1.先入栈pushi位置的数据 2.栈顶数据跟出栈popi序列位置数据比较如果匹配则出栈那么popi如果不匹配的话那么我们继续重复第一个操作
结束条件就是直到我们的栈是空的匹配完了
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pushV int整型vector * param popV int整型vector * return bool布尔型*/bool IsPopOrder(vectorint pushV, vectorint popV){size_t pushi0,popi0;stackintst;while(pushipushV.size()){//我们先往st这个栈中插入pushv中pushi指向的元素然后pushi进行加加操作st.push(pushV[pushi]);//这个是我们入的数据//入完数据之后我们进行一个比较的操作while(!st.empty()popV[popi]st.top()){//如果这个st这个栈不是空的并且我们的popv这个数组中i指向的元素和st中的元素是相等的话那么我们就进行出栈操作进了st之后又出就是这个意思popi;//换下一个数据进行比较st.pop();//删除当前栈的栈顶数据}}return st.empty();}
};
/*
两个数组
1 2 3 4 5 pushi
4 3 5 1 2 popi
我们先将1进行入栈然后与popi指向的元素进行比较不匹配我们继续进行入栈
入栈了2 3 4
到了4这里我们的pushi和篇popi指向的数据进行了匹配了
然后我们删除了当前的这个4这个元素我们将popi那么就指向了3
然后我们还是处于循环中我们判断的pushi和popi指向的数据是否匹配然后此时的栈顶元素是3匹配上了到了然后将3删除了
然后我们此时的栈顶元素是2但是我们的popi指向了5那么我们就出了循环继续进行入栈的操作了将最后的5入栈了。然后我们匹配上了将5进行删除了
然后我们在循环之中继续进行判断是否匹配我们的此时栈顶元素是2但是我们的popi指向的元素是1然后我们又出循环了然后我们进行入栈操作但是我们的pushi已经越界了那么就出了外循环了然后我们的循环就终止了然后我们判断我们的栈是不是空的如果是空的话那么我们就返回了true,如果不是空的话那么就返回false
*/如果是匹配的话那么最后栈的空间里面肯定是空的如果不匹配的话那么肯定是不匹配的
150. 逆波兰表达式求值
题目
class Solution {
public:int evalRPN(vectorstring tokens){stack ints;for(auto str:tokens){//如果是操作符的话if(str||-str||*str||/str){//如果遇到操作符的话我们就从栈里面拿出两个数字进行操作符的运算操作//我们先拿出来的是右操作符然后是左操作符int rights.top();//拿完一个元素之后我们删除这个栈顶元素换新的元素当栈顶元素s.pop();int lefts.top();s.pop();switch(str[0]){case :s.push(leftright);break;case -:s.push(left-right);break;case *:s.push(left*right);break;case /:s.push(left/right);break;}}else//如果是操作数的话{s.push(stoi(str));//stoi的作用是将字符串转换为整型然后放到栈里面去}}return s.top();//最后保存的就是我们的结果}
};232. 用栈实现队列
题目
class MyQueue
{
private:stackint stackIn;stackint stackOut;//辅助函数将所有元素从stackIn移动到stackOutvoid move(){while(!stackIn.empty())//In这个栈不是空的那么就进行循环操作{stackOut.push(stackIn.top());stackIn.pop();}}public:MyQueue()//构造函数不写{}//将元素x推入队列的末尾 ,这里我们的新元素入栈到in栈里面void push(int x){stackIn.push(x);}//移除队列的开头元素并返回队列开头元素int pop(){if(stackOut.empty())//如果out这个栈为看空的话那么我们就将in栈的元素全部移动到out的栈里面{move();//直接利用我们上面写的辅助函数进行操作就行了}int resultstackOut.top();stackOut.pop();return result;//返回out栈的栈顶元素}//返回队列开头的元素int peek(){if(stackOut.empty())//如果out栈是空的话那么我们将in的元素全部移动到out的栈{move();}return stackOut.top();}//如果队列是空的返回true否则返回falsebool empty()//两个栈都是空的话那么这个队列就是空的{return stackIn.empty()stackOut.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj new MyQueue();* obj-push(x);* int param_2 obj-pop();* int param_3 obj-peek();* bool param_4 obj-empty();*/225. 用队列实现栈
题目 class MyStack
{
private:queueint queue1;queueint queue2;public:MyStack(){}//压入元素到栈顶后入先出void push(int x){queue2.push(x);//先将元素插入到队列2中while(!queue1.empty())//只要队列1中有数据就进行循环操作{queue2.push(queue1.front());queue1.pop();}//将两个队列进行交换的操作swap(queue1,queue2);}// 移除栈顶元素,栈顶元素在 queue1 的队首因此直接 pop 并返回该元素。int pop(){int topmentqueue1.front();queue1.pop();return topment;}int top(){return queue1.front();}bool empty(){return queue1.empty();}
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj new MyStack();* obj-push(x);* int param_2 obj-pop();* int param_3 obj-top();* bool param_4 obj-empty();*/
