算法7：设计一个class，类似于stack, 但可以是O(1)时间内返回min()

2019-11-06 06:09:48

字体：大中小

来源：转载

供稿：网友

解题思路

类中存一个数据栈和一个辅助栈，向数据栈push的时候，判断当前值与辅助栈栈顶的值的大小，如果小则push到辅助栈，否则push辅助栈的栈顶数值到辅助栈；向数据栈pop时，同时pop辅助栈的值。获取当前数值最小值即辅助栈栈顶数据，时间复杂度为O(1)

MinStack类定义

#include <stack>using namespace std;class MinStack{public: MinStack(); ~MinStack(); //栈的push操作 void Push(int value); //栈的pop操作 int Pop(); //获取最小值操作 int Min(); //判断栈是否为空 bool IsEmpty();PRivate: stack<int> dataStack; stack<int> minStack;};

MinStack类实现

#include "stdafx.h"#include "MinStack.h"#include <iostream>using namespace std;MinStack::MinStack(){}MinStack::~MinStack(){}void MinStack::Push(int data){ dataStack.push(data); //向minStack push当前最小值 if(minStack.empty() || data < minStack.top()) { minStack.push(data); } else { minStack.push(minStack.top()); }}int MinStack::Pop(){ if(IsEmpty()) { cout<<"stack is empty,can't pop"<<endl; return -1; } //获取栈顶数据 int data = dataStack.top(); dataStack.pop(); minStack.pop(); return data;}bool MinStack::IsEmpty(){ if(dataStack.empty()) { return true; } return false;}int MinStack::Min(){ if(minStack.empty()) { cout<<"min stack is empty"<<endl; return -1; } return minStack.top();}

测试代码

#include "stdafx.h"#include "MinStack.h"#include <iostream>using namespace std;int _tmain(int argc, _TCHAR* argv[]){ cout<<"please input minStack"<<endl; MinStack minStack; int data = 0; for(int i = 0; i < 8; i++) { cin>>data; minStack.Push(data); cout<<"min data is "<<minStack.Min()<<endl; } minStack.Pop(); cout<<"after pop one data, the min data is "<<minStack.Min()<<endl; minStack.Pop(); cout<<"after pop one data, the min data is "<<minStack.Min()<<endl; minStack.Pop(); cout<<"after pop one data, the min data is "<<minStack.Min()<<endl; return 0;}

上一篇：算典04_例题_02_UVA-489

下一篇：[Aha]图的深度优先遍历

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注