Sort Stack

3.5 Sort Stack: Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek, and isEmpty.

• The main idea is to hold a temporary variable for the current element on the top, and then continuing pushing off elements from the second stack until you find an appropriate spot for the temp var.

• O(n^2) time, O(N) space

template <typename T>
stack<T> sortStack(stack<T> s1) {
    if (s1.size() <= 1) return s1;

    // start us off
    stack<T> temp;
    int pop_count = 0;
    temp.push(s1.top());
    s1.pop();

    while (!s1.empty()) {
        // grab top element of s1
        T temp2 = s1.top();
        s1.pop();

        // find correct position in temp
        while (!temp.empty() && temp.top() < temp2) {
            s1.push(temp.top());
            temp.pop();
            pop_count++;
        }
        temp.push(temp2);

        // place back
        for (int i = 0; i < pop_count; i++) {
            temp.push(s1.top());
            s1.pop();
        }
        pop_count = 0;
    }

    return temp;
}


int main() {
    vector<int> v = { 1,5,2,10,3,3,3,3,3,100,1001,232 };
    stack<int> s;
    for (auto i : v) {
        s.push(i);
    }

    stack<int> s2 = sortStack(s);
    while (!s2.empty()) {
        cout << s2.top() << " ";
        s2.pop();
    }
    pause();
}