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

В данной работе приведен пример шаблонного класса 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++. Стек как односвязный список. Структура Node<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; // размер стека
};

...

В конструкторе копирования и операторе копирования необходимо выполнять операцию копирования стека из внешнего объекта во внутреннюю структуру данных, на которую указывает указатель 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);
}

⇑

2.14. Оператор присваивания копированием operator=(const Stack<T>& obj)

Оператор присвоения копированием проверяет, есть ли элементы в стеке. Если в стеке приемнике есть элементы, то этот стек освобождается путем вызова метода 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 << "-";
}

⇑

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

⇑