题目出处:
http://zhedahht.blog.163.com/blog/static/25411174200712895228171/题目：定义栈的数据结构，要求添加一个min
函数，能够得到栈的最小元素。要求函数min
、push
以及pop
的时间复杂度都是O(1)
。
#include "StackWithMin.h"
#include<cstdio>
#include<cstdlib>
#include<cstring>
const int StackWithMin::MAX_SIZE ;
StackWithMin::StackWithMin() :
top_index(-1), min_index(-1)
{
printf("StackWithMin Constructor\n");
}
StackWithMin::~StackWithMin()
{
printf("StackWithMin Destructor\n");
}
int
StackWithMin::top() const
{
if(top_index == -1) {
printf("top() failed: Stack Empty\n");
return -1;
}
return stack[top_index];
}
int
StackWithMin::get_min() const
{
if(min_index == -1) {
printf("get_min() failed: Stack Empty\n");
return -1;
}
return stack[min_index];
}
void
StackWithMin::push(int value)
{
if(top_index == -1) { /* stack empty */
stack[++top_index] = value;
min_index = top_index;
return;
}
stack[++top_index] = value;
if(value < stack[min_index]) {
index[top_index] = min_index;
min_index = top_index;
}
}
int
StackWithMin::pop()
{
if(top_index == -1) {
printf("pop() failed: Stack Empty\n");
return -1;
}
int ret = stack[top_index];
if(min_index == top_index)
min_index = index[top_index];
--top_index;
return ret;
}
class StackWithMin
{
public:
StackWithMin();
~StackWithMin();
int get_min() const;
int top() const;
void push(int value);
int pop();
private:
static const int MAX_SIZE = 101;
int top_index, min_index;
int stack[MAX_SIZE];
int index[MAX_SIZE];
};