## Set of stacks with capacity

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 structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

My initial thoughts:
Use stack of stacks. Push to the top sub-stack. Pop from the top sub-stack. If the top sub-stack becomes empty, remove it. Keep a array list of all the sub-stacks.

My initial codes:

```	public class MyStackOfStack<T> {

private MyStack<MyStack<T>> buffer = new MyStack<MyStack<T>>();
private static final int THRESHOLD = 10;
private int size = 0;
private List<MyStack<T>> indices = new ArrayList<MyStack<T>>();

public void push(T data) {
if (size < THRESHOLD && size > 1) {
buffer.peek().push(data);
size++;
} else { // size == 0 || size == THRESHOLD
MyStack<T> newStack = new MyStack<T>();
newStack.push(data);
size = 1;
buffer.push(newStack);
}
}

public T pop() {
MyStack<T> topStack = buffer.peek();
if (size > 1) {
} else { // size == 1
T data = topStack.pop();
buffer.pop();
indices.remove(indices.size() - 1);
size = THRESHOLD;
return data;
}
}

public T popAt(int index) {
return indices.get(index).pop();
}
}

popAt(int index) removes the bottom element of the sub-stack.
If one of the middle sub-stack is poped, its above sub=stack is supposed to pad down one element. This behavior is not supported.

Solution:
public class StackNode2<T> {
private T data = null;
private StackNode2<T> below = null;
private StackNode2<T> above = null;
// getters and setters are omitted.
}

public class MyStack2<T> {

private StackNode2<T> top = null;
private final int CAPACITY;
private StackNode2<T> bottom = null;
private int size = 0;

public MyStack2(int capacity) {
this.CAPACITY = capacity;
}

public void push(T data) {
StackNode2<T> item = new StackNode2<T>(data);
if (size == 0) {
top = item;
bottom = top;
size++;
} else if (size < CAPACITY) {
top.setAbove(item);
item.setBelow(top);
top = item;
size++;
}
}

public T pop() {
if (size > 0) {
size--;
StackNode2<T> item = top;
top = item.getBelow();
// top.setAbove(null);
return item.getData();
}
return null;
}

public T peek() {
if (size > 0) {
}
return null;
}

public int size() {
return size;
}

public boolean isEmpty() {
return size == 0;
}

public boolean isFull() {
return size == CAPACITY;
}

public T getBottom() {
if (size > 0)
return bottom.getData();
else
return null;
}

public T removeFromBottom() {
if (size > 0) {
size--;
StackNode2<T> item = bottom;
bottom = item.getAbove();
bottom.setBelow(null);
return item.getData();
} else {
return null;
}
}
}

public class SetOfStack<T> {

private ArrayList<MyStack2<T>> buffer =
new ArrayList<MyStack2<T>>();
private final int CAPACITY;

public SetOfStack(int capacity) {
this.CAPACITY = capacity;
}

public void push(T data) {
if (buffer.isEmpty()) {
MyStack2<T> stack = new MyStack2<T>(CAPACITY);
stack.push(data);
} else {
MyStack2<T> stack = buffer.get(buffer.size() - 1);
if (stack.isFull()) {
MyStack2<T> newStack = new MyStack2<T>(CAPACITY);
newStack.push(data);
} else {
stack.push(data);
}
}
}

public T pop() {
if (buffer.isEmpty()) {
return null;
} else {
MyStack2<T> stack = buffer.get(buffer.size() - 1);
T data = stack.pop();
if (stack.isEmpty())
buffer.remove(buffer.size() - 1);
return data;
}
}

public T popAt(int index) {
return leftShift(index, true);
}

public T leftShift(int index, boolean removeTop) {
MyStack2<T> stack = buffer.get(index);
T removedItem = null;
if (removeTop)
removedItem = stack.pop();
else
removedItem = stack.removeFromBottom();
if (stack.isEmpty())
buffer.remove(index);
else if (buffer.size() > index + 1) {
stack.push(leftShift(index + 1, false));
}
return removedItem;
}
}

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5c910df38da79', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5c910df38dabc',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5c910df38dabf',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Related
```

1. C++ implementation ::

#include
#include
#include
using namespace std;

vector<stack*>vec;
int index=0;
int size=5;

void init()
{
stack*s=new stack;
vec.push_back(s);
}

bool top(int &v)
{
stack*s=new stack;
s=vec.at(index);
if(s->size()==0 && index==0)
return false;
if(s->size()==0)
{
delete s;
index–;
s=vec.at(index);
}

v=s->top();
return true;
}

void pop(int b)
{
stack*s=new stack;
s=vec.at(index);

if(s->size()==0 && index==0)
{
cout<size()==0 && index>0)
{
delete(s);
index–;
s=vec.at(index);
s->pop();
}
else if(s->size()>0 && index>=0)
{
s->pop();
}

}
void push(int x)
{
stack*s=vec.at(index);
cout<size();
if(s->size()==5)
{
s=new stack;
vec.push_back(s);
index++;
}
s->push(x);
}

void pop_at(int in)
{
stack*s=new stack;
s=vec.at(in);
int a[5],i=0;
int x=s->top();
s->pop();
if(s->size()<5&& in!=index)
{
while(in!=index)
{
stack*q=new stack;
in=in+1;
q=vec.at(in);
while(q->size()!=0 && i!=5)
{
a[i]=q->top();

i++;
q->pop();

}
i–;
s->push(a[i]);
while(i!=0)
{ i–;
q->push(a[i]);
}
s=q;
}
}
}

int main()
{
init();
for(int i=0;i<15;i++)
{
push(i);
cout << "Push: Stack index " << index << " — " << i << endl;

}

for(int i=0;i<1;i++)
{
int b,v;
b=top(v);
pop(b);
if(b){
cout << "Stack index " << index << " — " << v << endl;
}
else{
cout << "No more elements in stack !" <>in;
pop_at(in);
for(int i=0;i<14;i++)
{
int b,v;
b=top(v);
pop(b);
if(b){
cout << "Stack index " << index << " — " << v << endl;
}
else{
cout << "No more elements in stack !" << endl;
}
}

return 0;
}