CTCI, 3.6.

/*
11.01.2015
3.6. Write a program to sort a stack in ascending order (with biggest items on top).
You may use at most one additional stack to hold items, 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
*/
#include<stdio.h>
#include<iostream>
#include<time.h>
#include<stdlib.h>

using namespace std;

class Node{
public:
    Node(int n){
        value = n;
        next = NULL;
    }
    int value;
    Node *next;
};

class Stack{
private:
    Node *top;
public:
    Stack(){
        top = NULL;
    }
    void push(int value){
        if(!top){
            top = new Node(value);
        }
        else{
            Node *newTop = new Node(value);
            newTop->next = top;
            top = newTop;
        }
    }
    int pop(){
        if (!top){
            return -1;
        }
        Node *tmp = top;
        int retValue = tmp->value;
        top = top->next;
        free(tmp);
        return retValue;
    }
    bool isEmpty(){
        return top == NULL;
    }
    int peek(){
        if (!top)
            return -1;
        return top->value;
    }
    void print(){
        if (isEmpty())
            return;
        else{
            int val = pop();
            cout << val << " ";
            print();
            push(val);

        }
    }
};

void sortOrder(Stack &stack, int value){
    if (stack.isEmpty()){
        stack.push(value);
        return;
    }
    if (stack.peek() > value){
        int memTop = stack.pop();
        sortOrder(stack, value);
        stack.push(memTop);
    }
    else{
        stack.push(value);
    }


}
void sortStack(Stack &stack){
    if (stack.isEmpty()){
        return;
    }
    int topValue = stack.pop();
    sortStack(stack);
    sortOrder(stack, topValue);

}

int main(){
    Stack s;
    srand(time(NULL));

    for (int i = 0; i < 10; i++){
        int rnd = rand() % 100 + 1;
        cout << "push: " << rnd << "\n";
        s.push(rnd);
    }
    s.print();
    sortStack(s);
    cout << "sorted: \n";
    s.print();
}