Алгоритм формирования стека

Рассмотрим данный алгоритм для первых двух элементов.

1. Описание структуры переменной, содержащей информационное и адресное поля:

struct Stack ® info Next

Шаблон структуры рекомендуется описывать глобально:

struct Stack {

int info;

Stack *Next;

} ;

2. Объявление указателей на структуру:

Stack *begin (вершина стека), *t (текущий элемент);

3. Так как первоначально стек пуст: begin = NULL;

4. Захват памяти под первый (текущий) элемент:

t = (Stack*) malloc (sizeof(Stack)); или t = new Stack;

формируется конкретный адрес ОП (обозначим его А1) для первого элемента, т.е. t равен А1.

5. Ввод информации (например, i1);

а) формирование информационной части:

t -> info = i1;

б) формирование адресной части: значение адреса вершины стека записываем в адресную часть текущего элемента (там был NULL)

t -> Next = begin;

t ® info = i1 Next ® begin = NULL

6. Вершина стека переносится на созданный первый элемент:

begin = t;

в результате получается следующее:

begin (A1) ® info = i1 NULL

7. Захват памяти под второй элемент:

t = (Stack*) malloc (sizeof(Stack)); или t = new Stack;

формируется конкретный адрес ОП (A2) для второго элемента.

8. Ввод информации для второго элемента (i2);

а) формирование информационной части:

t -> info = i2;

б) в адресную часть записываем значение адреса вершины, т.е. адрес первого (предыдущего) элемента (А1):

t -> Next = begin;

t (A2) ® info = i2 Next = A1  

9. Вершина стека снимается с первого и устанавливается на новый элемент (A2):

begin = t;

получается следующая цепочка:

begin (A2) ® info = i2 Next = A1 ® info = i1 Next = NULL

Обратите внимание, что действия 7, 8, 9 идентичны действиям 4, 5, 6, т.е. добавление новых элементов в стек можно выполнять в цикле, до тех пор, пока это необходимо.

Функция формирования элемента стека для объявленного ранее типа данных может выглядеть следующим образом:

Stack* Create(Stack *begin) {

Stack *t = (Stack*)malloc(sizeof(Stack));

printf(“\n Input Info ”);

scanf(“%d”, &t -> info);

t -> Next = begin;

return t;

}

Участок программы с обращением к функции Create для добавление необходимого количества элементов в стек может иметь следующий вид:

¼

Stack *begin = NULL;

int repeat = 1;

while(repeat) { // repeat=1 – продолжение ввода данных

begin = Create(begin);

printf(“ Stop - 0 ”); // repeat=0 – конец ввода данных

scanf(“%d”, &repeat);

}

¼

Если в функцию Сreate указатель на вершину передавать по адресу и использовать для захвата памяти операцию new, то она может иметь следующий вид:

void Create(Stack **pt) {

Stack *t = new Stack;

printf(“\n Input Info ”);

scanf(“%d”, &t -> info);

t -> Next = *pt;

}

Обращение к ней в данном случае будет: Create(&begin);

Алгоритм извлечения элемента из стека

В данном алгоритме вершина begin не сдвигается.

1. Устанавливаем текущий указатель на вершину стека: t = begin;

2. Обрабатываем информационную часть текущего элемента (t ->info), например, выводим на экран.

3. Переставляем указатель текущего элемента на следующий элемент, адрес которого находится в адресной части текущего:

t = t->Next;

Просмотр стека

1. Устанавливаем текущий указатель на вершину t = begin.

2. Проверяем, если begin равен NULL, то стек пуст, выводим сообщение и либо завершаем работу, либо переходим на формирование стека.

3. Если стек не пуст, начинаем выполнять цикл до тех пор, пока текущий указатель t не равен NULL, т.е. пока не обработаем последний элемент, в адресной части которого находится значение NULL.

4. Выводим на экран информационную часть текущего элемента:

printf(“\n Элемент: %d”, t -> info); или cout << t->info;

5. Переставляем текущий указатель на следующий элемент:

t = t -> Next;

6. Конец цикла.

Функция просмотра стека без сдвига его вершины может выглядеть следующим образом:

void View(Stack *begin)

{

Stack *t = begin;

if(begin == NULL) {

puts(“ Стек пуст! ”);

return;

}

while( t != NULL) {

printf(“ %d \n”, t->info);

t = t -> Next;

}

}

Обращение к этой функции: View(begin);

Наши рекомендации