> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/stacks_and_queues/stack-of-plates.md).

# 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.

```cpp
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();

}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/stacks_and_queues/stack-of-plates.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.