扩展栈O(1)求取最小值：
（0）问题描述：
（1）分析：
（2）步骤：
（3）代码实现：
------------------------
（0）问题描述：
扩展stack的实现，完成正常的push，pop操作，新增访问最小（或最大）元素的接口Min（），使得push，pop，Min的时间复杂度都是O(1)。
（1）方法一：
（1.1）分析：
在栈的每个元素加一个属性值minIndex,(记录下当前位置及其它下面的最小元素的索引,使用索引不使用元素类型是为了节省空间)；
元素的值用value表示；
进栈push,当压入的元素的value小于当前栈顶的stackArray[minIndex]时，将新压入元素的minIndex设置为top+1；否则，将新压入元素的minIndex字段，设置为当前栈顶的元素的
minIndex；
出栈则和以前一样；
（2）代码实现：
#include <iostream>
using namespace std;
typedef int ElemType;
class newElemType{
public:
ElemType value;
int minIndex;
newElemType(ElemType elem){
value=elem;
}
newElemType(){}
};
class minStack{
public:
newElemType * stackArray;
int maxSize;
int top;
public:
/*constructor*/
minStack(int size){
maxSize=size;
stackArray=new newElemType[maxSize];
top=-1;
}
/*destructor*/
~minStack(){
delete []stackArray;
stackArray=NULL;
top=-1;
}
bool isFull(){
if(maxSize-1==top)
return true;
return false;
}
bool isEmpty(){
if(-1==top)
return true;
return false;
}
/*push to stack*/
bool push(ElemType elem){
if(isFull()) return false;
newElemType newElem(elem);
if(isEmpty()) /* 栈为空时，最小的就是自己的索引，即0；*/
{
top++;
newElem.minIndex=top;
}
else{
top++;
int index=stackArray[top-1].minIndex;
/*未进栈前最小的索引*/
if(elem<stackArray[index].value){
newElem.minIndex=top;
}else {
newElem.minIndex=index;
}
}
stackArray[top]=newElem;
return true;
}
/*pop from stack*/
bool pop(ElemType & elem){
if(isEmpty()) return false;
elem=stackArray[top].value;
top--;
return true;
}
bool getTop(ElemType & elem){
if(isEmpty()) return false;
elem=stackArray[top].value;
return true;
}
bool getMin(ElemType & minElem){
if(isEmpty()) return false;
int index=stackArray[top].minIndex;
minElem=stackArray[index].value;
return true;
}
};
int main()
{
minStack stack(10);
stack.push(2);
stack.push(5);
stack.push(3);
stack.push(6);
stack.push(4);
ElemType topElem,minElem;
stack.getTop(topElem);
stack.getMin(minElem);
cout<<"top elem is : "<<topElem<<endl<<"min elem is: "<<minElem<<endl;
stack.push(1);
stack.push(7);
stack.getTop(topElem);
stack.getMin(minElem);
cout<<"top elem is : "<<topElem<<endl<<"min elem is: "<<minElem<<endl;
cout << "Hello world!" << endl;
return 0;
}
--------------------------------
以下代码每个元素中添加的不是索引值，而是直接存储当前元素及其以下的最小值。
/*代码实现二*/
#include <iostream>
using namespace std;
typedef int ElemType;
class newElemType{
public:
ElemType value;
ElemType min;
newElemType(ElemType elem){
value=elem;
}/*构造函数*/
newElemType(){}
/*重载构造*/
};
class minStack{
public:
newElemType * stackArray;
int maxSize;
int top;
public:
/*constructor*/
minStack(int size){
maxSize=size;
stackArray=new newElemType[maxSize];
top=-1;
}
/*destructor*/
~minStack(){
delete []stackArray;
stackArray=NULL;
top=-1;
}
bool isFull(){
if(maxSize-1==top)
return true;
return false;
}
bool isEmpty(){
if(-1==top)
return true;
return false;
}
/*push to stack*/
bool push(ElemType elem){
if(isFull()) return false;
newElemType newElem(elem);
/*栈为空时，则新元素的min=value；
栈非空时，则新元素的value与栈顶元素的value比较，取较小者*/
newElem.min=(isEmpty())?elem: stackArray[top].min;
/*新元素的min取的是value(栈空时)或者进栈前栈顶的min*/
if(elem<newElem.min){
newElem.min=elem;
}
top++;
stackArray[top]=newElem;/*进栈*/
return true;
}
/*pop from stack*/
bool pop(ElemType & elem){
if(isEmpty()) return false;
elem=stackArray[top].value;
top--;
return true;
}
bool getTop(ElemType & elem){
if(isEmpty()) return false;
elem=stackArray[top].value;
return true;
}
bool getMin(ElemType & minElem){
if(isEmpty()) return false;
minElem=stackArray[top].min;
return true;
}
};
int main()
{
minStack stack(10);
stack.push(2);
stack.push(5);
stack.push(3);
stack.push(6);
stack.push(4);
ElemType topElem,minElem;
stack.getTop(topElem);
stack.getMin(minElem);
cout<<"top elem is : "<<topElem<<endl<<"min elem is: "<<minElem<<endl;
stack.push(1);
stack.push(7);
stack.getTop(topElem);
stack.getMin(minElem);
cout<<"top elem is : "<<topElem<<endl<<"min elem is: "<<minElem<<endl;
cout << "Hello world!" << endl;
return 0;
}