这道笔试题再发帖，麻烦哪位大侠给出完整答案!!

Question

 1）用int数组实现栈，实现pop(),push()方法，并且当栈空间满时，栈的空间增加一倍。 
 2）在1)的基础之上，增加一个getMax()方法，返回栈中的最大值，要求这个函数具有O（1）的时间复杂度（注释：O(1)复杂度说白了就是以空间换时间！）

Answer 1

你可以查一下String的源代码，看一下数组的动态增长是怎么写的，你的问题就这个技术点需要解决。

Answer 2

public Stack(int s){
maxSize=s;
stackArray=new char[maxSize];
top=-1;
}

public void push(char j){
                if(top==maxSize)
                   stackArray=new char[2*maxSize];
stackArray[++top]=j;
}

public char pop(){
return stackArray[top--];
}
          
        

Answer 3

import java.util.*;
public class IntStack
{
private int size;
private int[] elements;
private int top = -1; public IntStack(int size)
{
if (size < 0 ) throw new NegativeArraySizeException();
this.size = size;
elements = new int[size];
} public void push(int value)
{
if (++top >= size)
{
size *= 2;
int[] oldData = elements;
elements = Arrays.copyOf(oldData, size);
}
elements[top] = value;
} public int pop()
{
if (top < 0) throw new IndexOutOfBoundsException(); return elements[top--];
}
}
O(1）的方法我没想到怎么实现比较好

Answer 4

import java.util.*;class StackEmptyException extends RuntimeException{};
class NegativeStackSizeException extends RuntimeException{};public class IntStack
{
private int size;
private int[] elements;
private TreeMap<Integer,Integer> values = new TreeMap<Integer,Integer>();
private int top = -1; public IntStack(int size)
{
if (size < 0 ) throw new NegativeArraySizeException();
this.size = size;
elements = new int[size];
} public void push(int value)
{
if (++top >= size)
{
size *= 2;
int[] oldData = elements;
elements = Arrays.copyOf(oldData, size);
}
Integer freq = values.get(value);
freq = ( freq == null) ? 1 : freq + 1;
values.put(value, freq);
elements[top] = value;
} public int pop()
{
if (top < 0) throw new StackEmptyException();
int result = elements[top--];
int freq = values.get(result);
if (freq == 1) values.remove(result);
else values.put(result,freq - 1);
return result;
} public int getMax()
{
if (values.isEmpty()) throw new StackEmptyException();
return values.lastKey();
}
}