Zad12

/*
18.12.2014
Problem 12 Write a C Program to reverse a stack in place using recursion. You can only
use the following ADT functions on stack: IsEmpty, IsFull, Push, Pop, Top.

*/

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

#define max 1000
using namespace std;

class Stack {

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

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

    bool IsEmpty(){
        return size == 0;
    }
    bool IsFull(){
        return false;
        //return size == max; // ?
    }
    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 pushToBottom(Stack *stack, int value){
    if (stack->IsEmpty()){
        stack->Push(value);
    }
    else{
        int top = stack->Pop();
        pushToBottom(stack, value);
        stack->Push(top);
    }

}

void reverseStack(Stack *stack) {
    if (stack->IsEmpty()){
        return;
    }
    int top = stack->Pop();
    reverseStack(stack);
    pushToBottom(stack, top);
};


int main(){
    Stack stack;
    for (int i = 0; i < 10; i++){
        stack.Push(i);
    }

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