微软等数据结构与算法面试100题 第二题
第二题
题目： 要求设计一个栈，栈包含min函数的功能，即能够在O(1)的时间内做min， pop， push运算。
分析：
因为传统的栈只有push和pop功能，push和pop功能都是在O（1）的时间内做操作，题目要求具有min函数的功能，也就是在pop操作和push操作以后可以
在O（1）的时间内给出最小值的功能。因为如果是直接增加min函数，那么每次计算最小值的时候都是O(N)的时间，为了要达到O（1）的时间，因此需要一个
数组来存储这一动态变化过程，min_array中min_array[k]存储前K个数字里面最小值。
代码：
[cpp]
#include<iostream>
using namespace std;
template <class T>
class Stack{
private:
int size;
T * data;
int top;
T * min_data;
T min_value;
public:
Stack(int size = 100);
~Stack();
T pop();
//为什么要去地址呢
void push(const T item);
void print(){cout<<min_value<<endl;}
};
template<class T>
Stack<T>::Stack(int size){
data = new T [size];
min_data = new T [size];
this->top = -1;
}
template<class T>
Stack<T>::~Stack()
{
delete []data;
delete []min_data;
}
template<class T>
void Stack<T>::push(const T item)
{
if(top==size-1){
cout<<"堆栈溢出"<<endl;
//return;
}
top ++;
data[top]=item;
if(top==0)
{
min_data[top] = item;
min_value = item;
}
else
{
if(item < min_data[top-1])
{
min_data[top] = item;
min_value = item;
}
else
{
min_data[top] = min_data[top-1];
this->min_value = min_data[top-1];
}
}
}
template<class T>
T Stack<T>::pop()
{
if(top==-1)
{
cout<<"堆栈空"<<endl;
return -1;
}
T DATA_POP = data[top];
min_value = min_data[top-1];
top = top -1;
return DATA_POP;
}
int main(){
int stack_size = 100;
Stack<int> a_value(stack_size);
// test
a_value.push(10);
a_value.print();
a_value.push(2);
a_value.print();
a_value.push(3);
a_value.print();
a_value.push(1);
a_value.print();
a_value.push(5);
a_value.print();
cout<<"sc"<<endl;
a_value.pop();
a_value.print();
a_value.pop();
a_value.print();
return 0;
}
补充：软件开发 , C++ ,
