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

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


Содержание


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

Реализация динамической структуры данных стек в виде односвязного списка имеет следующие преимущества:

  • потребности в меньшем объеме памяти в случае добавления нового элемента. В односвязном списке дополнительная память для элемента выделяется только для этого одного элемента. В динамическом массиве сначала нужно выделить новый фрагмент (массив) памяти для всех элементов, затем осуществить копирование старого массива в новый и только тогда освободить память, выделенную под старый массив. С возрастанием количества элементов в стеке это преимущество становится более ощутимым;
  • меньшее количество дополнительных операций в случае манипулирования стеком (добавление нового элемента, удаление элемента).

Недостатки:

  • сложность реализации. Обработку односвязного списка более сложно реализовать (это все условно);
  • для доступа к i-му элементу в динамическом массиве удобно использовать доступ по индексу. В односвязном списке нужно пересматривать (перематывать) весь список от начала к нужной позиции.

 

2. Структура NodeStack, описывающая узел

Любой односвязный (двусвязный) список базируется на специальной структуре или классе, которая описывает один узел (рисунок 1).

C++. Узел в случае односвязного списка

Рисунок 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.

 


Связанные темы