// пример работы со стеком
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <locale.h>

struct zap
{
    char inf[50];                   // информациое поле
    zap *l;                         // поле адреса
};
void push(zap **);
char* pop(zap **);
void show(zap *);
void sort1(zap *);
void sort2(zap **);

int main()
{
    setlocale(LC_ALL, "Russian");
    zap *s = nullptr;              // указатель на вершину стека
    char l, ss[50];
    while (1)
    {
        puts("\nвид операции:\n  1-создать/добавить\n  2-удалить");
        puts("  3-просмотреть\n  4-сортировка 1\n  5-сортировка 2");
        puts("  0-кончить");
        fflush(stdin);
        l = getch();
        switch (l)
        {
            case '1': push(&s); break;
            case '2': if(s)
                      {  strcpy(ss, pop(&s));
                         printf("%s", ss);
                      }
                      else puts("стек пуст");
                      break;
            case '3': show(s); break;
            case '4': if (s) sort1(s); break;
            case '5': if (s) sort2(&s); break;
            case '0': return 0;
            default: printf("Ошибка, повторите \n");
        }
    }
    return 0;
}

// функция cоздания/добавления в стек
void push(zap **s)
{
    zap *s1 = *s;
    do
    {
        if(!(*s = (zap *)calloc(1, sizeof(zap))))  // указатель на новый элемент стека
        {
            puts("Нет свободной памяти");
            return;
        }
        puts("Введите информацию в поле inf");
        fflush(stdin);
        gets_s((*s)->inf);
        (*s)->l = s1;              // новый эл-т стека "ссылается" на элемент вершину стека
        s1 = *s;                   // новый элемент становится вершиной стека
        puts("Продолжить (y/n)");
        fflush(stdin);
    } while (getch() == 'y');
}

// функция просмотра элементов стека
void show(zap *s)
{
    if(!s)
    {
        puts("Стек пуст");
        return;
    }
    do
    {
        printf("    %s\n", s->inf);  // вывод информационного поля пекущего эл-та стека
        s = s->l;                    // переход "вниз" к предыдущему эл-ту стека
    } while (s);
}

// функция удаления последнего элемента стека
// (с вершины стека)
char* pop(zap **s)
{
    zap *s1, ss;
    //char st[50];
    //strcpy(st, (*s)->inf);  // в st копируется содержимое информ. поля с вершины стека
    s1 = *s;                // запоминаем указатель на вершину стека
    ss = **s;               // запоминаем содержимое вершины стека
    *s = (*s)->l;           // указатель передвигаем "вниз" по стеку
    free(s1);               // удаляем элемент с вершины стека
    return ss.inf;
}

// функция сортировки элементов списка организованного
// в виде перестановкой содержимого элементов стека
void sort1(zap *s)
{
    zap *s1, *s2;
    char inf[50];
    for (; s->l; s = s->l)                // выбор элемента списка к упорядочиванию
    {
        s1 = s;                           // запиминаем адрес выбранного элемента списка
        for (s2 = s->l; s2; s2 = s2->l)   // перебор эл-тов списка "ниже" выбранного
        if (strcmp(s1->inf, s2->inf)>0)   // найден элемент s2 с меньшим значением
            s1 = s2;                      // запоминаем найденный элемент списка
        if (s1 != s)                      // т.е. был найден элемент с меньшим значением
        {                                 // чем выбранный s
            strcpy(inf, s1->inf);         // замена содержимого s <-> s1
            strcpy(s1->inf, s->inf);
            strcpy(s->inf, inf);
        }
    }
}

// функция сортировки элементов списка организованного
// в виде стека изменением указателей элементов стека
void sort2(zap **s)
{
    zap *ss, *s1, *s2, *s3, *s4 = NULL;
    ss = (zap *)calloc(1, sizeof(zap));
    ss->l = *s;                              // доп. элемент указывает на вершину стека
    for (; ss->l->l;)                        // цикл ДО последнего эл-та списка
    {
        s1 = ss->l;                          // выбор элемента списка к упорядочиванию
        for (s2 = ss->l; s2->l; s2 = s2->l)  // перебор последующих эл-тов списка ДО последнего
        if (strcmp(s1->inf, s2->l->inf)>0)   // сравнение содержимого двух эл-тов списка
        {                                    // найдено новое меньшее значение
            s1 = s2->l;                      // адрес текущего минимального эл-та
            s3 = s2;                         // адрес элемента перед минимальным
        }
        if (s1 != ss->l)                     // найденный меньший не совпадает с выбранным
        {
            s3->l = s1->l;                   // исключение из списка найденного меньшего
            s1->l = ss->l;                   // меньший "вставляется" перед выбранным
            ss->l = s1;                      // предыдущий перед выбранным указывает на найденный меньший
        }
        if (!s4) s2 = ss;
        ss = ss->l;                         // переход к следующему упорядочиваемому эл-ту
        if (!s4)
        {
            free(s2);                       // удаление дополнительного (временного) элемента
            *s= s4 = s1;                    // новая вершина стека
        }
    }
}