3.3 栈就像叠盘子，当盘子叠得太高时，就会倾斜倒下。因此，在真实的世界中，当一叠盘子 (栈)超过了一定的高度时，我们就会另起一堆，再从头叠起。实现数据结构SetOfStacks 来模拟这种情况。SetOfStacks由几个栈组成，当前一栈超出容量时，需要创建一个新的栈 来存放数据。SetOfStacks.push()和SetOfStacks.pop()的行为应当和只有一个栈时 表现的一样。
进一步地，
实现函数popAt(int index)在指定的子栈上进行pop操作。
实现第一步：
#include<iostream>
#include<new>
using namespace std; //myStack表示一个栈
class myStack
{
private:
int *buf;
int capacity;
int cur;
public:
myStack(int size=)
{
buf=new int[size];
capacity=size;
cur=-;
}
~myStack()
{
delete[] buf;
}
void push(int x)
{
buf[++cur]=x;
}
void pop()
{
cur--;
}
int top()
{
return buf[cur];
}
bool empty()
{
return cur==-;
}
bool full()
{
return cur==capacity-;
}
}; //一个栈组成的数组
class SetOfStacks
{
private:
myStack *st;
int cur;
int capacity;
public:
SetOfStacks(int cap=)
{
st=new myStack[cap];
capacity=cap;
cur=;
}
~SetOfStacks()
{
delete[] st;
}
void push(int x)
{
if(st[cur].full())
cur++;
if(cur>capacity-)
return;
st[cur].push(x);
}
void pop()
{
if(st[cur].empty())
cur--;
if(cur<)
return;
st[cur].pop();
}
int top()
{
if(st[cur].empty())
cur--;
if(cur<)
return ;
else
return st[cur].top();
}
bool empty()
{
return cur==&&st[cur].empty();
}
bool full()
{
return cur==capacity-&&st[cur].full();
}
};
int main()
{
SetOfStacks ss1;
for(int i=; i<*+; ++i)
{
ss1.push(i);
}
while(!ss1.empty())
{
cout<<ss1.top()<<endl;
ss1.pop();
}
return ;
}
当加入popAt函数，情况就变得复杂了。因为这时候的数据分布可能出现中间的某些子栈使 用popAt把它们清空了，而后面的子栈却有数据。为了实现方便，我们不考虑因为popAt 带来的空间浪费。即如果我用popAt把中间某些子栈清空了，并不把后面子栈的数据往前移 动。这样一来，cur指向操作的“最后”一个栈，它后面的子栈一定都是空的， 而它本身及前面的子栈由于popAt函数的缘故都有可能是空的。如果没有popAt函数， cur前面的子栈一定都是满的(见上面的例子)。这样一来，push仍然只需要判断一次当前子 栈是否为满。但是，pop函数则要从cur向前一直寻找，直到找到一个非空的子栈， 才能进行pop操作。同理，popAt，top，empty也是一样的。
#include<iostream>
#include<new>
using namespace std; //myStack表示一个栈
class myStack
{
private:
int *buf;
int capacity;
int cur;
public:
myStack(int size=)
{
buf=new int[size];
capacity=size;
cur=-;
}
~myStack()
{
delete[] buf;
}
void push(int x)
{
buf[++cur]=x;
}
void pop()
{
cur--;
}
int top()
{
return buf[cur];
}
bool empty()
{
return cur==-;
}
bool full()
{
return cur==capacity-;
}
}; //一个栈组成的数组
class SetOfStacks
{
private:
myStack *st;
int cur;
int capacity;
public:
SetOfStacks(int cap=)
{
st=new myStack[cap];
capacity=cap;
cur=;
}
~SetOfStacks()
{
delete[] st;
}
void push(int x)
{
if(st[cur].full())
cur++;
if(cur>capacity-)
return;
st[cur].push(x);
}
void pop()
{
while(st[cur].empty())
cur--;
if(cur<)
return;
st[cur].pop();
}
int top()
{
while(st[cur].empty())
cur--;
if(cur<)
return ;
else
return st[cur].top();
}
bool empty()
{
while(cur>=&&st[cur].empty())
cur--;
return cur==-;
}
bool full()
{
return cur==capacity-&&st[cur].full();
}
void popAt(int idx)
{
while(st[idx].empty()) --idx;
st[idx].pop();
}
};
int main()
{
SetOfStacks ss1;
for(int i=; i<*+; ++i)
{
ss1.push(i);
}
for(int i=; i<; ++i)
{
ss1.popAt();
//ss1.popAt(1);
ss1.popAt();
}
while(!ss1.empty())
{
cout<<ss1.top()<<endl;
ss1.pop();
}
return ;
}