一道笔试题，麻烦大家看哈！

Question

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

Answer 1

http://topic.csdn.net/u/20090612/10/c1df5a00-ed6d-4c25-9b62-1b6507a55f7c.html
/*自己定义的栈，为了可以自由的访问栈中的元素。
 * */
class MyStack{
    String[]  st=new String[10];
    int top=0;
    void push(String vex){
        if(top==st.length-1){      //栈满时，给栈扩容
            String[] st1=new String[st.length+10];
            System.arraycopy(st, 0, st1, 0, st.length-1);
            st=st1;
        }
        st[top++]=vex;
    }
    boolean isEmpty() {
        if(top==0) return true;
        return false;
    }
    String pop(){
        if(top==0){
            return null;
        }else{
            return st[--top];    
        }
    }
    public String toString(){
        String s="";
        for(int i=0;i<top;i++){
            s=s+st[i]+" ";
        }
        return s;
    }
}只是给个例子,给整型栈扩容不能用上面的办法.getMax()这个太简单了

Answer 2

看错了,以为getMax()是返回栈的最大容量.如果是返回栈内元素的最大植,这个不太好弄.我能不能牺牲pop和push的效率来使getMax()为O(1)?

Answer 3

如果只有int数组来实现，求最大值的时候要O(1)，不知道怎么做。但如果栈的每个结点可以自己定义一个类，那么就容易多了，使用栈，然后再加上一个排序链就可以达到O(1)的要求，可以参考PriorityQueue的实现：出队是按优先级出队，但是队的排列还是按入队顺序。

Answer 4

连接的插入与删除复杂度是O(1), 不会扫描整个链的。参考PriorityQueue实现就明白了。

Answer 5

这题,我在回家的路上好好想了想,能想到的只有以下两个办法了:
第一种：加一属性max，就保存最大值。这样，在push()时，把入栈的元素与max比较一下，再入栈就行了。pop时，只要出栈元素不等于max，就出栈。如果出栈元素等于max，那就遍历除栈顶外的其它元素，找出最大值，再出栈。这时的时间复杂度为O（n）,好在栈是一个整形栈，速度是可以保证的。我记得有的书叫pop为弹栈，嗯，在弹之前是应该憋一会儿，这样弹出去有劲。getMax()直接返回max的值，绝对的O（1）。第二种:加一整数数组indexes，大小和栈一样大（栈扩容时，这个数组也要扩），这个数组保存栈中元素在栈中的下标，相当指针了。可以把indexes组织为一个有序表，堆，优胜者树。
优胜者树的维护代价最低。目的就是找出最大元素，最大元素如果出栈了，可以非常快的找到新的最大元素。代价是每一次的pop和push都要维护这种结构。getMax()也绝对是O（1）.这两种方法那一种的综合效率最高，没有研究。个人感觉第一种好。

Answer 6

就是优先级队列，按照一定的优先级出队（可以按元素最高的先出队）
队列中的元素要实现Comparable接口，这样队列中的元素有可比性

Answer 7

public class MyStack {
private Pear[] data;
private int count;
public MyStack(int init)
{
count=0;
data=new Pear[init];
}

public void ensureCapacity(int min)
{
Pear biggerArray[];
if(data.length<min)
{
biggerArray=new Pear[min];
System.arraycopy(data,0,biggerArray,0,count);
data=biggerArray;
}
}

public Pear peek()
{
if(count==0)
throw new EmptyStackException();
return data[count-1];
}
public Pear pop()
{
Pear p;
if(count==0)
throw new EmptyStackException();
p=data[--count];
data[count]=null;
return p; 
}

public void push(Pear p)
{
if(count==data.length)
{
ensureCapacity(count*2+1);
}
data[count]=p;
count++;
}
public int size()
{
return count;
}

public void trimToSize()
{
Pear trimmedArray[];
if(data.length!=count)
{
trimmedArray=new Pear[count];
System.arraycopy(data,0 ,trimmedArray, 0, count);
data=trimmedArray;
}
}
}

Answer 8

