Разработка шаблонного класса реализующего стек в виде односвязного списка
Содержание
- 1. Преимущества реализации стека в виде односвязного списка по сравнению с динамическим массивом
- 2. Структура NodeStack, описывающая узел
- 3. Реализация стека в виде односвязного списка (рисунок)
- 4. Текст программы
- 5. Результат работы программы
- 6. Особенности программной реализации
- Связанные темы
Поиск на других ресурсах:
1. Преимущества реализации стека в виде односвязного списка по сравнению с динамическим массивом
Реализация динамической структуры данных стек в виде односвязного списка имеет следующие преимущества:
- потребности в меньшем объеме памяти в случае добавления нового элемента. В односвязном списке дополнительная память для элемента выделяется только для этого одного элемента. В динамическом массиве сначала нужно выделить новый фрагмент (массив) памяти для всех элементов, затем осуществить копирование старого массива в новый и только тогда освободить память, выделенную под старый массив. С возрастанием количества элементов в стеке это преимущество становится более ощутимым;
- меньшее количество дополнительных операций в случае манипулирования стеком (добавление нового элемента, удаление элемента).
Недостатки:
- сложность реализации. Обработку односвязного списка более сложно реализовать (это все условно);
- для доступа к i-му элементу в динамическом массиве удобно использовать доступ по индексу. В односвязном списке нужно пересматривать (перематывать) весь список от начала к нужной позиции.
⇑
2. Структура NodeStack, описывающая узел
Любой односвязный (двусвязный) список базируется на специальной структуре или классе, которая описывает один узел (рисунок 1).
Рисунок 1. Узел в случае односвязного списка: item – элемент данных, next – указатель на структуру типа NodeStack
В узле (структуре) выделяются два элемента:
- элемент данных item некоторого обобщенного типа T;
- указатель на следующий элемент типа NodeStack<T>.
На языке C++ объявление структуры NodeStack имеет следующий вид
// Структура, описывающая узел template <typename T> struct NodeStack { T item; NodeStack<T>* next; };
⇑
3. Реализация стека в виде односвязного списка (рисунок)
На рисунку 2 изображен стек в виде односвязного списка
Рисунок 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.
⇑
Связанные темы
- Стек. Операции над стеком. Пример реализации стека в виде динамического массива
- Очередь. Особенности реализации. Способы реализации очереди. Представление очереди в виде динамического массива
- Очередь с приоритетами. Пример реализации. Представление в виде динамического массива
⇑