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

Перед удалением звена из стека проверяем, пуст ли стек.

Пусть стек не пуст.

Рис.1. Исходный стек

Тогда спокойно приступаем к удалению.

Сохраняем удаляемый элемент:
```
    klad = (*stk).elem;
```
Рис.2. Сохранение удаляемого элемента
"Перенастраиваем" указатель стека и сохраняем адрес удаляемого элемента:
```
    q = stk; stk = (*stk).sled;
```
Рис.3. "Перенастройка" указателя стека
Возвращаем память в кучу:
```
    delete q;
```
Рис.4. Возврат памяти в кучу

Запишем полученный алгоритм в виде функции:

void YDALENIE (node **stk, int klad)
// Удаление звена  из  стека, заданного указателем  *stk, и
// помещение значения информационного поля удаленного звена
// в параметр klad.
{
  node *q;

  if (*stk==NULL) cout<<"Стек пуст!\n";
  else
    { *klad = (**stk).elem; q = *stk; 
      *stk = (**stk).sled; delete q;}
}

Приведем пример программы, реализующей действия со стеком. Формирование и вывод содержимого стека на экран дисплея. Удаление и вставка звена в стек.

#include<iostream.h>
struct node
{
  int elem;
  node *sled;
};
class Spisok
{
  private:
    node *stk;
    int klad;
  public:
    Spisok () { stk=NULL; }
    int Set_Stack () {return klad;}
    void POSTROENIE();
    void VYVOD();
    void W_S(int);
    void YDALENIE ();
    void OCHISTKA();
};

void main ()
{
  Spisok A;
  int  el;
  int t; //Содержимое информационного поля верхушки стека.

  A.POSTROENIE (); A.VYVOD ();
  cout<<"Введите вставляемый элемент: ";
  cin>>el;
  A.W_S (el); A.VYVOD ();

  cout<<"Удалим элемент из стека.\n";
  A.YDALENIE ();
  t=A.Set_Stack();
  cout<<"Из стека было извлечено число... "<<t<<endl;
  A.VYVOD ();
  A.OCHISTKA();
}

void Spisok::POSTROENIE ()
//Построение стека, заданного указателем stk. 
{
  node *t;
  int el;

  cout<<"Вводите элементы стека: ";
  cin>>el;
  while  (el!=0)
  {
     t = new (node);
    (*t).elem = el; (*t).sled = stk;
    stk = t; cin>>el;
  }
}

void Spisok::VYVOD ()
//Вывод содержимого стека, заданного указателем stk.
{
  node *t;

  cout<<"Содержимое стека: "; t = stk;
  while  (t!=NULL)
    {cout<<(*t).elem<<" "; t = (*t).sled;}
  cout<<endl;
}

void Spisok::W_S (int el)
//Помещение элемента el в стек stk.
{
  node *q;

  q = new (node);
  (*q).elem = el; (*q).sled = stk; stk = q;
}

void Spisok::YDALENIE ()
//Удаление элемента из стека, заданного указателем stk.
//Значение информационного поля удаляемого элемента 
//помещается в параметр klad.
{
  node *q;

  if  (stk==NULL)
    cout<<"Стек пуст!\n";
  else
  {
    klad = (*stk).elem; q = stk;
    stk = (*stk).sled; delete q;
  }
}

void Spisok::OCHISTKA()
//Возврат выделенной памяти в "кучу".
{
  node *t,*q;

  t = stk;
  if (t!=NULL)
  {
    q=(*t).sled;
    while  (q!=NULL)
    {
      delete t; t = q; q =(*q).sled;
    }
    delete t;
  }
}

Текст этой программы можно взять здесь.

Со следующего шага мы познакомимся с деком.

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