#include <iostream>
#include <string>

using namespace std;

template<typename T>//T używywane zamiast nazwy typu
class Stack //stos
{
    T *stack;
    int actSize, maxSize;
    string nazwa;

    void resize()//funkcja, która powiększa tablice
    {
        maxSize *= 2;
        T *nowaTablica = new T[maxSize]; //tworzenie nowej tablicy wielkosci nowego maxsize
        memcpy(nowaTablica, stack, actSize*sizeof(T));//dokad,skad, ile

        delete[] stack;//usuwanie starej tablicy
        stack = nowaTablica; //przypisanie wskaznika do nowej
    }

public:
    Stack(string nazwa)
        :actSize(0), maxSize(10)
    {
        stack = new T[maxSize]; //nowa tablica typu T
        this->nazwa = nazwa;

    }

    ~Stack()
    {
        delete[] stack;//usuwanie stosu
    }

    void push(T obj)
    {
        if (actSize == maxSize)resize();
        stack[actSize] = obj;
        actSize++;
    }

    T pop()
    {
        if (actSize == 0) return -1;
        actSize--; //zmiejsza rozmiar
        return stack[actSize];//zwaracanie ostatniego elementu
    }

    int size(){
        return actSize;
    }

    string Nazwa(){
        return nazwa;
    }
};

void przenies(Stack<int> &A, Stack<int> &C, Stack<int> &B, int n){
    if (n > 1) przenies(A, B, C, n - 1);
    int krazek = A.pop();
    C.push(krazek);
    cout << "Przenosze krazek nr: " << krazek << " z patyczka " << A.Nazwa() << " na patyczek " << C.Nazwa() << endl;
    if (n > 1) przenies(B, C, A, n - 1);
}

int main()

{
    int krazki = 0;

    cout << "Wpisz liczbe krazkow" << endl;
    cin >> krazki;
    if (krazki <= 0)
    {
        cout << "Nie mozna przetestowac algorytmu dla 0 krazkow. Wpisz liczbe krazkow: " << endl;
        cin >> krazki;

    }
    cout << "Chcesz przetestowac algorytm wiez Hanoi dla: " << krazki << " krazkow" << endl;

    Stack<int> A("A"), B("B"), C("C");

    for (int i = krazki; i > 0; i--) A.push(i); //umieszczam krazki na slupku A


    przenies(A, B, C, A.size());


    return 0;
}