java实现一个栈，并提供取该栈中最大数的方法，复杂度O(1)

?

记得是哪个面试题里的，这里只想到一个简单的方法，大家看看对不对。。。

?

?

/** * @Project:      Test      * @File:         org.coffeesweet.test01.Test19.java * @Author:       coffeesweet * @Date:         2011-6-7 * @Description:  2011 coffeesweet Inc. All rights reserved. */package org.coffeesweet.test01;import java.util.LinkedList;/** * @author coffeesweet * */public class Test19 {public static void main(String[] args){Long[] numList = new Long[]{1L,5L,3L,2L,1L,5L,7L,6L,7L,8L,-1L,-5L,2L,7L,2L,3L,5L,9L,9L};Test19 t19 = new Test19();MaxNumStack mns = t19.new MaxNumStack();for(int i=0;i<numList.length;i++){mns.push(numList[i]);}System.out.println(mns.pop());System.out.println(mns.pop());System.out.println(mns.top());System.out.println(mns.getMaxNum());}private class MaxNumStack{private LinkedList<Long> stackList = new LinkedList<Long>();private LinkedList<Long> maxNumList = new LinkedList<Long>();public void push(Long num){stackList.addLast(num);if(maxNumList.isEmpty()||(maxNumList.getLast().compareTo(num)<1)){maxNumList.addLast(num);}}public Long pop(){if(stackList.isEmpty())return null;if((maxNumList.getLast().compareTo(stackList.getLast())<1))maxNumList.removeLast();return stackList.removeLast();}public Long top(){return stackList.getLast();}public boolean isEmpty(){return stackList.isEmpty();}public Long getMaxNum(){if(maxNumList.isEmpty())return null;return maxNumList.getLast();}}}

?if(maxNumList.isEmpty()||(maxNumList.getLast().compareTo(num)<1)){ maxNumList.addLast(num); }
导致多pop几次以后，就可能找不到最大数了
按你的思路，你的maxNumList必须存储所有的数字，并且排序。

如果数字的区间不是特别大的话，可以考虑除栈本身的数据结构外(不管是用顺序表还是链表)，用一个BitSet存储所有的数，在存储的时候相当于对所有数进行了排序，并且取最大值也很容易，然后每次pop的时候对相应位set 0就可以了if(maxNumList.isEmpty()||(maxNumList.getLast().compareTo(num)<1)){ maxNumList.addLast(num); }
导致多pop几次以后，就可能找不到最大数了
按你的思路，你的maxNumList必须存储所有的数字，并且排序。

如果数字的区间不是特别大的话，可以考虑除栈本身的数据结构外(不管是用顺序表还是链表)，用一个BitSet存储所有的数，在存储的时候相当于对所有数进行了排序，并且取最大值也很容易，然后每次pop的时候对相应位set 0就可以了
同上

送一程if(maxNumList.isEmpty()||(maxNumList.getLast().compareTo(num)<1)){ maxNumList.addLast(num); }
导致多pop几次以后，就可能找不到最大数了
按你的思路，你的maxNumList必须存储所有的数字，并且排序。

如果数字的区间不是特别大的话，可以考虑除栈本身的数据结构外(不管是用顺序表还是链表)，用一个BitSet存储所有的数，在存储的时候相当于对所有数进行了排序，并且取最大值也很容易，然后每次pop的时候对相应位set 0就可以了
同上

送一程


呵呵，一直在内网，没有切出来，老早前的一个面试题，有同学问我就放出来了，没怎么再看。当时就这么随便写的，不考虑线程问题，逻辑应该没问题吧？？
嘿嘿，不管怎么样，谢谢大家的关注，我再看看。if(maxNumList.isEmpty()||(maxNumList.getLast().compareTo(num)<1)){ maxNumList.addLast(num); }
导致多pop几次以后，就可能找不到最大数了
按你的思路，你的maxNumList必须存储所有的数字，并且排序。

如果数字的区间不是特别大的话，可以考虑除栈本身的数据结构外(不管是用顺序表还是链表)，用一个BitSet存储所有的数，在存储的时候相当于对所有数进行了排序，并且取最大值也很容易，然后每次pop的时候对相应位set 0就可以了
同上

送一程


我的maxNumList并没有存储所有数字啊，比如我按顺序入栈这些数字：[1, 5, 3, 2, 1, 5, 7, 6, 7, 8, -1, -5, 2, 7, 2, 3, 5, 9, 9]，然后我的maxNumList存入的数字是：[1, 5, 5, 7, 7, 8, 9, 9]；

再然后我的栈连续POP两次以后变成：[1, 5, 3, 2, 1, 5, 7, 6, 7, 8, -1, -5, 2, 7, 2, 3, 5]，
这时我的maxNumList也变成了[1, 5, 5, 7, 7, 8]，

maxNumList.getLast()始终是目前栈的最大数啊。难道是我的main里的测试数据有问题？？？有没想到的情况？？？if(maxNumList.isEmpty()||(maxNumList.getLast().compareTo(num)<1)){ maxNumList.addLast(num); }
导致多pop几次以后，就可能找不到最大数了
按你的思路，你的maxNumList必须存储所有的数字，并且排序。

如果数字的区间不是特别大的话，可以考虑除栈本身的数据结构外(不管是用顺序表还是链表)，用一个BitSet存储所有的数，在存储的时候相当于对所有数进行了排序，并且取最大值也很容易，然后每次pop的时候对相应位set 0就可以了

要改成小于等于1就行了，我试过了！