跟阿里的题目好像啊～我就写了getmax的，扩容的没什么算法，就没写#include <iostream>
using namespace std;
#define MAXSIZE 100class Stack
{
public:
Stack():size(0)
{
           memset(data,0,sizeof(data));
   memset(data,0,sizeof(tag));
}
   unsigned int size;
   int data[MAXSIZE];
   int tag[MAXSIZE+1];
   void push(int element)
   {
   if(size==MAXSIZE-1)
   return;
   tag[size+1]=element>tag[size]?element:tag[size];
   data[size++]=element;
   }
   int pop()
   {
   int element=data[size--];
   return element;
   }
   int getmax()
   {
   return tag[size];
   }
};

Answer 9

插入时做个处理，保存最大值，GetMax()的时间复杂度就是O(1)

Answer 10

sec_max不就是第二大吗?那得找出来才行啊.

Answer 11

照样地，每次push和pop时都可以确定最大和第二大的呀。

Answer 12

push 的时候记录最大值 保存起来 以备不时之需……

Answer 13

public class MyStack {
    private Pear[] data;
    private int count;
    public MyStack(int init)
    {
        count=0;
        data=new Pear[init];
    }
    
    public void ensureCapacity(int min)
    {
        Pear biggerArray[];
        if(data.length<min)
        {
            biggerArray=new Pear[min];
            System.arraycopy(data,0,biggerArray,0,count);
            data=biggerArray;
        }
    }
    
    public Pear peek()
    {
        if(count==0)
            throw new EmptyStackException();
        return data[count-1];
    }
    public Pear pop()
    {
        Pear p;
        if(count==0)
            throw new EmptyStackException();
        p=data[--count];
        data[count]=null;
        return p; 
    }
    
    public void push(Pear p)
    {
        if(count==data.length)
        {
            ensureCapacity(count*2+1);
        }
        data[count]=p;
        count++;
    }
    public int size()
    {
        return count;
    }
    
    public void trimToSize()
    {
        Pear trimmedArray[];
        if(data.length!=count)
        {
            trimmedArray=new Pear[count];
            System.arraycopy(data,0 ,trimmedArray, 0, count);
            data=trimmedArray;
        }
    }
}
O(∩_∩)O哈哈~加油吧

Answer 14

楼上几个代码，怎么看都像是jdk的代码。呵呵！

Answer 15

学习的时候貌似老师讲过这道题，
思路没那么复杂，
一个数组，首次大小定义为10.
堆栈是后进先出的原则，所以需要定义一个变量作为游标，首次为0。
push（），
判断游标是否等于数组。length-1，
等于就做个方法，
newArray（）
int[] new = new int[old.length*2].
将old中值传入new。存入数，注意类型转换，游标+1.pop（）
array[游标]=null；
游标-1；
2）；
O(1),是不是说1次循环？忘记什么意思了。
若是，
实际上是排序算法
先排序之后取最大值，用快速排序算法。
两个游标，一个开头，一个结尾，
开头从0-array。length-1.
结尾从array。length-1到0.
array[开头]>array[结尾]
互换。
程序设计来讲，一般不赞成这样做，
作为通用来讲，应该再加一个数组，与存数据的数组一样大，但它的操作像链表一样，
存储的是另外一个数组中大小顺序。
这样不光最大值，最小值什么的都可以很快找出。
一般人可能认为只要一个属性就可以了，当新存的值比以前的大就替换一下，但是，如果执行了pop（）呢，就需要重新计算。
如果只是加属性，每次pop和push都需要重新计算一遍，
而加一个数组来讲，并不是每次都需要计算。
对于一下存入多个值或者pop多个值，那么效率对比就会明显了。现在不建议大家这样做，因为对于java，有Collection，支持sort方法。
还有list，对于实现栈和链表比较容易，内部算法也写的不错。
对于c呢，我学过一点，我记得有个quitSort的方法，具体记不清了，使用过，
那个方法的效率是最高的，记得当时老师将它的内部算法就是快速排序算法。

Answer 16

蛮有意思的，自己写了下，大家给拍拍砖
package com.saturday.test;/**
 * 实现堆栈操作
 * @author 王建波
 */
