CareerCup3.3.cpp

CareerCup3.3.cpp

/*
 * Chapter 3
 *
 * 3.3 Implement a data structure SetOfStacks.
 * SetOfStacks should be composed of several stacks and should
 * creat new stack once that previous one exeeds capacity.
 * SetOfStack.push() and SetOfStack.pop() should behave identically to a single stack.
 * FOLLOW UP
 * Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.
 */

#include <iostream>
#include <stack>
#include <vector>  // for dynamic array

using namespace std;
/* Definition of class SetOfStack */
class SetOfStack {
private:
    vector<stack<int>> stack_set;
    int capacity;
    int size;
public:
    SetOfStack(int cap) {capacity = cap; size = 0;}
    void push(int data);
    void pop();
    int top();
    void popAt(int index);
    int stack_size() {return size;}
};
/* SetOfStack member functions implementation */
void SetOfStack::push(int data) {
    if (stack_set.empty()) {
        stack<int> sub_stack;
        sub_stack.push(data);
        stack_set.push_back(sub_stack);
        size++;
    }
    else if (stack_set.back().size() < capacity) {
        stack_set.back().push(data);
        size++;
    }
    else {
        stack<int> sub_stack;
        sub_stack.push(data);
        stack_set.push_back(sub_stack);
        size++;
    }
}

void SetOfStack::pop() {
    if (stack_set.back().size()) {
        stack_set.back().pop();
        size--;
    }
    if (stack_set.back().empty()) {
        stack_set.pop_back();
    }
}

int SetOfStack::top() {
    if (!stack_set.back().empty()) {
        return stack_set.back().top();
    }
    else
        return -1;
}


/*FOLLOW UP: popAt(int index)*/
// sub-stack indexed from 0
void SetOfStack::popAt(int index) {
    stack<int> tmp;
    
    if (index >= 0 && index < stack_set.size() && !stack_set.empty()) {
        stack_set[index].pop();
        size--;
        while (stack_set.at(index) < stack_set.back()) {
            /* Shift elements */
            // pop from index+1  and push into tmp
            while (!stack_set[index + 1].empty()) {
                int element = stack_set[index + 1].top();
                tmp.push(element);
                stack_set[index + 1].pop();
            }
            // pop from tmp, and push into index
            // if full, change to index+1
            while (stack_set[index].size() < capacity) {
                int element = tmp.top();
                stack_set[index].push(element);
                tmp.pop();
            }
            // rest element in tmp
            while (!tmp.empty()) {
                int element = tmp.top();
                stack_set[index + 1].push(element);
                tmp.pop();
            }
            index++;
        }
        /* Delete empty stack */
        if (stack_set.back().empty()) {
            stack_set.pop_back();
        }
    }
    else {
        cout << "Wong index number. Out of range." << endl;
        return;
    }
}

void print(SetOfStack sos) {
    for (int i = sos.stack_size(); i > 0; --i)
    {
        cout << sos.top() << " ";
        sos.pop();
    }
    cout << endl;
}

int main(int argc, char const *argv[])
{
    SetOfStack sos(3);  // capacity of sub-stack is 3
    // test push()
    for (int i = 0; i < 14; ++i)
    {
        sos.push(i);
    }
    print(sos);
    // test pop()
    sos.pop();
    print(sos);
    // test popAt()
    sos.popAt(66);
    sos.popAt(0);
    print(sos);
    sos.popAt(2);
    print(sos);
    sos.popAt(4);

    return 0;
}