题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。
在该栈中，调用min,push及pop的时间复杂度都是O(1).
这一题实际上需要一个辅助栈存储最小值:
1.在模板类定义两个栈类型私有成员变量,一个为保存数据的栈另外一个为保存最小值的栈
2.当栈为空的时候直接将数据同时压入数据栈和最小值栈
3.当栈不为空的时候，将数据先压入数据栈同时比较该数据和最小值栈栈顶元素的大小
若大于最小值栈栈顶元素，则向最小值栈压入其栈顶元素，否则压入该数据到最小值栈
栈顶
4.当我们使用方法的时候直接取最小值的栈顶即为栈中的最小值
5.当我们要pop栈的时候应同时pop最小值栈的栈顶元素
代码实现如下:
MinStack.h
#ifndef _MINSTACK_H
#define _MINSTACK_H #include <stack>
using namespace std; template <typename T>
class StackWithMin
{
public:
void push(T data);
void pop();
T min();
private:
stack<T> DataStack;
stack<T> MinStack;
}; template <typename T> void StackWithMin<T>::push(T data)
{
DataStack.push(data);
if(MinStack.empty())
{
MinStack.push(data);
}
else
{
if(data>=MinStack.top())
{
MinStack.push(MinStack.top());
}
else
{
MinStack.push(data);
}
}
} template <typename T> void StackWithMin<T>::pop()
{
MinStack.pop();
DataStack.pop();
} template <typename T> T StackWithMin<T>::min()
{
if(!DataStack.empty())
{
return MinStack.top();
}
else
{
cout<<"不好意思栈空!"<<endl;
}
} #endif
测试函数：
#include "MinStack.h"
#include <iostream>
using namespace std; int main()
{
StackWithMin<int> MinStack;
cout<<"请输入依次压入栈的数据(0-exit): "<<endl;
int data;
while(data!=)
{
cin>>data;
if(data!=)
MinStack.push(data);
}
cout<<endl;
cout<<"栈的最小值为: "<<MinStack.min()<<endl;; return ;
}
运行截图: