Стек. Продолжим разговор.

"Первое, что приходит в голову С++ программисту это написать класс, с перегрузкой операторов, динамическим выделением памяти, обработкой исключений и тому подобных фишек данного языка. Но этим мы займемся как-нибудь в другой раз." Это - цитата автора статьи "Просто о сложном. Стек". В этой статье стек реализован через массив, причем массив статический.

Обратите внимание на последнее предложение автора "Но этим мы займемся как-нибудь в другой раз.". Именно сегодня этим мы и займемся. Сегодня мы создадим шаблонный класс Stack с перегруженным оператором вывода (<<), динамическим выделением памяти, обработкой исключительной ситуации, которая может возникнуть при выделении памяти, а также затронем динамическое определение типа.

Еще одной особенностью нашего стека будет то, что он будет динамическим, то есть в него можно помещать бесконечно большое число элементов до тех пор, пока не кончится память, выделенная для программы. И хотя все это будет сделано мной, а не автором вышеупомянутой статьи, я не думаю, что у меня получится хуже. Начнем.

Стек

Этот раздел статьи написан для тех, кто не знает, что такое стек. Хотя, наверное, таких немного, я посчитал нужным все же оставить его.
Стек (англ. stack — стопка) — структура данных, в которой доступ к элементам организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю. Так же Вы можете увидеть сравнение стека с обоймой: последним будет вынут тот патрон, который вставили первым.

Традиционно в классе, реализующем стек, существует всего две функции. Первая из них push, эта функция реализует добавление элемента в стек, причем, как понятно из принципа LIFO, элемент добавляется в вершину стека, то есть добавленный элемент становится первым сверху. Вторая функция - функция pop. С помощью этой функции происходит выталкивание элементов из стека. Выталкивание, так же как и добавление, возможно только верхнего элемента.
Кроме этих функций, в стек можно добавить другие функции, например, просмотр стека. И хотя стандартная реализация стека не предусматривает этой (да и других) функции, ее возможно реализовать не извлекая элементов стека. Именно эта функция и будет у нас реализована, только эта функция у нас будет реализована не как член-метод класса, а как перегруженный оператор вывода (<<). Вторым названием оператора вывода является "оператор вставки", так как он вставляет символы в поток. Функция, перегружающая оператор вставки, называется функцией вставки.

Теперь, зная что такое стек, можно перейти к следующему вопросу, необходимому для понимания данного материала, а именно шаблоны.

Шаблоны

Шаблоны - один из наиболее сложных и мощных механизмов языка C++. С помощью шаблонов можно создавать обобщенные функции и классы, которые работают с типом данных, заданным как параметр. Таким образом, одну и ту же функцию или класс можно применять как разным типам данных, не используя отдельные варианты для каждого типа.
Вообще тема шаблонов является довольно объемной, и я не буду полностью раскрывать эту тему в данной статье. Тут я не буду описывать шаблонные функции и их применение, я всего лишь расскажу про шаблонные классы, и то, только ту информацию, которая необходима для понимания данной статьи. Если Вы захотите более углубленно изучить шаблоны - воспользуйтесь сторонними источниками.

Шаблонный класс - класс, в котором определены все алгоритмы, а фактический тип данных задается в качестве параметра при создании объекта. Чаще всего шаблонные классы применяются в тех случаях, когда логика класса не зависит от типа данных. В нашем случае, к стеку, состоящему из целых чисел или символов, можно применять один и тот же алгоритм.

Объявление шаблонного класса имеет следующий вид:

template <typename Тип> class Имя_Класса {
...
}

Имя_Класса <Тип> Имя_Объекта.

Если на данном этапе Вам не все понятно - не расстраивайтесь. Когда будем рассматривать пример кода - станет понятнее (я на это надеюсь).
Далее пару слов о перегрузке операторов, динамическом выделении памяти, исключительных ситуациях и динамическом определении типа. Все эти темы будут рассмотрены очень кратко, т.к. при полном их рассмотрении надо писать материал, по размеру превышающий этот раз в 10-20. Да и есть полно литературы на эти темы. Так что если понадобиться - не составит трудности найти по ним информацию.

Перегрузка операторов

Перегрузка операторов определяет действия операторов применительно к соответствующему классу. То есть Вы можете перегрузить оператор для Вашего класса, так, что бы он выполнял нужные вам действия.

Для нашего класса будет перегружен оператор вывода (<<), так, что бы он выводил содержимое нашего стека в поток.
Тут ситуация такая же, как и с шаблонами: будет пример - будет проще.

Обработка исключительных ситуаций

Исключительные ситуации возникают, когда нормальный ход выполнения программы необходимо прервать или нормальный ход выполнения программы был прерван из-за возникшей ошибки.

Обработка исключительных ситуаций позволяет правильно реагировать на ошибки, возникающие в ходе выполнения программы.
Механизм обработки исключительных ситуациях в языке C++ основан на ключевых словах try и catch (еще есть ключевое слово throw, но о нем не будем). Фрагменты программы, подлежащие контролю, помещаются в блок try. Если в ходе выполнения программы в блоке try возникает исключительная ситуация (т.е. ошибка), она перехватывается блоком catch и обрабатывается в нем. Оператор catch ловит тип ошибки и обрабатывает ее нужным образом.
Этих знаний нам хватит, для дальнейшего изучения материала.

Динамическое выделение памяти

В языке C++ предусмотрены два оператора динамического распределения памяти: new и delete. Эти операторы выделяют и освобождают память в ходе выполнения программы. Оператор new выделяет область памяти и возвращает указатель на ее первую ячейку. Оператор delete освобождает память, выделенную ранее оператором new.

Поскольку объем кучи (области памяти, выделяемой и освобождаемой динамически. Эта память выделяется ОС для выполнения программы) ограничен, память может оказаться исчерпанной. В этом случае оператор new сгенерирует исключительную ситуацию bad_alloc, определенную в заголовке . Программа должна перехватить эту ситуацию и обработать ее. Как обработать исключительную ситуацию, мы ознакомились ранее.

Динамическое определение типа

В языке C++ для поддержки объектно-ориентированного программирования используется динамическая идентификация типа (RTTI - Run-Time Type Identification). Система RTTI позволяет идентифицировать тип объекта при выполнении программы.

Для идентификации типа объекта используется оператор typeid, определенный в заголовке . Чаще всего он применяется в следующей форме:

typeid (object)

Здесь параметр object является объектом, тип которого мы хотим определить.

Все то, что не вошло в предыдущие разделы

Ранее было описано почти все, что необходимо для понимания код, который я приведу ниже. Но есть еще немного моментов, которые я не описывал, но с которыми ми столкнемся. Я решил не создавать отдельный раздел для каждого из этих моментов и опишу их в одном разделе.

Основой объектно-ориентированного программирования является класс. Класс представляет собой совокупность логически связанных данных и методов, объединенных под одним именем. Данные в классе могут быть открытыми (public) и закрытыми (private). Есть так же защищенные члены класса (protected), но они нас сейчас не волнуют. Доступ к открытым членам класса можно получить с любой точки программы, а вот к закрытым членам могут обратиться только методы класса (функции, определенные в классе).

С помощью ключевого слова friend можно предоставить обычной функции доступ к закрытым членам класса. Для того, что бы объявить дружественную функцию, следует поместить ее прототип внутри класса, указав перед ней ключевое слово friend.

Когда будем рассматривать код, Вы на рабочем примере увидите и поймете все то, что сейчас не понятно.

Ну и перед тем, как начать писать код, немного слов о потоках в языке C++. Поток - логическое устройство, получающее или передающее информацию. Поток связан с физическим устройством ввода-вывода. В начале выполнения программы на языке С++ автоматически открывается четыре потока. Один из них cout, с ним мы и будем работать сегодня. cout - поток стандартного вывода, устройством вывода которого является экран.
Теперь у нас есть база, достаточная для написания и понимания кода.

Код

В этом разделе будет приведен полный код с подробными комментариями к нему, поэтому кроме кода и комментариев к нему в этом разделе Вы не увидите. Но комментариев и знаний, полученных ранее должно хватить для понимания кода.

#include "stdafx.h"
#include <iostream> //необходимо для работы с потоками ввода-вывода
#include <typeinfo> //необходимо для использования функции динамического определения типа typeid
#include <new> //в этом заголовке описан класс ошибки выделения памяти bad_alloc 
 
/* Все функции из стандартных библиотек языка С++
помещаются в пространство имен std */
using namespace std; 
 
/* Сообщаем компилятору о существовании класса Stack.
Так как этот класс далее используется для объявления дружественного
оператора вывода*/
template <typename StackType> class Stack;
/*Объявление дружественного оператора вывода.
Объявление происходит перед описанием класса, что бы
компилятор мог связать перегруженный оператор с конкретным типом данных.
Эта проблема касается только шаблонных классов, т.к. тип, используемый
в классе заранее не известен. */
template <typename StackType> ostream &operator<<(ostream &stream, Stack <StackType> &obj);
 
//Объявление класса Stack
template <typename StackType> class Stack {
	StackType value; //значение, хранящееся в элемента стека
	Stack *top, *next; //указатель на вершину стека, первый элемент стека, и на следующий элемент стека
public:
	Stack() {next=0; top=0;} //конструктор. вызывается при создании элемента
	void push (StackType obj); //прототип функции помещения элемента в стек
	StackType pop(); //прототип функции выталкивания элемента из стека
	//дружественный перегруженный оператор вывода
	friend ostream &operator<< <StackType> (ostream &stream, Stack <StackType> &obj); 
};
 
//описание функции помещения элемента в стек
template <typename StackType> void Stack <StackType>::push(StackType obj) {
	//в блоке try мы пытаемся выделить память для новго элемента
	try {
		Stack *temp = new Stack; //выделяем память для нового элемента
		temp->value=obj; //присваиваем значение, переданное в функцию полю value вновь созданного элемента
 
	if(top!=0) //если стек не пуст
		temp->next=top; //предыдущим элементом для вновь добавленного становится текущая вершина стека
	top=temp; //новой вершиной стека становится вновь добавленный элемент
	}
	catch (bad_alloc badalloc) { //если удается словить ошибку выделения памяти
		cout<<"Exception: memory can not be allocated!"<<endl; //выводим информационное сообщение
		exit(1); //завершаем программу
	}
}
 
//описание функции выталкивания элемента
template <typename StackType> StackType Stack <StackType>::pop() {
	Stack *item; //адрес удаляемого элемента
	StackType valToRet=0; //возвращаемое значение функции
 
	if(!top) { //если стек пуст
		cout<<"Stack is empty"<<endl; //выводим информационное сообщение
		return (StackType) 0; //выходим из функции
	}
 
	/* в качестве возвращаемого значения
	используем информационное поле вершины стека*/
	valToRet=top->value;
	item=top; //присваиваем удаляемому элементу адрес вершины стека
	top=top->next; //новой вершиной стека становиться следующей за текущей вершиной элемент
	delete item; //удаляем старую вершину стека, освобождая занятую ей память
	return valToRet; //возвращаем информационное поле удаленной вершины
}
 
/* перегрузка оператора вывода.
В левой части оператора должен находиться поток, в который му будем
вставлять информацию. В правой - объект класса стек, из которого
мы будем вставлять информацию. */
template <typename StackType> ostream &operator<< <StackType>(ostream &stream, Stack <StackType> &obj) {
	Stack <StackType> *temp=obj.top; //указатель на вершину стека
 
	/* вставляем в поток информацию о том, какой тип данных используется в стеке.
	Функция typeid возвращает объект класса type_info, открытым методом которого
	является функция name(), возвращающая имя используемое объектом.
	Таким образом мы получаем информацию и типе данных стека. */
	stream<<"Inside of "<<typeid(StackType).name()<<" stack: "<<endl;
	while(temp) { // пока не достигнем конца стека
		stream<<temp->value<<" "; //вставляем в поток значение текущего элемента и символ пробела
		temp=temp->next; //переходим к следующему элементу
	}
	stream<<endl; //вставляем в поток символ перехода на новую строку
 
	return stream; //возвращаем поток
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
	Stack <char> charStack; //создаем объект класса Stack, организующий стек символов
 
	//заталкиваем в стек элементы
	charStack.push('a');
	charStack.push('b');
	charStack.push('c');
 
	cout<<charStack; //выводим содержимое стека на экран
 
	Stack <int> intStack; //создаем стек из целочисленных значений
 
	//помещаем элементы в стек
	intStack.push(1);
	intStack.push(2);
	intStack.push(3);
 
	cout<<intStack; //выводим стек на экран
 
	return 0;
}

Вот и все. Исходник выкидывать нет смысла, т.к. кода не много и весь код приведен выше. Надеюсь, что весь материал понятен и не вызвал никаких затруднений.
Если возникнут вопросы, касающиеся данной темы, или что-то не получится – пишите в комментариях.
Спасибо за внимание.

Written by: Сергей Дубовик aka SD
Date: 07.10.2011