Стек и очередь в Си

В языке Си (не С++) нет таких конструкций как класс и соответственно нет класса для работы с очередью и стеком. Но есть тип struct (структура), которая похожа на тип class, но без возможности включения методов (функций) в него. С помощью структуры можно описать все динамические структуры: стек, очередь, дек, списки, деревья.

В Си для выделения динамической памяти используется функция malloc, а для освобождения - функция free. В С++ для этих целей используется оператор new и delete соответственно.

Рассмотрим следующую задачу:
Дан набор числовых и символьных величин. Все числа целые, а символ всегда один. Символы и числа разделены одним пробелом. Необходимо вывести числа в обратном порядке, а символы - как они поступали на вход, т.е. в прямом порядке.

В этой задаче сформулируем несколько алгоритмических проблем:

1. Как прочитать все данные, где будет конец ввода?
2. Как отделить числа от символов? А если число состоит из нескольких цифр или оно отрицательное?
3. Как вывести в обратном и прямом порядке? Какие динамические структуры нам в этом помогут?

Начнем отвечать на вопросы и составлять алгоритм.

1. Как прочитать все данные, где будет конец ввода?

В задаче не указано, когда закончиться набор данных, но можно предположить, что данные могут храниться в файле. Тогда считываем данные до конца файла (код конца файла можно определить с помощью функции EOF()). А если этот ввод производить с клавиатуры - то можно ввести код конца файла Ctrk+Z и Enter.
В более простом случае - можно вводить только строку. Тогда кодом конца строки будет символы с кодом 10 и 13, и на клавиатуре - это клавиша Enter. Для такой реализации можно в цикле while считывать символы последовательно до тех пор, пока символы с кодом 10 и 13 не обнаружатся. А можно просто считать всю строку с помощью функции gets(адрес начала строки) и далее в цикле for просматривать все символы последовательно до полученной длины строки.

2. Как отделить числа от символов? А если число состоит из нескольких цифр или оно отрицательное?

В этом случае посимвольное чтение символов должно сопровождаться проверкой, что:

• первый символ может быть минусом, после которого стоит любая цифра;
• цифра - это символ, который принадлежит диапазону от '0' до '9';
• после числа стоит один пробел.

Все эти условия можно проверить последовательно, используя некий флаг - переменная отвечающая за то, что мы считываем число, и "собирать" в числовую строку, которую потом с помощью функции atoi можно преобразовать в целый тип. Если флаг нулевой, то это не число. Важно после цикла проверить этот флаг, так как может оказаться, что последним был введен не символ, а число. И необходимо его сохранить. 

3. Как вывести в обратном и прямом порядке? Какие динамические структуры нам в этом помогут?

Если нужно вывести в обратном порядке, то это стек, а если в прямом, то - очередь. 

Реализация стека:

Опишем структуру (struct) данных, которая содержит информационную часть (то, что хранится в стеке) и указатель (адрес ячейки) на следующий элемент в стеке. 

struct STACK
{
  int a;
  struct STACK *next;
};

Кроме этого нужна переменная - указатель на начало (верхушка) стека. В начале программы указатель ни на что не указывает и имеет нулевой адрес NULL.

struct STACK *top=NULL;

Напишем два метода (функции): добавить/затолкать элемент (push) и удалить/вытолкнуть (pop) элемент.

Добавление элемента в стек:

void push(int c, struct STACK **b)

{
  struct STACK *temp = (struct STACK*) malloc(sizeof(struct STACK));

  temp->a = c;
  temp->next = (*b);
  (*b) = temp;
}

Удаление элемента из стека:
int pop(struct STACK **t)
{
  if ((*t)!=NULL)
  {
    struct STACK *temp=(*t);
    int a = (*t)->a;
    (*t) = (*t)->next;
    free(temp);
    return a;
  }
  else
    return 0;
}

Реализация очереди:

Опишем структуру (struct) данных, которая содержит информационную часть (то, что хранится в очереди) и указатель (адрес ячейки) на следующий элемент в очереди.

struct QUEUE
{
  char a;
  struct QUEUE *next;
};

