C++,Visual C++,Теорія

C++. Розробка шаблонного класу, що реалізує стек у вигляді однозв’язного списку




Розробка шаблонного класу, що реалізує стек у вигляді однозв’язного списку

Зміст

Пошук на інших ресурсах:

1. Переваги реалізації стеку у вигляді однозв’язного списку порівняно з динамічним масивом

Реалізація динамічної структури даних стек у вигляді однозв’язного списку має наступні переваги:

  • потреби у меншому об’ємі пам’яті у випадку додавання нового елементу. В однозв’язному списку додаткова пам’ять для елементу виділяється тільки для цього одного елементу. У динамічному масиві спочатку потрібно виділити новий фрагмент (масив) пам’яті для усіх елементів, потім здійснити копіювання старого масиву в новий і тоді звільнити пам’ять, виділену під старий масив. Зі зростанням кількості елементів у стеку ця переваги стає більш відчутною;
  • менша кількість додаткових операцій у випадку маніпулювання стеком (додавання нового елементу, видалення елементу).

Недоліки:

  • складність реалізації. Обробку однозв’язного списку складніше реалізувати;
  • для доступу до i-го елементу в динамічному масиві зручно використовувати доступ за індексом. В однозв’язному списку потрібно переглядати (прокручувати) увесь список від початку до потрібної позиції.

  ⇑

2. Структура NodeStack, що описує вузол

Будь-який однозв’язний (двохзв’язний) список базується на спеціальній структурі або класі, що описує один вузол (рисунок 1).

C++. Вузол у випадку однозв’язного списку: item – елемент даних, next – покажчик на структуру NodeStack

Рисунок 1. Вузол у випадку однозв’язного списку: item – елемент даних, next – покажчик на структуру NodeStack

У вузлі (структурі) виділяються два елементи:

  • елемент даних item деякого узагальненого типу T;
  • покажчик на наступний елемент типу NodeStack<T>.

На мові C++ оголошення структури NodeStack має наступний вигляд

// Структура, що описує вузол
template <typename T>
struct NodeStack
{
  T item;
  NodeStack<T>* next;
};

  ⇑

3. Реалізація стеку у вигляді однозв’язного списку (рисунок)

На рисунку 2 відображено стек у вигляді однозв’язного списку

C++. Стек як однозв’язний список

Рисунок 2. Стек як однозв’язний список

Вершина стеку – покажчик pTop. В останньому вузлі стеку значення next = nullptr.




  ⇑

4. Текст програми

У програмі реалізується шаблонний клас StackList, який реалізує стек у вигляді однозв’язного списку. За бажанням у текст класу можна додати інші функції що розширять його можливості.
У класі оголошуються наступні поля та методи:

  • покажчик pTop, що є вершиною стеку;
  • конструктор за замовчуванням;
  • конструктор копіювання StackList(const StackList&);
  • деструктор;
  • метод Push(), що поміщає елемент в стек;
  • метод Pop() – витягує елемент зі стеку;
  • метод Count() – повертає кількість елементів у стеку;
  • метод Empty() – видаляє усі елементи зі стеку;
  • оператор копіювання operator=(const StackList&) – необхідний для реалізації коректного присвоєння об’єктів класу StackList;
  • метод Print(), що виводить вміст стеку на екран.

Повний текст класу StackList та структури NodeStack наступний

#include <iostream>
using namespace std;

// Структура, що описує вузол
template <typename T>
struct NodeStack
{
  T item;
  NodeStack<T>* next;
};

// Шаблонний клас Стек на основі однозв'язного списку
template <typename T>
class StackList
{
private:
  NodeStack<T>* pTop; // покажчик на вершину стеку

public:
  // конструкто за замовчуванням
  StackList() { pTop = nullptr; }

  // конструктор копіювання
  StackList(const StackList& SL)
  {
    NodeStack<T>* p; // додаткові покажчики
    NodeStack<T>* p2;
    NodeStack<T>* p3;

    // Ініціалізувати pTop
    pTop = nullptr;
    p3 = nullptr;

    p = SL.pTop; // покажчик p рухається по списку SL.pTop->...
    while (p != nullptr)
    {
      // 1. Сформувати вузол p2
      try {
        // спроба виділення пам'яті
        p2 = new NodeStack<T>;
      }
      catch (bad_alloc e)
      {
        // якщо пам'ять не виділена, то вихід
        cout << e.what() << endl;
        return;
      }

      p2->item = p->item;
      p2->next = nullptr;

      // 2. pTop = pTop + p2
      if (pTop == nullptr) // створити чергу
      {
        pTop = p2;
        p3 = p2;
      }
      else
      {
        p3->next = p2;
        p3 = p3->next;
      }

      // 3. Перейти на наступний елемент
      p = p->next;
    }
  }
  // помістити елемент у стек
  // елемент поміщається на початок списку
  void Push(T item)
  {
    NodeStack<T>* p;

    // 1. Сформувати елемент
    try {
      p = new NodeStack<T>; // спроба виділити пам'ять
    }
    catch(bad_alloc e)
    {
      // якщо пам'ять не виділилась, то вихід
      cout << e.what() << endl;
      return;
    }

    p->item = item;
    p->next = pTop; // p вказує на 1-й елемент

    // 2. Перенаправити pTop на p
    pTop = p;
  }

  // К-сть елементів у стеку
  int Count()
  {
    if (pTop == nullptr)
      return 0;
    else
    {
      NodeStack<T>* p = pTop;
      int count = 0;
      while (p != nullptr)
      {
        count++;
        p = p->next;
      }
    }
  }

