Односвязные списки: реализация стека

#include <iostream>
 
using namespace std;
 
struct node
{
    int inf;
    struct node *next;    
};
 
struct node *head, *s;
 
void push(int val)
{
    s = malloc(10*sizeof(int));
    s->inf = val;
    s->next = head;
    head = s;
}
 
void pop(int &val)
{
    s = head->next;
    val = head->inf;
    head = s;
    free(s);
}
 
int main()
{
    char key;
    
    do
    {
        cout << "    STACK\n1 - push elements;\n2 - pop and write elements;\n3 - exit program\nPress key 1..3 ";
        key = getchar();
        cout << key << endl;
        switch (key)
        {
            case '1':
                int n, a;
                cout << "\nenter number of elements ";
                cin >> n;
                for (int i = 0; i < n; ++i)  {
                    cin >> a;
                    push(a);
                }
                break;
            case '2':
                while (head != NULL)
                {
                    int a;
                    pop(a);
                    cout << a;
                }
        }
    }
    while (key != '3');
    
    getchar();    
    return 0;
}

/*
Я никак не могу реализировать полноценный стек не используя масив,
у меня есть такой код , но он не пашет, что и не странно, 
так как о ссылках у нас была лекция только по паскалю, 
а как это реализуруется на си/си++ не знаю..
Если кто может дать ссылку на сответсвтующие материалы 
и растолковать буду весьма благодарен..
*/
#include<iostream>
#define UT unsigned short int
struct nodes
{
    UT data;
    nodes* prior;
};
 
class stacks
{
    public:
        stacks(){top = NULL;}
        ~stacks(){}
        void push(UT data)
        {
            nodes* tmp = new nodes;
            tmp->prior = top;
            tmp->data = data;
            top = tmp;
        }
        
        void pop(UT *p)
        {
            *p = top->data;
            nodes* tmp;
            tmp = top;
            top = top->prior;
            delete tmp;         
        }
        
        void clear()
            {
                if (top==NULL) return;
                nodes* tmp = top;
                while (true)
                {
                    if(top->prior!=NULL) 
                        {
                            tmp = top;
                            top = top->prior;
                            delete tmp; 
                        }
                    else {  delete top;  break; }
                }
            }
        
        bool empty(){return (top==NULL);} 
    private:
        nodes* top;
};
 
stacks a;
 
int main()
{
    using namespace std;
    char key;
while(true)
{
    system("cls");
    cout<<"STACK:\n 1 - push;\n 2 - pop & write;\n 3 - exit.\n";
    cin>>key;
    switch(key)
    {
        case '1':
            {
                cout<<"\n pushing:\n input element:   ";
                UT d;
                cin>>d;
                a.push(d);
                cout<<"\t OK!!\n";
                break;
            }
        case '2':
            {
                cout<<"\n poping:\n";
                UT tmp;
                if(a.empty()) cout<<"\n is empty";
                while(!a.empty()) {a.pop(&tmp);cout<<tmp<<endl;}
                cout<<"\t\t\t\t OK!!\n";
                system("pause");
                break;
            }
        case '3':{cout<<"\n exiting: "; goto end;}
        default: {cout<<"\n input 1, 2 or 3, please...\n";system("pause");}
    }
}
 
end:        
    a.clear();
    cout<<"\texit is correct."<<endl;
    system("pause");
    return 0;
}

#include <iostream>
#include <string>
 
using namespace std;
 
struct node
{
    int inf;
    node* L, R;
};
 
class BinTree
{
public:
    BinTree(){root = NULL;}
    ~BinTree(){}
    node* push(int n)
    {
        if (n)
            return NULL;
        int l = n/2,
            r = n - l - 1,
            data;
        cin >> data;
        node* newroot = new node;
        newroot->L = push(l);
        newroot->inf = data;
        newroot->R = push(r);
        return newroot;
    }
private:
    node* root;
};
 
BinTree T;
 
int main()
{
    int n;
    cin >> n;
    T.push(n);
    return 0;
}

template <typename T>
struct node
{
    T inf;
    node<T>* next;
};
 
template <typename T>
class mstack
{
private:
    node<T>* head;
public:
    mstack(){head = NULL;}
    ~mstack(){}
    
    void push(T &val)
    {
        node<T>* tmp = new node<T>;
        tmp->inf = val;
        tmp->next = head;
        head = tmp;
    }
    
    void clear()
    {
        while (head->next != NULL)
        {
            node<T>* tmp = head;
            head = head->next;
            delete tmp;
        }
        head = NULL;
    }
    
    bool empty(){return (head == NULL);}
    
    T pop()
    {
        T res = head->inf;
        node<T>* tmp = head;
        head = head->next;
        delete tmp;
        return res;
    }
};

#include <iostream>
#include <string>
#include "mstack.hpp"
 
using namespace std;
 
int main()
{
    mstack <string> s;
    int key;
    string val;
    do
    {
        system("cls");
        cout << "\tStack\t\t\t\tmade by TFTM\n\n";
        cout << "1 - push\n";
        cout << "2 - pop & write\n";
        cout << "3 - exit\n\n";
        cout << "press key: ";
        cin >> key;
        switch (key)
        {
            case 1:
                {
                    cout << "\nenter element: ";
                    cin >> val;
                    s.push(val);
                    break;    
                }
            case 2:
                {
                    if (s.empty()) cout << "stack is empty..";
                    else
                    {
                        cout << "poping:\n";
                        while (!s.empty())
                            cout << s.pop() << endl;
                    }
                    system("pause");
                    break;    
                }
            default:
                {
                    if (key == 3) cout << "exiting succesfully..\n";
                    else cout << "press only 1, 2 or 3\n";
                    system("pause");
            }                
        }
    }
    while (key != 3);
    
    return 0;
}