Кроме этого нужны две переменные - указатель на начало (голова) очереди и конец (хвост) очереди. В начале программы указатели ни на что не указывают и имеют нулевой адрес NULL.

struct QUEUE *head=NULL, *tail=NULL;

Напишем два метода (функции): добавить/затолкать элемент в конец очереди (push_back) и удалить/вытолкнуть элемент из начала очереди (pop_front).

Поставить в очередь:

void push_back(char c, struct QUEUE **b)
{
  if((*b)!=NULL)
  {
    struct QUEUE *temp=(struct QUEUE*) malloc(sizeof(struct QUEUE));
    temp->a = c;
    temp->next = NULL;
    (*b)->n=temp;
    (*b)=temp;
  }
  else
  {
    (*b) = (struct QUEUE*) malloc(sizeof(struct QUEUE));
    (*b)->a = c;
    (*b)->next = NULL;
     head=(*b);
  }
}

Удалить из очереди:

char pop_front(struct QUEUE **t)
{

  if ((*t)!=NULL)
  {
    struct QUEUE *temp=(*t);
    char a = (*t)->a;
    (*t) = (*t)->next;
    free(temp);
    return a;
  }
  else
    return 0;
}

Вывод в прямом и обратном порядке соответствует операции удаления (выталкивания) элемента из очереди или стека соответственно до тех пор, пока не будет элементов или пока указатель на начало очереди или стека не станет нулевым (пока не на что будет указывать):

    while(head!=NULL)
        printf("%c ", pop_front(&head));

    while(top!=NULL)
        printf("%d ", pop(&top));

Приведем полный код программы:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

struct STACK
{
    int a;
    struct STACK *next;

};
struct STACK *top=NULL;

void push(int c, struct STACK **b)

{
        struct STACK *temp = (struct STACK*) malloc(sizeof(struct STACK));

        temp->a = c;
        temp->next = (*b);
        (*b)=temp;
}
int pop(struct STACK **t)

{
    if ((*t)!=NULL)
    {
        struct STACK *temp=(*t);

        int a = (*t)->a;
        (*t) = (*t)->next;
        free(temp);
        return a;
    }
    else
        return 0;
}

struct QUEUE
{
    char a;
    struct QUEUE *next;

};

struct QUEUE *head=NULL, *tail=NULL;

void push_back(char c, struct QUEUE **b)

{
    if((*b)!=NULL)
    {
        struct QUEUE *temp=(struct QUEUE*) malloc(sizeof(struct QUEUE));

        temp->a = c;
        temp->next = NULL;
        (*b)->next=temp;
        (*b)=temp;
    }
    else
    {
        (*b) = (struct QUEUE*) malloc(sizeof(struct QUEUE));
        (*b)->a = c;
        (*b)->next = NULL;
        head=(*b);
    }
}
char pop_front(struct QUEUE **t)

{
    if ((*t)!=NULL)
    {
        struct QUEUE *temp=(*t);

        char a = (*t)->a;
        (*t) = (*t)->next;
        free(temp);
        return a;
    }
    else
        return 0;
}

int main()
{
    char c[200], str[10];
    gets(c);
    int a, k=0;
    for (int i=0; i<strlen(c); i++)
    {
        if (c[i]=='-' && c[i+1]>='0' && c[i+1]<='9' && k==0) k=1;
        else
        if (c[i]>='0' && c[i]<='9') k=1;
        else
        if (c[i]==' ' && k==1)
        {
            k=0;
            strncpy(str,c,i+1);
            strcpy(c,&(c[i+1]));
            i=-1;
            a=atoi(str);
            push(a,&top);
        }
        else
        {
            if (c[i]!=' ') push_back(c[i], &tail);
            strcpy(c,&(c[i+1]));
            i=-1;
        }

    }
    if(k==1)
    {
        a=atoi(c);
        push(a,&top);
    }

    while(head!=NULL)
        printf("%c ", pop_front(&head));

    while(top!=NULL)
        printf("%d ", pop(&top));

    return 0;
}