public class MyStack {
private int index;
private int[] stack;
private int[] max;
private static int PAGE_SIZE=10; public static void main(String[] args){
MyStack stack=new MyStack();

try{
//入栈出栈测试
stack.push(1);
stack.push(2);
stack.push(12);
stack.push(17);
stack.push(55);
stack.push(19);
System.out.println(
stack.toString()+"max:"+stack.getMax()
);

System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(
stack.toString()+"max:"+stack.getMax()
);
stack.pop();
stack.pop();
stack.pop();

//测试自动扩容
stack.push(0);
stack.push(110);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
stack.push(9);
stack.push(10);
stack.push(11);
stack.push(12);
stack.push(13);
System.out.println(stack);
System.out.println(stack.getMax());

}catch (Exception e) {
e.printStackTrace();
}
}


public MyStack(){
index=-1;
stack=new int[PAGE_SIZE];
max=new int[PAGE_SIZE];
}


public void push(int num){
int stackLen=stack.length;

index++;
stack[index]=num;
max[index]=index<1?num
  :(max[index-1]>num?max[index-1]:num);

if(index==stackLen-1){
int[] _newStack=new int[stackLen+PAGE_SIZE];
int[] _newMax=new int[stackLen+PAGE_SIZE];

System.arraycopy(stack,0,_newStack,0,stackLen);
System.arraycopy(max,0,_newMax,0,stackLen);

stack=_newStack;
max=_newMax;
}
}


public  int pop() throws Exception{
if(index>=0){
return stack[index--];
}else {
throw new Exception("Emputy Stack!");
}
}


public int getValue() throws Exception{
if(index>=0){
return stack[index];
}else {
throw new Exception("Emputy Stack!");
}
}


public int getMax() throws Exception{
if(index>=0){
return max[index];
}else {
throw new Exception("Emputy Stack!");
}
}
public String toString(){
StringBuffer sbOut=new StringBuffer();

sbOut.append('[');
for(int i=0;i<=index;i++){
sbOut.append(i==0?stack[i]:","+stack[i]);
}
sbOut.append(']');

return sbOut.toString();
}
}

Answer 17

保存sec_max没有意义， 当Pop的值正好是max的时候， max=sec_max, 那么sec_max值又取什么值， 结果是还要再扫描数组。还是弹栈的说法比较适合。。憋一会弹得更有劲

Answer 18

我也以为getMax()是返回最大值呢，如果是返回最大值估计要在Pop和Push上作手脚了返回容量O(1)还是没什么问题的，可以top-base就没问题了

Answer 19

前面有人说用一个最大值保存起来的，我想问如果pop出来的就是那个最大值 那么这个最大值，就需要扫描全队列了？更新吗 当然从概率的角度来说 刚好pop出最大的值不是经常发生的事情。但是毕竟扫描全队列的的复杂度有点大了。

Answer 20

答：48楼xingqiliudehuanghun 兄弟的思路很好，完全正确！
对于getMax()，用空间换时间，这样O（1）级。而且：push()与pop()操作除了空间扩容外，都是O（1）级。我认为这个答案是正解。

Answer 21

48楼,pop时,如果最大元素不是栈顶元素,你的getMax()有问题了.

Answer 22

他用了一组max[]来动态确定最大数

Answer 23

 public class Stack
    {
        Int32[] val=new Int32[10];
        int temp = 0;
        public void Push(int v)
        {
            if (temp==val.Length-1)
            {
                Int32[] vals=new Int32[val.Length*2];
                Array.Copy(val, vals, val.Length);
                val = vals;
            }
            val[temp] = v;
            temp++;
        }
        public int MaxLength()
        {
            return val.Length;
        }
        public bool IsEmpty()
        {
            return temp == 0 ? true : false;
        }
        public int? Pop()
        {
            if (temp == 0)
            {
                return null;
            }
            else
            { 
                return val[temp-1];
            }
        }
        public new string ToString()
        {
            string ret = "";
            foreach (int va in val)
            {
                ret += va.ToString()+"   ";
            }
            return ret;
        }
    }

Answer 24

int stack[];    //存储栈内容
int maxIndex[]; //存储最大值索引
int curIndex;   //当前索引1.maxIndex.length = stack.length
2.maxIndex[curIndex]里面存的是stack[0-curIndex]中最大值的索引.
3.每次push的时候比较一下stack[curIndex-1] 与 stack[curIndex] 哪个大,如果stack[curIndex]大,maxIndex[curIndex]=curIndex否则,maxIndex[curIndex]=maxIndex[curIndex-1].
4.每次取的时候直接返回stack[maxIndex[curIndex]]