  // очищує стек - видаляє усі елементи зі стеку
  void Empty()
  {
    NodeStack<T>* p; // додатковий покажчик
    NodeStack<T>* p2;

    p = pTop;
    while (p != nullptr)
    {
      p2 = p; // зробити копію з p
      p = p->next; // перейти на наступний елемент стеку
      delete p2; // видалити пам'ять, виділену під попередній елемент
    }
    pTop = nullptr; // поправити вершину стеку
  }

  // оператор копіювання
  StackList<T>& operator=(const StackList<T>& LS)
  {
    // чи є елементи в стеку?
    if (pTop != nullptr) Empty();

    NodeStack<T>* p; // додатковий покажчик
    NodeStack<T>* p2;
    NodeStack<T>* p3;

    // Ініціалізувати pTop
    pTop = nullptr;
    p3 = nullptr;

    p = LS.pTop; // покажчик p рухається по списку SL.pTop->...
    while (p != nullptr)
    {
      // 1. Сформувати вузол p2
      try {
        // спроба виділити пам'ять
        p2 = new NodeStack<T>;
      }
      catch (bad_alloc e)
      {
        // якщо пам'ять не виділена, то вихід
        cout << e.what() << endl;
        return *this;
      }
      p2->item = p->item;
      p2->next = nullptr;

      // 2. pTop = pTop + p2
      if (pTop == nullptr) // створити чергу
      {
        pTop = p2;
        p3 = p2;
      }
      else
      {
        p3->next = p2;
        p3 = p3->next;
      }

      // 3. Перейти на наступний елемент
      p = p->next;
    }
    return *this;
  }

  // вивід стеку
  void Print(const char* objName)
  {
    cout << "Object: " << objName << endl;

    if (pTop == nullptr)
      cout << "stack is empty." << endl;
    else
    {
      NodeStack<T>* p; // додатковий покажчик
      p = pTop;
      while (p != nullptr)
      {
        cout << p->item << "\t";
        p = p->next;
      }
      cout << endl;
    }
  }

  // деструктор
  ~StackList()
  {
    Empty();
  }

  // метод, що витягує елемент зі стеку - працює
  T Pop()
  {
    // перевірка, чи стек порожній
    if (pTop == nullptr)
      return 0;

    NodeStack<T>* p2; // додатковий покажчик
    T item;
    item = pTop->item;

    // перенаправити покажчики pTop, p2
    p2 = pTop;
    pTop = pTop->next;

    // Звільнити пам'ять, виділену під 1-й елемент
    delete p2;

    // повернути item
    return item;
  }
};

void main()
{
  StackList<int> SL;
  SL.Print("SL");

  SL.Push(8);
  SL.Push(5);
  SL.Push(10);
  SL.Push(7);
  SL.Print("SL");

  // перевірка конструктора копіювання
  StackList<int> SL2 = SL;
  SL2.Print("SL2");

  SL.Empty();
  SL.Print("SL");

  SL = SL2;
  SL.Print("SL = SL2");

  StackList<int> SL3;
  SL3.Push(1);
  SL3.Push(2);
  SL3.Push(3);
  SL3.Print("SL3");

  SL = SL2 = SL3;
  SL.Print("SL");
  SL2.Print("SL2");

  int d = SL2.Pop();
  cout << "d = " << d << endl;
  SL2.Print("SL2-1");

  d = SL2.Pop();
  SL2.Print("SL2-2");

  d = SL2.Pop();
  SL2.Print("SL2-3");

  d = SL2.Pop();
  cout << "d = " << d << endl;
  SL2.Print("SL2----");
}

  ⇑

5. Результат роботи програми
Object: SL
stack is empty.
Object: SL
7 10 5 8
Object: SL2
7 10 5 8
Object: SL
stack is empty.
Object: SL = SL2
7 10 5 8
Object: SL3
3 2 1
Object: SL
3 2 1
Object: SL2
3 2 1
d = 3
Object: SL2-1
2 1
Object: SL2-2
1
Object: SL2-3
stack is empty.
d = 0
Object: SL2----
stack is empty.

  ⇑

6. Особливості програмної реалізації
6.1. Виділення пам’яті для елементу стеку

Виділення пам’яті для вузла виконується з допомогою оператора new. Однак можливий випадок, що пам’ять не виділиться. У цьому випадку буде згенероване виключення типу bad_alloc. Тип bad_alloc є класом. У програмі для обробки цієї ситуації використовується наступний блок try…catch:

try {
  p = new NodeStack<T>; // спроба виділити пам'ять
}
catch (bad_alloc e)
{
  // якщо пам'ять не виділилась, то вихід
  cout << e.what() << endl;
  return;
}

Якщо пам’ять для покажчика p не виділилась, то вивести відповідне системне повідомлення можна з допомогою методу what() класу bad_alloc.

  ⇑

6.2. Очищення стеку. Метод Empty()

Очищення стеку реалізоване в методі Empty(). Щоб очистити стек потрібно в циклі звільнити пам’ять для кожного елементу в стеку як показано нижче

void Empty()
{
  NodeStack<T>* p; // додатковий покажчик
  NodeStack<T>* p2;

  p = pTop;
  while (p != nullptr)
  {
    p2 = p; // зробити копію з p
    p = p->next; // перейти на наступний елемент стеку
    delete p2; // видалити пам'ять, виділену під попередній елемент
  }
  pTop = nullptr; // поправити вершину стеку
}

  ⇑

6.3. Конструктор копіювання та оператор копіювання

Оскільки пам’ять в класі StackList виділяється динамічно, то в цьому класі обов’язково потрібно реалізовувати власний конструктор копіювання та оператор копіювання щоб уникнути недоліків побітового копіювання. Більш детально про конструктор копіювання можна прочитати тут. Оператор копіювання необхідний для правильного присвоювання об’єктів класу StackList.

  ⇑

Зв’язані теми

  ⇑