Zad18

/*
26.12.2014
Probl em 18 Given a stack S, write a C program to sort the stack (in ascending order).
You are not allowed to make any assumptions about how the stack is implemented; the only
functions allowed to be used are: Push, Pop, Top, IsEmpty, IsFull
*/

#include<stdio.h>
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>

using namespace std;

class Stack {

private:
    int size = 0;
    vector<int> items;
public:

    Stack(){
        items = vector<int>(1);
    }

    bool IsEmpty(){
        return size == 0;
    }
    int Pop(){
        int popItem = items[size - 1];
        size--;
        if ((size > 0) && (size == items.size() / 4)){
            items.resize(items.size() / 2);
        }
        return popItem;
    }
    void Push(int item){
        size++;
        items[size - 1] = item;
        if (size == items.size()){
            items.resize(items.size() * 2);
        }
    }
    int Top(){
        return items[size - 1];
    }
};

void pushValueInPlace(Stack &stack, int value){
    if (stack.IsEmpty())
        stack.Push(value);
    else{
        if (stack.Top() < value){
            int mem = stack.Pop();
            pushValueInPlace(stack, value);
            stack.Push(mem);
        }
        else
            stack.Push(value);
    }
}

void sortStack(Stack &stack){
    if (stack.IsEmpty())
        return;
    int top = stack.Pop();
    sortStack(stack);
    pushValueInPlace(stack, top);

}

int main(){
    Stack stack;

    srand(time(NULL));


    for (int i = 0; i < 15; i++){
        int num = rand() % 100 + 1;
        stack.Push(num);
    }

    sortStack(stack);

    while (!stack.IsEmpty()){
        cout << stack.Pop() << " ";
    }
    cout << "\n";
}