算法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]圖的深度優先遍歷