#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>

using namespace std;

class Stack {
    static const int STACK_LENGTH = 10;
    int stack[STACK_LENGTH];
    int top;
    unsigned int size = 0;

public:
    Stack();
    void push(int);
    int pop();
    unsigned int getSize() const;
    bool isOrdered();
    void pushOrder(int);
    string toString() const;
    Stack operator+(Stack);
    void stackSort() {
        for (int i = 0; i < STACK_LENGTH; i++){
            for (int j = i+1; j < STACK_LENGTH; j++){
                if (stack[i] < stack[j])
                {
                    int tmp = stack[i];
                    stack[i] = stack[j];
                    stack[j] = tmp;
                }
            }
        }
    }
};

Stack::Stack(): top(-1) {
    for(int i = 0; i < STACK_LENGTH; i++) {
        stack[i] = NULL;
    }
}

void Stack::push(int i) {
    top++;
    size++;
    stack[top] = i;
}

int Stack::pop() {
    if (top == -1) {
        cout << "Stack is empty!" << endl;
        return NULL;
    }

    int data = stack[top];
    stack[top] = NULL;
    top--;
    size--;

    return data;
}

unsigned Stack::getSize() const {
    return size;
}

bool Stack::isOrdered() {
    for (int i = 0; i < size; i++) {
        if(i != 0) {
            if(stack[i] >= stack[i - 1]) {
                return false;
            }
        }
    }
    return true;
}

void Stack::pushOrder(int input) {
    if(size != STACK_LENGTH) {
        if(isOrdered()) {
            int i=0;
            while (i < size && input > stack[i]) i++;
                for (int j = size; j > i; j--) {
                    stack[j] = stack[j - 1];
                }
                stack[i] = input;
                size++;
                top++;
        } else {
            cout << "Stack is not ordered" << endl;
        }
    } else {
        cout << "Stack is full" << endl;
    }
}

string Stack::toString() const {
    stringstream ss;
    for (int i = 0; i < size; i++) {
        ss << setw(2) << stack[i];
    }
    ss << endl;
    return ss.str();
}

Stack Stack::operator+(Stack stackToMerge) {
    Stack resultStack;

    for (int i = 0; i < STACK_LENGTH; i++) {
        if (i % 2 == 0) {
            if(size > 0) {
                resultStack.push(pop());
            } else if(stackToMerge.getSize() > 0) {
                resultStack.push(stackToMerge.pop());
            }
        } else {
            if (stackToMerge.getSize() > 0) {
                resultStack.push(stackToMerge.pop());
            } else if (size > 0) {
                resultStack.push(pop());
            }
        }
    }

    return resultStack;
}

int main() {
    Stack firstStack, secondStack;
    int answer;
    firstStack.push(5);
    firstStack.push(8);
    firstStack.push(3);
    firstStack.push(5);
    firstStack.push(9);
    firstStack.push(2);

    secondStack.push(1);
    secondStack.push(4);
    secondStack.push(6);
    secondStack.push(8);

    cout << "Merge:" << endl;

    cout << "First Stack:" <<  firstStack.toString();
    cout << "Second Stack:" <<  secondStack.toString();

    Stack resultStack = firstStack + secondStack;

    cout << "Result Stack:" <<  resultStack.toString();

    cout << "Pop:" << endl;

    cout << "pop two last elements" << endl;

    resultStack.pop();
    resultStack.pop();

    cout << "Stack: " <<  resultStack.toString();

    cout << "Size:" << endl;

    cout << "size: " << resultStack.getSize() << endl;
    //resultStack.pop();

    cout << "sort:" << endl;
    resultStack.stackSort();
    cout << "sorted: " << resultStack.toString() << endl;

    cout << "isOrdered?" << endl;

    cout << "isOrdered: " << (resultStack.isOrdered() == 1 ? "true" : "false") << endl;
    if(resultStack.isOrdered() == 1){
        cout << "want to sort Stack? \n 0 - no, 1 - yes " <<endl;
        cin >> answer;
        if(answer == 1){
            cout << "pushOrder:" << endl;
            cout << "push 10" << endl;
            resultStack.pushOrder(10);
            //resultStack.stackSort();
            cout << resultStack.toString();
        } else{
            cout << "Fuck up :/" << endl;
        }
    } else{
        cout << "still not ordered :/" << endl;

    }
    /*
    cout << "final " << endl;
    resultStack.toString();
     */

    return 0;

}