【第三轮】6.30-7.6 CareerCup 3.3

3.3 Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structureSetOf Stacks that mimics this. SetOf Stacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should be have identically to a single stack(that is,pop() should return the same values as it would if there were just a single stack).
FOLLOW UP
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

我这次是来求教的……
我的思路是，把stack化成一个数组来完成这个要求，但这个程序怎么都调试不对，5个小时了……
import java.util.*;

class stack{
        int maxSize;
        Object[][] stElem = new Object[maxSize][10];
        int top[] = new int[maxSize];
       
       
        public void init(int currInt){
                top[currInt] = 0;
        }

        public Object pop(int currInt){
                if(top[currInt] == 0)
                        return null;
                else
                        return stElem[--top[currInt]];
               
        }
        public void push(int currInt, Object e){
                if(top[currInt]<=9){
                        top[currInt]++;
                        stElem[currInt][top[currInt]] = e;
                }
                else
                        System.out.print("您真逗");
        }
        public void display(int currInt){
                for(int i = top[currInt]-1; i>=0; i--)
                        System.out.print(stElem[currInt][i]+" ");
                System.out.println();
        }
}

public class Q3_3{
        public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
                System.out.print("请输入值的总数:");
                int x = sc.nextInt();       
                stack st = new stack();
                st.maxSize = x/10+1;
                int i = 0;
                int j = 0;
                for(int currInt = 0; currInt < st.maxSize; currInt++){
                        st.init(currInt);
                        while(j%10 != 0 && i<=x){
                                st.push(currInt, i);
                                i++;
                                j++;
                        }
                }
                System.out.println(st.top[0]);
                System.out.print("请输入想要显示的栈:");
                st.display(sc.nextInt());
                System.out.print(st.top[0]);
        }
}

【解题思路】c++ 用了vector, 每个元素是一个stack. 一个stack满了，新建一个stack接着push_back()到vector; 反之如果最后一个stack空了就马上
                         pop_back()
                  FOLLOW UP：pop的部分很直接，有了index，找到vector对应的那个stack 进行pop()。 比较烦的是，若pop非最后一个stack，就要移动后面的
                  所有元素，我用了临时的一个stack来移动，这部分代码多一点。
【时间复杂度】
O(1) : pop(), push(int data)
O(n) : popAt(int index)
【空间复杂度】
O(1) : pop(), push(int data)
O(n) : popAt(int index)
【gist link】
https://gist.github.com/xun-gong/432e30aa9c8c4419095c

【解题思路】
Maintaining a list of stacks.
Push: add new stack if the current one is full
Pop: remove current stack if it's empty after pop
PopAt: simply pop that stack without filling in the empty space from the bottom of following stacks

【时间复杂度】
O(1) - Average/Amortized
O(Capacity) - Worst case

【空间复杂度】
O(N) - N is size of all stacks

【gist link】
https://gist.github.com/chrislukkk/795abf2fe2350f419594

【解题思路】
使用ArrayList存储Stack，这样popAt(index)操作是O(1)，当Array满了之后，再添加Stack，ArrayList会自动double size，所以push操作是average O(1)
【时间复杂度】
push : average O(1)
pop: average O(1)
popAt: O(1)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/chouclee/1e3eacb31d0bb2ea52c9

没有做优化，尾部连续几个Stack为空时应该删除部分Stack，不过影响不大

【解题思路】
Stack的本质是数组，而本题的一大难点在于如何在保留原stack的前提下创立新的stack。所以只要把数组改为矩阵就可以了
【时间复杂度】
O(1)
【空间复杂度】
O(N)
【gist link】
https://github.com/donnice/donnice/blob/master/Q3_3

请帮我把我地板里的帖子删了谢谢……

【解题思路】Implement a counter in each stack, if the counter is greater than the threshold, create a new stack. store the stacks in an ArrayList.
【时间复杂度】 O(1)
【空间复杂度】O(n)
【gist link】https://gist.github.com/bitcpf/317b70b2fc28c6134846

【解题思路】use an arraylist to store stacks.   when pop elements by popAt(),   use the roll over method described in the book.
【时间复杂度】 O(1) except for popAt()
【空间复杂度】O(n)
【gist link】https://gist.github.com/jyhjuzi/073c6c9788ad5b5bdf5b

【解题思路】use an ArrayList of LinkedList. Roll over when popAt().
【时间复杂度】 O(1) for pop(), push()
【空间复杂度】O(n)
【gist link】https://gist.github.com/nealhu/36b8feb85c435958e9b6

【解题思路】  use a 2-D array to mimic set of stacks.  use a pivot index to indicate current stack that common pop() and push() are applyed to
【时间复杂度】
  O(1)
【空间复杂度】
  O(n)
【gist link】
  https://gist.github.com/monkerek/37e80cd7adc5db094774