Динамические структуры данных - стек

Стеком называется динамическая структура данных, добавление компонента в которую и исключение компонента из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу 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;

}