4.3. Стек

Применение указателей позволяет создавать различные динамические структуры для хранения данных. Наиболее простой из них является стек, представляющий собой последовательность объектов данных, связанных между собой с помощью указателей. Особенность организации структуры стека показана на рис. 4.4.

Рис. 4.4. Организация структуры стека

Из рис. 4.4 видно, что каждый объект стека связан с последующим с помощью указателя next. Если указатель next равен NULL, то достигнут конец стека. Особенность работы со стеком заключается в том, что новый объект всегда добавляется в начало списка. Удаление также возможно только для первого элемента. Таким образом, данная структура реализует очередь по принципу «первым вошел, последним вышел». Такой принцип характерен при вызове функций в рекурсии, когда адрес каждой последующей функции записывается в стеке для корректной передачи управления при ее завершении.

Для описания объектов составляющих стек можно воспользоваться структурами, например, следующее определение задает шаблон для описания объекта данных стека:

typedef struct tag_obj {
char name[100];
struct tag_obj* next;
} OBJ;

Здесь поле name – символическое имя объекта, а next – указатель на следующий объект. Зададим указатель top как глобальную переменную со значением равным NULL:

OBJ* top = NULL;

и введем функцию для добавления нового объекта в стек:

void push(char* name)
{
OBJ* ptr = (OBJ *)malloc(sizeof(OBJ));
strcpy(ptr->name,name);
ptr->next = top;
top = ptr;
}

Данная функция в качестве аргумента принимает указатель на строку символов, которые составляют имя добавляемого объекта. Внутри функции инициализируется указатель ptr на новый созданный объект. В поле name записывается переданная строка, а указатель next инициализируется на первый объект. Таким образом, добавленный объект ставится на вершину списка.

Для извлечения объекта из стека реализуется следующая функция:

void pop()
{
if(top != NULL)
{
OBJ* ptr = top->next;
printf("%s - deletedn",top->name);
free(top);
top = ptr;
}
}

В данной функции сначала выполняется проверка указателя top. Если он не равен значению NULL, то в стеке имеются объекты и самый верхний из них следует удалить. Перед удалением инициализируется указатель ptr на следующий объект для того, чтобы он был доступен после удаления верхнего. Затем вызывается функция printf(), которая выводит на экран сообщение об имени удаленного объекта. Наконец, вызывается функция free() для удаления самого верхнего объекта, а указатель top инициализируется на следующий объект.

Для анализа работы данных функций введем еще одну вспомогательную функцию, которая будет выводить имена объектов, находящихся в стеке.

void show_stack()
{
OBJ* ptr = top;
while(ptr != NULL)
{
printf("%sn",ptr->name);
ptr = ptr->next;
}
}

Работа данной функции реализуется с помощью цикла while, который работает до тех пор, пока указатель ptr не достигнет конца стека, т.е. пока не будет равен значению NULL. Внутри цикла вызывается функция printf() для вывода имени текущего объекта на экран и указатель ptr перемещается на следующий объект.

Рассмотрим применение данных функций в функции main():

int main()
{
char str[100];
for(int i = 0;i < 5;i++) {
sprintf(str,"Object %d",i+1);
push(str);
}
show_stack();
while(top != NULL) pop();
return 0;
}

Здесь создается стек, состоящий из 5 объектов, с помощью оператора цикла for. Внутри цикла инициализируется переменная str с именем объекта, которая, затем, передается в качестве аргумента функции push(). После вызова функции show_stack() на экране появляются следующие строки:

Object 5
Object 4
Object 3
Object 2
Object 1

Полученные результаты показывают, что последний 5-й добавленный объект находится на вершине стека, а первый – в конце. При вызове функции pop() в цикле while() осуществляется удаление элементов стека из памяти ЭВМ. В результате на экране появляются строки:

Object 5 - deleted
Object 4 - deleted
Object 3 - deleted
Object 2 - deleted
Object 1 – deleted

Таким образом, функция pop() удаляет верхние объекты стека с 5-го по 1-й.