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

У даній роботі наведено приклад шаблонного класу Stack<T>, який реалізує стек у вигляді однозв’язного списку. Пройшовши покроково дану інструкцію можна отримати працездатний клас стеку.

Перед вивченням даної теми рекомендується ознайомитись з наступними темами:

Зміст

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

1. API класу Stack<T>. Вимоги клієнта

У даній статті стек реалізується в шаблонному класі Stack<T>. Для цього класу визначено наступний API:

Для коректної роботи класу (копіювання, звільнення пам’яті тощо) визначено загальнодоступні додаткові функції.

⇑

2. Програмний код класу Stack<T>

2.1. Оголошення пустого класу Stack<T>

На самому початку потрібно оголосити пустий шаблонний клас Stack<T>, який оперує узагальненим типом T:

#include <iostream>
using namespace std;

template <class T>
class Stack
{

};

⇑

2.2. Прихована структура Node<T>

У розділ private вводиться структура, яка описує один вузол в стеку. На рисунку 1 зображено вигляд структури

C++. Стек як однозв'язний список. Структура, що описує вузол Note<T>

Рисунок 1. Структура Node<T>

Програмний код структури в класі наступний

template <class T>
class Stack
{
private:
  // Внутрішня структура
  template <class T>
  struct Node
  {
    T data;
    Node<T>* next;
  };
};

⇑

2.3. Ввід внутрішніх полів head та size

У розділ private класу вводяться внутрішні поля, які мають наступне призначення:

head – покажчик на вершину стеку;
size – розмір стеку.

Фрагмент коду з введеними полями має наступний вигляд:

...

template <class T>
class Stack
{
private:

  ...

  Node<T>* head; // покажчик на вершину стеку
  unsigned int size; // розмір стеку
};

...

⇑

2.4. Внутрішня функція Copy()

В конструкторі копіювання та операторі копіювання потрібно виконувати операцію копіювання стеку з зовнішнього об’єкту у внутрішню структуру даних на яку вказує покажчик head (вершина стеку).

Тому, з метою оптимізації коду в розділ private класу потрібно ввести фунцію Copy()

private:

  ...

  // Функція Copy() - використовується, якщо потрібно
  // отримати копію стеку у внутрішні дані
  void Copy(Node<T>* _head)
  {
    // 1. Перевірка
    if (_head == nullptr)
      return;

    // 2. Додаткові змінні
    Node<T>* p = _head; // Встановити покажчик на вершину стеку
    bool f_first = true;
    Node<T>* p2 = nullptr;
    Node<T>* p3 = nullptr;

    // 2. Цикл обходу стеку
    size = 0; // к-сть елементів у стеку

    while (p != nullptr)
    {
      // 2.1. Виділити пам'ять і заповнити її значеннями
      try
      {
        p2 = new Node<T>;
        p2->data = p->data;
        p2->next = nullptr;

        // 2.2. Перевірка, чи додається перший елемент
        if (f_first)
        {
          // 2.3. Якщо додається перший елемент
          head = p2;
          p3 = p2;
          f_first = false;
        }
        else
        {
          // 2.4. Якщо додається не перший, то
          //      встановити покажчик next
          p3->next = p2;
          p3 = p3->next;
        }

        // 2.4. Збільшити кількість елементів
        size++;

        // 2.5. Перейти на наступний елемент
        p = p->next;
      }
      catch (bad_alloc e)
      {
        cout << e.what();
      }
    }
  }

⇑

2.5. Звільнення пам’яті, що була виділена під стек. Метод Free()

Важливою операцією є звільнення стеку, яке може викликатись з оператора присвоєння копіюванням та деструктора. Ця операція реалізується з допомогою private-функції Free().

...

private:

  ...

  // Метод, що звільняє пам'ять під стек
  void Free()
  {
    // 1. Встановити покажчик на вершину стеку
    Node<T>* p = head;

    // 2. Обхід стеку і звільнення пам'яті
    while (p != nullptr)
    {
      head = head->next;
      delete p;
      p = head;
      size--; // не обов'язково
    }
  }

⇑

2.6. Конструктор Stack()

У розділ public вводиться конструктор, який створює пустий стек.

public:

  // Створити пустий стек
  Stack()
  {
    head = nullptr;
    size = 0;
  }

⇑

2.7. Функція Push(). Додати елемент до стеку

Для додавання елементу в стек використовується функція Push(). Елемент додається до вершини стеку. Відповідно покажчик head зсувається.

public:

  ...

  // Додати елемент до стеку
  void Push(T item)
  {
    try
    {
      // 1. Якщо перший елемент
      if (size == 0)
      {
        head = new Node<T>;
        head->next = nullptr;
        head->data = item;
      }
      else
      {
        // 2. Якщо не перший елемент
        // 2.1. Створити нову комірку і заповнити її даними
        Node<T>* p2 = new Node<T>;
        p2->data = item;
        p2->next = nullptr;

        // 2.2. Перенаправити покажчики
        p2->next = head;
        head = p2;
      }

      // Збільшити к-сть елементів у стеку
      size++;
    }
    catch (bad_alloc e)
    {
      cout << e.what();
    }
  }

