C++ Шаблонный класс стека

Тут на днях сижу, вспоминаю С++. Решил отработать "стандарты" на прошлых задачках. Вот набросал шаблонный класс стека (велосипед по мотивам std::stack). Тут есть кое-что интересное - динамические структуры (решил не привязываться к std::list и подобным) и внутренние классы.

Стек представляет собой такую конструкцию:

Это стопка объектов. Реализует принцип FILO (First In, Last Out - "первый вошел, последний вышел"), мы можем запихивать в стопку (операция Push) и извлекать (операция Pop) только с одного конца.

С помощью стека можно считать, например, скобки в выражении или соблюдается ли условие закрытия всех тегов в документе XML. То есть, мы открывающиеся скобки "(" добавляем в стек, а когда встречаем закрывающие скобки ")", мы извлекаем из стека верхний элемент. Таким образом, если в выражении правильно расставлены скобки, то стек окажется пустым (каждой открывающей скобке соответствует пара - закрывающая скобка) и не будет ни одного обращения к пустому стеку.

Во-первых, что нам необходимо для работы со стеком? Он должен:

• хранить информацию (ячейка данных)


• знать, где у него верх (закрытая переменная-указатель top, т.к. пользователю она не понадобится)


• знать, пуст ли он (интерфейсный (открытый) метод IsEmpty(void); )


• уметь извлекать и вносить новые элементы в стек (интерфейсные методы Pop(void) и Push(вносимая_информация) соответственно)

Таким образом, нам понадобятся связанные между собой (имеющие ссылки друг на дуга) элементы. Это нужно за тем, чтобы удаляя элемент из вершины (Pop), переадресовать указатель на вершину новой вершине (предпоследнему элементу в стеке). Выходит, помимо класса-провайдера (управляющего класса, содержащего методы интерфейса) нам необходим подкласс, реализующий сам связный список элементов. /*Если знаком с динамическими структурами, то тебе это будет знакомо.*/ Состоит каждый элемент, как мы тут расписывали, из блока данных date и указателя на предыдущий элемент this->prev.

struct Node
{
    DataType data;
    Node     *prev;

    Node(const DataType& inData) { data = inData; }
};

Понятно, что создавая новый элемент, мы будем связывать его с предыдущим (тут оперируем с указателем Node *top, т.к. он всегда будет указывать на вершину стека). Во внешнем классе-провайдере Stack мы имеем наш подкласс Node, переменную количества элементов int count и указатель на вершину Node *top :

template<class DataType> class Stack
{
 int count;

 // Dynamic list struct without depending
 // from std::list
 struct Node
 {
  DataType data;
  Node     *prev;

  Node(const DataType& inData) { data = inData; }
 };

 Node *top;
 
public:

 ~Stack() {
  while(count > 0) {
   Pop();
  }
 }
 
 int   GetCount() const  { return count;   }
 bool  IsEmpty() const   { return !count;  }
 
 void     Push(DataType inData);
 DataType Pop();
};

Конструктор ясен как день - инициализируем count нулем, также зануляем указатель. Деструктор - делаем Pop(), пока стек не окажется пустым. Не оптимально, зато наглядно)

Ну и в качестве финала весь текст проекта:

// file "Stack.h"
//------------------

template<class DataType> class Stack
{
 int count;

 // Dynamic list struct without depending
 // from std::list
 struct Node
 {
  DataType data;
  Node     *prev;

  Node(const DataType& inData) { data = inData; }
 };

 Node *top;
 
public:

 ~Stack() {
  while(count > 0) {
   Pop();
  }
 }
 
 int   GetCount() const  { return count;   }
 bool  IsEmpty() const   { return !count;  }
 
 void     Push(DataType inData);
 DataType Pop();
};

template<class DataType> void Stack<Type>::Push(const Type& inData) {
 auto newObj = new Node(inData);
 
 if (IsEmpty()) { // Create first
  newObj->prev = nullptr;
  top =  newObj;
 } else { // Create second and others
  newObj->prev = top;
  top = newObj;
 }
 ++count;
}

template<class DataType> DataType Stack<Type>::Pop() {
 Type resultData = top->data;
 auto willDeleted = top;
 
 if (count > 0) { // Stack is not empty
  // if > 1 elements inside
  if (count > 1) {
   top = top->prev;
   delete willDeleted;
  } else { // 1 emement inside
   delete top;
   top = nullptr;
  }
  --count;
  return resultData;
 } else {
  return nullptr;
 }
}

Пример использования:

// file "src.cpp"
//------------------

#include <iostream>
#include "Stack.h"

int main() {
 Stack<int> st;
 
 for (int i=1; i<10; i++) {
  st.Push(i);
 }
 
 while(!st.IsEmpty()) {
  std::cout << st.Pop() << std::endl;
 }

   std::cout << "Press [Enter] to exit..." << std::endl;
 std::cin.get();
 return 0;
}

Для пущей радости решил разбросать по файлам. Случилось откровение: методы шаблонного класса нельзя выносить из *.h файла объявления класса в сорец *.cpp, ибо это лишь формализованная форма (как дела обстоят с конкретными реализациями - не пробовал, но подозреваю, что можно). Иначе - линковщик заругает.