На этом шаге мы рассмотрим алгоритм формирования стека.

    Напомним, что стек - это специально организованная память, выборка и занесение данных в которую подчиняется дисциплине LIFO ("последним вошел - первым обслужен").

    Стек на базе линейного однонаправленного списка - линейный однонаправленный список, в котором все включения и исключения звеньев делаются в одном (выбранном нами) конце списка.

    Опишем алгоритм помещения в стек информации.

1. Вначале стек пуст:

       stk = NULL;
   

   
   Рис.1. Стек пуст

2. Содержимое стека будем вводить с клавиатуры, ввод заканчивается нулем:

       cin>>Элем;
       t = new (node);
       (*t).elem = Элем; (*t).sled = stk;
   

   
   Рис.2. Новый элемент

3. "Настраиваем" указатель стека на созданный элемент:

       stk = t;
   

   
   Рис.3. "Настройка" указателя стека

4. В результате в стек будет помещено первое звено:

   
   Рис.4. Первый элемент в стеке

5. Продолжим заполнение стека:

       cin>>Элем1;
       t = new (node);
       (*t).elem = Элем1;
       (*t).sled = stk;
   

   
   Рис.5. Размещение в стеке второго элемента

6. "Настраиваем" указатель стека на созданный элемент:

       stk = t;
   

   
   Рис.6. "Настройка" указателя стека

7. Теперь стек содержит уже два звена:

   
   Рис.7. В стеке два элемента

    Продолжение процесса построения стека достаточно очевидно.

    Оформим алгоритм в виде функции языка C++:

void POSTROENIE (node **stk)
//Построение стека, заданного указателем *stk с клавиатуры.
{
  node *t;
  int el;
  *stk = NULL;
  cin>>el;
  while (el!=0)
  {
    t = new (node);
    (*t).elem = el; (*t).sled = *stk; *stk = t; 
    cin>>el;
  }
}

    На следующего шаге мы рассмотрим алгоритм включения звена в стек.

Предыдущий шаг Содержание Следующий шаг