学步园

     栈就像叠盘子，当盘子叠得太高时，就会倾斜倒下。因此，在真实的世界中，当一叠盘子 (栈)超过了一定的高度时，我们就会另起一堆，再从头叠起。实现数据结构SetOfStacks 来模拟这种情况。SetOfStacks由几个栈组成，当前一栈超出容量时，需要创建一个新的栈 来存放数据。SetOfStacks.push()和SetOfStacks.pop()的行为应当和只有一个栈时 表现的一样。

进一步地，

    实现函数popAt(int index)在指定的子栈上进行pop操作

    首先，我们如果不考虑popAt这个麻烦的函数，那么SetOfStacks的实现就简单很多。 SetOfStacks由栈的数组构成，我们需要一个指向当前栈的变量cur， 每当执行push操作时，我们需要检查一下当前栈是否已经达到其容量了， 如果是的话，就要将cur加1，指向下一个栈。而执行pop操作时， 需要先检查当前栈是否为空，如果是，则cur减1，移向上一个栈。top操作同理。 这时候，SetOfStacks可以想象成把一个本来可以叠得很高的栈，分成了好几个子栈。
push和pop操作其实都只是在“最后”一个子栈上操作。

代码如下：

<span style="font-size:18px;">class SetOfStacks{//without popAt()
private:
    stack *st;
    int cur;
    int capacity;

public:
    SetOfStacks(int capa=STACK_NUM){
        st = new stack[capa];
        cur = 0;
        capacity = capa;
    }
    ~SetOfStacks(){
        delete[] st;
    }
    void push(int val){
        if(st[cur].full()) ++cur;
        st[cur].push(val);
    }
    void pop(){
        if(st[cur].empty()) --cur;
        st[cur].pop();
    }
    int top(){
        if(st[cur].empty()) --cur;
        return st[cur].top();
    }
    bool empty(){
        if(cur==0) return st[0].empty();
        else return false;
    }
    bool full(){
        if(cur==capacity-1) return st[cur].full();
        else return false;
    }    
};</span>

      当加入popAt函数，情况就变得复杂了。因为这时候的数据分布可能出现中间的某些子栈使 用popAt把它们清空了，而后面的子栈却有数据。为了实现方便，我们不考虑因为popAt 带来的空间浪费。即如果我用popAt把中间某些子栈清空了，并不把后面子栈的数据往前移 动。这样一来，cur指向操作的“最后”一个栈，它后面的子栈一定都是空的， 而它本身及前面的子栈由于popAt函数的缘故都有可能是空的。如果没有popAt函数， cur前面的子栈一定都是满的(见上面的例子)。这样一来，push仍然只需要判断一次当前子
栈是否为满。但是，pop函数则要从cur向前一直寻找，直到找到一个非空的子栈， 才能进行pop操作。同理，popAt，top，empty也是一样的。

代码如下：

<span style="font-size:18px;">class SetOfStacks1{
private:
    stack *st;
    int cur;
    int capacity;

public:
    SetOfStacks1(int capa=STACK_NUM){
        st = new stack[capa];
        cur = 0;
        capacity = capa;
    }
    ~SetOfStacks1(){
        delete[] st;
    }
    void push(int val){
        if(st[cur].full()) ++cur;
        st[cur].push(val);
    }
    void pop(){
        while(st[cur].empty()) --cur;
        st[cur].pop();
    }
    void popAt(int idx){
        while(st[idx].empty()) --idx;
        st[idx].pop();
    }
    int top(){
        while(st[cur].empty()) --cur;
        return st[cur].top();
    }
    bool empty(){
        while(cur!=-1 && st[cur].empty()) --cur;
        if(cur==-1) return true;
        else return false;
    }
    bool full(){
        if(cur==capacity-1) return st[cur].full();
        else return false;        
    }
};</span>