题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的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 ;
}

运行截图:

剑指offer-面试题21.包含min函数的栈-LMLPHP

04-25 12:24