Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
题目的意思是实现一个栈，能够实现推入，推出，返回顶端元素，获得最小元素的功能
public class MinClass {
private Stack<Integer> a = new Stack<Integer>() ;
private Stack<Integer> minStack = new Stack<Integer>();
public void push(int x) {
/**
* 判断最小栈，如果栈为空或者压入的栈值小于栈顶元素，将x压入最小栈
*/
if(minStack.isEmpty() || x<minStack.peek()){
minStack.push(x);
}
a.push(x);
}
public void pop() {
/**
* 如果不相等，会把minStack中保存的最小值给推出。所以必须保证minStack中推出
* 的值必须和a中的值一样
*/
if(minStack.peek().equals(a.peek())){
minStack.pop();
}
a.pop();
}
public int top() {
return a.peek();
}
public int getMin() {
return minStack.peek();
}
/**
* 测试
*/
public static void main(){
MinClass obj = new MinClass();
obj.push(10);
obj.push(20);
obj.pop();
obj.push(30);
System.out.println(obj.getMin());
}
}
拓 展
图片来自于维基
堆栈（英语：stack），也可直接称栈 由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。栈空间有操作系统自动分配，使用完成后有编译器自动释放，通常用来存放函数的参数值、局部变量的值等。
栈使用的是靠近ALU的一级缓存，他们通常是在调用时处于存储空间中，调用完毕后就会立即释放。与“堆（Heap）"不同,堆内存有程序员释放那个，存放于二级缓存中，结构类似于链表，程序员分配时内存变量的值不一定是连续的，因此，堆处理的速度相比与栈来说速度要慢一些！
（截图来自 计算机系统概论）
如图所示，a)有5个连续的存储空间，每个存储单元为1个字节（这也是目前操作系统内存结构的排列方式，类似于一个大的字节数组）。R6代表栈顶寄存器，用来存储栈顶元素的指针。b）当往栈中push一个元素18以后，栈顶元素指针加1，其他地址不变。c）往栈中压入3个元素后的结果，可以看到不断修改栈顶指针的大小。d）弹出2个元素的结果
下面我们用Java代码实现栈，前文已经说明，实现栈的方式可以有数组，也可以有链表来实现（因为这两个数据结构都是线性结构）
Java的SDK中封装好的有一个Stack,他的常用方法有
empty()
peek()
pop()
push(E item)
/**
* 栈的数组实现方式
* @author CYW
*/
public class ArrayStack {
private long[] stackArray;//数组
private int stackSize;//记录存储记录的最大的条数
private int top = -1;//记录栈顶位置 // 记录分配存储空间的大小
public ArrayStack(int s){
stackArray = new long[s];
top = -1;
stackSize = s;
} public long pop(){
return stackArray[top--];
} public void push(int x){
stackArray[++top] = x;
} public long peek(){
return stackArray[top];
} public boolean isEmpty(){
return (stackArray.length == 0);
} // 测试
public static void main(){
ArrayStack obj = new ArrayStack(100);
obj.push(100);
obj.push(20);
obj.push(10);
obj.push(200);
obj.push(1000);
obj.pop();
/**
*
*/
for (int i = 0;i<obj.top;i++){
System.out.println(obj.stackArray[i]);
}
}
}
需要注意的一点是：我们在输出数组元素的时候不能根据数组的长度来判断，而必须根据站顶的top来判断！
C++代码
struct Node{
struct Node* pPre;
int data;
};
class ListStack{
private:
//定义指向栈顶元素的指针
struct Node *top;
public:
void push(int data){
//创建新的变量
struct Node *node = new struct Node();
node->data = data;
node->pPre = top;
//重新定义top的指向
top = node;
}
int pop(){
//重新定义top的指向
int temp = top->data;
top =top->pPre;
//返回输出结果
return temp;
}
int peek(){
return top->data;
}
//判断是否为空
bool isEmpty(){
if(top){
return true;
}else{
return false;
}
}
};
int _tmain(int argc, _TCHAR* argv[])
{
ListStack stack;
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
stack.push(50);
cout<<stack.pop()<<endl;
cout<<stack.peek()<<endl;
cout<<stack.pop()<<endl;
cout<<stack.pop()<<endl;
cout<<stack.pop()<<endl;
cout<<stack.peek()<<endl;
cout<<stack.pop()<<endl;
if(stack.isEmpty()){
cout<<"栈中数据为空!"<<endl;
}else{
stack.pop();
}
return 0;
}
当然，上面代码中有很多不安全的地方，仅仅是学习的目的，http://shmilyaw-hotmail-com.iteye.com/blog/1825171 从Java给出了比较好的解释。