#include <iostream>
using namespace std;
typedef int Data;

struct Node
{
    Node(Data d):data(d){next = NULL;};
    Data data;
    Node* next;
};

class Stack
{
public:
    Stack():topNode(NULL){};
    void pop()
    {
        if(topNode != NULL)
        {
            Node* p = topNode;
            topNode = topNode->next;
            delete p;
        } else {
            throw "Empty Stack";
        }
    };
    Data top()
    {
        if(topNode != NULL)
        {
            return topNode->data;
        } else {
            throw "Empty Stack";
        }
    };
    void push(Data data)
    {
        Node* d = new Node(data);
        d->next = topNode;
        topNode = d;
    };
    bool isEmpty(){return topNode == NULL;};
    void sort()
    {
        Stack t;
        while(!this->isEmpty())
        {
            Data data = this->top();
            this->pop();
            while(!t.isEmpty() && t.top() > data)
            {
                this->push(t.top());
                t.pop();
            }
            t.push(data);
        };
        while(!t.isEmpty())
        {
            this->push(t.top());
            t.pop();
        };
    };
private:
    Node* topNode;
};

int main()
{
    Stack stack;
    stack.push(3);
    stack.push(1);
    stack.push(5);
    stack.push(9);
    stack.sort();
    while(!stack.isEmpty())
    {
        cout<<stack.top()<<endl;
        stack.pop();
    }
    system("pause");
};