wordpress 增加文章字段,seo引擎优化工具,重庆建网站价格,flash网站建设公司最小栈 最小栈#xff08;Min Stack#xff09;是一个支持常数时间复杂度获取栈中最小元素的特殊栈数据结构。通常#xff0c;标准的栈数据结构只支持在常数时间内执行入栈#xff08;push#xff09;和出栈#xff08;pop#xff09;操作#xff0c;但无法在常数时间内…最小栈 最小栈Min Stack是一个支持常数时间复杂度获取栈中最小元素的特殊栈数据结构。通常标准的栈数据结构只支持在常数时间内执行入栈push和出栈pop操作但无法在常数时间内获取栈中的最小元素。 最小栈通过在每个栈节点中额外存储一个当前阶段的最小值从而实现在常数时间内获取最小元素的功能。这意味着无论栈的大小如何都可以在常数时间内获取栈中的最小值。
最小栈的主要操作包括 入栈push将元素压入栈顶并更新当前最小值。 出栈pop从栈顶弹出一个元素。 获取最小值getMin返回栈中的最小元素即栈顶节点的最小值。 这样在使用最小栈时我们可以通过调用 getMin 操作来获取栈中的最小元素并保持常数时间复杂度。其他与标准栈一致的操作例如入栈和出栈仍然可以在常数时间内执行。 使用最小栈的一个常见场景是需要快速获取栈中的最小元素的问题例如实现一个获取最小元素的栈MinStack或解决一些需要以常数时间获取最小值的算法问题。
栈结构 代码实现
#include iostream
#ifndef TEST_MIN_STACK_H
#define TEST_MIN_STACK_H
using namespace std;
class StackNode{public:int val;StackNode * next;StackNode(int v):val(v),next(nullptr){}
};
class MinStack {
public:MinStack() {}void push(int val) {// 将元素压入栈StackNode* n;data nullptr ? (data new StackNode(val)) nullptr : (n new StackNode(val)) (n-next data) (data n);// 更新最小值栈if (minData nullptr) {minData new StackNode(val);}else if(val minData-val){StackNode* n new StackNode(val);n-next minData;minData n;}}void pop() {if (data ! nullptr) {// 取出栈顶元素int top data-val;// 如果栈顶元素是最小值同时从最小值栈中弹出if (minData ! nullptr top minData-val) {StackNode* t minData;minData minData-next;delete t;}// 弹出栈顶元素StackNode* t data;data data-next;delete t;}}int top() {// if (data ! nullptr) {// // 返回栈顶元素// return data-val;// }// // 当栈为空时返回一个无意义的值// return INT_MIN;return data nullptr ? INT_MIN : data-val;}int getMin() {//if (minData ! nullptr) {// 返回最小值栈的栈顶元素// return minData-val;// }// 当栈为空时返回一个无意义的值// return INT_MIN;return minData nullptr ? INT_MIN : minData-val;}private:StackNode *data nullptr;StackNode *minData nullptr;
};#endif //TEST_MIN_STACK_H实现分析
MinStack 类中有两个私有成员变量 data 和 minData分别表示存储栈元素的栈和存储最小值的栈。这两个栈都是通过 StackNode 类的节点构成的。
下面是对 MinStack 类的各个方法进行分析 void push(int val)将元素压入栈。该方法首先判断 data 是否为空如果为空则创建一个新的节点作为栈顶并将 data 指向该节点如果不为空创建一个新节点并将其指向当前的栈顶节点然后将 data 指向新的节点。接着该方法更新最小值栈 minData。如果 minData 为空直接创建一个新节点作为最小值栈的栈顶如果不为空并且当前值小于等于最小值栈的栈顶元素创建一个新节点并将其指向最小值栈的栈顶节点然后将 minData 指向新的节点。 图解: StackNode* n new StackNode(val); n-next data; data n; void pop()弹出栈顶元素。首先判断 data 是否为空如果为空则直接返回。如果 data 不为空则取出栈顶元素 top。如果 minData 不为空且栈顶元素 top 等于最小值栈的栈顶元素则将最小值栈的栈顶元素弹出。接着将栈顶元素弹出并释放内存。 int top()返回栈顶元素的值。如果 data 为空返回 INT_MIN否则返回栈顶节点的值。 int getMin()返回最小值栈的栈顶元素的值。如果 minData 为空返回 INT_MIN否则返回最小值栈的栈顶节点的值。 总体而言该代码实现了一个基本的最小栈支持在常数时间内进行入栈、出栈、获取栈顶元素和获取最小值的操作。 其他实现方式 使用stackvector或deque实现MinStack。把其中的data和minData属性换成对应的容器对象即可。
