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

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

}