# Stack of Plates

3.3 Stack of Plates: 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).
FOLLOW UP Implement a function popAt (int index) which performs a pop operation on a specific sub-stack.
template <class T>
class Stack {
public:
Stack(int capacity) {
cap_s = capacity;
iter_s = 0;
data = new T[capacity];
}
~Stack() {
delete[]data;
}
bool push_s(T thing) {
if (full()) {
return false;
}
else {
data[iter_s] = thing;
iter_s++;
return true;
}
}
bool pop_s() {
if (empty_s()) {
return false;
}
else {
iter_s--;
return true;
}
}
T top_s() {
if (empty_s()) {
return INT_MAX;
}
return data[iter_s - 1];
}
bool empty_s() {
return iter_s == 0;
}
private:
// array
T *data;
int cap_s;
int iter_s;
bool full() {
return iter_s == cap_s;
}
};
template <class T>
class setOfStacks {
public:
setOfStacks(const int capacity) {
Stack<T> *s = new Stack<T>(capacity);
stacks.push_back(s);
cap = capacity;
iter = 0;
}
void push(T thing) {
// current stack is full
if (stacks.at(iter)->push_s(thing) == false) {
Stack<T> *s = new Stack<T>(cap);
stacks.push_back(s);
iter++;
stacks.at(iter)->push_s(thing);
}
}
void pop() {
// everything is empty
if (empty()) {
cout << "stack is empty" << endl;
return;
}
// current stack is empty
else if (subEmpty()) {
// delete current stack, and move on the previous
delete stacks.at(iter);
iter--;
stacks.at(iter)->pop_s();
}
else {
stacks.at(iter)->pop_s();
}
}
T top() {
// everything is empty
if (empty()) {
cout << "stack is empty" << endl;
return INT_MAX;
}
// current stack is empty
else if (subEmpty()) {
// pop or top can be preformed at any point so
// the share the same three lines
delete stacks.at(iter);
stacks.resize(stacks.size() - 1);
iter--;
stacks.at(iter)->top_s();
}
// current stack is empty
else {
return stacks.at(iter)->top_s();
}
}
bool empty() {
return (stacks.size() == 1 && stacks.at(iter)->empty_s());
}
private:
bool subEmpty() {
return (stacks.at(iter)->empty_s());
}
int cap;
int iter;
vector<Stack<T>*> stacks;
};
int main() {
cout << "// testing stack" << endl;
Stack<int> s(50);
for (int i = 0; i <= 50; i++) {
s.push_s(i);
}
// overflow
cout << s.push_s(51);
pause();
while (!s.empty_s()) {
cout << s.top_s() << " ";
s.pop_s();
}
// underflow
cout << s.pop_s();
pause();
cout << "// testing set of Stacks" << endl;
setOfStacks<int> ss(5);
for (int i = 0; i <= 100; i++) {
ss.push(i);
cout << ss.top() << " ";
//pause();
}
// next stack
ss.push(101);
//pause();
while (!ss.empty()) {
cout << ss.top() << " ";
ss.pop();
}
pause();
// completely empty
ss.pop();
pause();
}