⇑

2.8. Метод Pop(). Витягнути елемент зі стеку

Витягування елементу зі стеку реалізується з допомогою методу Pop(), опис якого подано нижче.

public:

  ...

  // Витягнути елемент зі стеку
  T Pop()
  {
    // 1. Перевірка
    if (size == 0)
      return 0;

    // 2. Запам'ятати елемент, який буде повертатись
    T item = head->data;

    // 3. Встановити додатковий покажчик на голову
    Node<T>* p = head;

    // 4. Перемістити голову
    head = head->next;

    // 5. Звільнити пам'ять під голову
    delete p;

    // 6. Зменшити кількість елементів у стеку
    size--;

    // 7. Повернути елемент
    return item;
  }

⇑

2.9. Вивід стеку на екран. Метод Show()

З метою контролю правильності виконання програми, у клас вводиться метод Show(), що відображає стек.

// Вивід стеку на екран
void Show(string msg)
{
  Node<T>* p = head;
  cout << msg << " => ";
  while (p != nullptr)
  {
    cout << p->data << "  ";
    p = p->next;
  }
  cout << endl;
}

⇑

2.10. Деструктор ~Stack()

Очищення стеку, що виділений для об’єкту класу здійснюється у деструкторі, який викликає метод Free() описаний в п. 2.5.

// Звільнення пам'яті - деструктор
~Stack()
{
  Free();
}

⇑

2.11. Визначення, чи пустий стек. Метод IsEmpty()

// Повертає true, якщо стек пустий
bool IsEmpty()
{
  return size == 0;
}

⇑

2.12. Отримати розмір стеку. Метод Size()

// Повернути розмір стеку
int Size() const { return size; }

⇑

2.13. Конструктор копіювання Stack(const Stack<T>& obj)

В конструкторі копіювання виконується копіювання зовнішнього об’єкту-параметру у внутрішні структури даних. Для цього викликається функція Copy() реалізація якої описується в п. 2.4.

// Конструктор копіювання this<=obj
Stack(const Stack<T>& obj)
{
  // Обійти стек obj і зробити копію
  Copy(obj.head);
}

Оператор присвоєння копіюванням робить перевірку на те, чи є елементи в стеку. Якщо в стеку-приймачі є елементи, то цей стек звільняється шляхом виклику методу Free(). Копіювання стеку-джерела в стек-приймач здійснюється з допомогою методу Copy().

// Оператор присвоєння копіюванням
Stack<T>& operator=(const Stack<T>& obj)
{
  if (this != &obj)
  {
    if (size > 0)
      Free();
    Copy(obj.head);
  }
  return *this;
}

⇑

3. Скорочений програмний код класу Stack<T>

Скорочений програмний код класу з коментарями наведено нижче.

#include <iostream>
using namespace std;

template <class T>
class Stack
{
private:
  // Внутрішня структура
  template <class T>
  struct Node
  {
    T data;
    Node<T>* next;
  };

  Node<T>* head; // покажчик на вершину стеку
  unsigned int size = 0;

  // Функція Copy() - використовується, якщо потрібно
  // отримати копію стеку у внутрішні дані
  void Copy(Node<T>* _head)
  {
    ...
  }

  // Метод, що звільняє пам'ять під стек
  void Free()
  {
    ...
  }

public:
  // Створити пустий стек
  Stack()
  {
     ...
  }

  // Додати елемент до стеку
  void Push(T item)
  {
    ...
  }

  // Вивід стеку на екран
  void Show(string msg)
  {
    ...
  }

  // Звільнення пам'яті
  ~Stack()
  {
    ...
  }

  // Повертає true, якщо стек пустий
  bool IsEmpty()
  {
    ...
  }

  // Витягнути елемент зі стеку
  T Pop()
  {
    ...
  }

  // Повернути розмір стеку
  int Size() const
  {
    ...
  }

  // Конструктор копіювання this<=obj
  Stack(const Stack<T>& obj)
  {
    ...
  }

  // Оператор присвоєння копіюванням
  Stack<T>& operator=(const Stack<T>& obj)
  {
    ...
  }
};

⇑

4. Тест роботи класу. Функція main()

Функція main() використовується для тестування роботи класу стек і може мати довільний вигляд.

void main()
{
  Stack<int> S1;
  Stack<int> S3;
  S3 = S1;

  if (S3.IsEmpty())
    cout << "+";
  else
    cout << "-";

  S1.Push(10);
  S1.Push(15);
  S1.Push(20);
  cout << S1.Size() << endl;
  S1.Show("S1");

  Stack<int> S2 = S1;
  S2.Show("S2");

  S3 = S2;
  S3.Show("S3");

  if (S3.IsEmpty())
    cout << "+";
  else
    cout << "-";
}