Алгоритм формирования стека
Рассмотрим данный алгоритм для первых двух элементов.
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);