Динамические структуры данных - стек
Работа с памятью при использовании динамических структур
В программах, в которых необходимо использовать динамические структуры данных, работа с памятью происходит стандартным образом. Выделение динамической памяти производится с помощью операции new или с помощью библиотечной функции malloc (calloc). Освобождение динамической памяти осуществляется операцией delete или функцией free.
Например, объявим динамическую структуру данных с именем Node с полями Name, Value и Next, выделим память под указатель на структуру, присвоим значения элементам структуры и освободим память.
struct Node {char *Name;
int Value;
Node *Next
};
Node *PNode; //объявляется указатель
PNode = new Node; //выделяется память
PNode->Name = "STO"; //присваиваются значения
PNode->Value = 28;
PNode->Next = NULL;
delete PNode; // освобождение памяти
Стеком называется динамическая структура данных, добавление компонента в которую и исключение компонента из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу LIFO (Last-In, First-Out)- «последний вошел - первый вышел».
Замечание. Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно сначала взять верхнюю (рис. 3).
Взять элемент можно только из вершины стека, добавить элемент можно только в вершину стека. Например, если записаны в стек числа 1, 2, 3, то при последующем извлечении получим 3,2,1.
Рис. 3. Стек и его организация.
Обычно над стеками выполняется три операции:
- начальное формирование стека (запись первого компонента);
- добавление компонента в стек;
- выборка компонента (удаление).
Для формирования стека и работы с ним необходимо иметь две переменные типа указатель (ph, px), первая из которых (ph) определяет вершину стека, а вторая – вспомогательная (px) необходимая для добавления компонента в стек.
Описание компонента (элемента, объекта) стека выглядит следующим образом:
struct имя_типа
{
информационное поле;
адресное поле;
};
где информационное поле – это поле любого ранее объявленного или стандартного типа (поле данных);
адресное поле – это указатель на следующий компонент (объект) стека. В него записывается адрес следующего элемента стека.
Например:
struct pointer
{
int d;
pointer *p;
};
pointer ph, px;
Здесь, указатель ph указывает на вершину стека, а указатель px - необходим для добавления нового компонента в стек.
Рассмотрим основные операции при работе со стеком.
1. Формирование стека.
Начальное формирование стека выполняется несколькими операторами:
- выделение в динамической памяти места под первый компонент стека и запись адреса этого компонента в переменную ph:
*ph = new pointer;
 |
- запись в поле d некоторых данных – D1:
ph->d = D1;
- запись в поле p нулевого адреса (NULL):
ph->p = NULL;
 |
2. Добавление компонента в стек.
Добавление компонента в стек осуществляется с вершины стека, при помощи дополнительного указателя – px:
- выделение в динамической памяти места под новый компонент стека и запись адреса этого компонента в переменную px:
*px = new pointer;
 |
- запись в поле d указателя px некоторых данных – D2:
px->d = D2;
 |
- запись в поле p, указателя px, адреса предыдущего компонента:
px->p = ph;
 |
- запись в указатель ph адреса последнего компонента;
ph = px;
 |
Добавление последующих компонентов осуществляется аналогично.
3. Исключение компонентов из стека.
Для исключения компонента из стека необходимо выполнить ряд операторов. Пусть к моменту выборки компонентов, в стек записано три компонента. Исключение компонентов из стека осуществляется из вершины стека.
 |
- первый оператор осуществляет чтение данных из компонента – вершины стека:
data = ph->d;
- смещение указателя на вершину стека (ph) на следующий компонент:
ph =ph->p;
 |
Повторив, указанные выше, два действия мы получим последовательно доступ ко всем компонентам стека. На практике эти два действия составляют тело цикла с предусловием (цикл while), в котором сначала проверяют условие (ph != NULL), а затем, выполняют исключение компонента из стека.
Рассмотрим реализацию этих операций в виде соответствующих функций.
Пример. Составить программу, которая формирует стек, добавляет в него произвольное количество компонентов, а затем читает все компоненты и выводит их на экран дисплея. В качестве данных взять целые числа. Ввод данных осуществляется до тех пор пока не введено число ноль (0).
#include <stdio.h>
#include <conio.h>
struct pointer //описание структуры компонента стека
{
int d;
pointer *p;
};
//прототипы используемых функций
pointer *formst(int data); //формирование стека
void dobst(pointer **pk, int d); //добавление в стек
int iskst(pointer **ph); //исключение из стека
//основная функция
void main()
{
clrscr();
int data; переменная для данных записываемых в стек
int i=1;
//формирование стека
printf("формирвание стека.\n");
printf("%d компонент ->",i);
scanf("%d",&data);
pointer *ph = formst(data);
//добавление в стек
printf("Добавление в стек. Концом ввода является ноль ( 0 ).\n");
do
{ i++;
printf("%d компонент ->",i);
scanf("%d",&data);
dobst(&ph,data);
}
while (data !=0); //концом ввода является ноль
printf("вывод стека на дисплей:\n");
i=0;
while (ph != NULL)
{
i++;
printf("%d компонент -> %d\n",i,iskst(&ph));
}
getch();
}
//------формирование первого элемента-----
pointer *formst(int d)
{
pointer *px = new pointer;
px->d = d; px->p = NULL;
return px;
}
//--- добавление элемента -----------------
void dobst(pointer **ph, int d)
{
pointer *px = new pointer;
px->d = d;
px->p = (*ph);
(*ph) = px;
}
//--исключение из стека-------------------
int iskst(pointer **ph)
{
int d=(*ph)->d;
(*ph)=(*ph)->p;
return d;
}