微软口试100题

微软面试100题

2.设计包含min函数的栈（栈）

定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。

要求函数min、push以及pop的时间复杂度都是O(1)。package cn.emma.interview_2;

public class Stack {public final static int MAX = 100;private static int top;private static int[] S = new int[MAX];static int min;private static Stack minStack = new Stack();public boolean emptyStack(){if(top == 0){return true;}return false;}public static void push(int x){if(top == 0){min =x;}else{min = (S[min] > x) ? ++top:min;}minStack.push(min);S[top] = x;}public static int pop(){minStack.pop();return S[--top];}public static int minElement(){return minStack.S[minStack.top];}public static int getMin(){return min;}public static void main(String[] args) {push(0);push(-1);push(2);push(-9);push(10);System.out.println(pop() + "\t" + pop() + "\t" + pop());System.out.println(minElement());}}