Реализуем еще один простой контейнер — стек. Мы могли бы использовать в качестве стека и наш класс-дек, однако он делает гораздо больше, чем нам надо, например, перебирать элементы стека, как правило, нет необходимости, поэтому класс-итератор нам не нужен. Мы реализуем более простой вариант, обеспечив только необходимую функциональность:
• добавление элемента в стек — push();
• удаление элемента из стека — рор();
• получение значения элемента с вершины стека — tOp();
• проверка, не пустой ли стек — empty ().
Для реализации такой дисциплины доступа к элементам нам достаточно одно-связного списка. Структура элемента односвязного списка (листинг 6.8) практически не отличается от структуры элемента двусвязного, только указатель для связи — единственный.
Очевидно, что стек является универсальной структурой, работа которой не зависит от типа элементов. Однако написать стек, который можно было бы использовать с данными произвольного типа, не так просто — тип элемента определяется во время компиляции и не может меняться динамически. Единственный универсальный тип в С++ — это нетипизированный указатель void *. Поэтому типом элементов должен быть указатель void *.
Листинг 6.8. Элемент односвязного списка
struct Elem { void *data; Elem *next;
E,lem (void *d, Elem *p) :data(d), next(p) { }
};
Так как в этом случае только владелец данных (программа-клиент, использующая стек) знает реальный тип элементов стека, то пусть она и «опорожняет» стек с помощью операции рор(). Таким образом, деструктор мы писать не будем1.
Конструктор инициализации нам тоже ни к чему, так как изначально стек не содержит ни одного элемента. Присваивать и копировать стеки обычно не требуется. Таким образом, нам хватит только одного конструктора без аргументов, функцией которого является обнуление указателя на вершину стека. Нулевое значение указателя служит признаком отсутствия элементов в стеке. Реализация нашего стека с учетом всех этих соображений представлена в листинге 6.9.
Листинг 6.9. Реализация простого стека
class TStack v
{ struct Elem // узел списка
{ void *data; // информационная часть
Elem *next; // указательная часть
Elem (void *d, Elem *p) // конструктор узла
:data(d), next(p)
1 Однако система создаст «пустой» деструктор по умолчанию.
{ }
};
Elem * Head; TStack(const TStack &); TStack& operator=(const TStack &); public:
TStackO: Head(0) {}
void push(void *d)
{ Head = new Elem(d. Head); }
void *top() const
{ return emptyO? 0: Head->data;
void *pop()
{ if (emptyO) return 0; void *top = Head->data; Elem *oldHead = Head; Head = Head->next; delete oldHead; return top;
}
bool emptyO const { return Head==0; }
// вершина стека
// закрыли копирование
// закрыли присваивание
// пустой стек
// положить элемент в стек
получить элемент с вершины стека
удалить элемент из стека если стек пустой - ничего не делать сохранили для возврата запомнили указатель передвинули вершину возвратили память возвратили элемент
// стек пустой, если указатель = 0
Деструктор нам действительно не понадобился: удаление элемента стека выполняет метод pop(), который возвращает указатель на информационную часть, чтобы программа-клиент могла возвратить эту память системе.
ПРИМЕЧАНИЕ -
Функции pop () и top () проверяют «пустоту» стека; признаком пустого стека является нулевой указатель Head.
При использовании стека нужно выполнять преобразование указателей: TStack t;
t.push(new double(l)); // кладем в стек числа
t.push(new double(2)); t.push(new double(3));
while (!t.emptyO) // пока стек не пустой
{ cout << *(double *)t.top() << endl; // выводим число с вершины
double *р = (double *)t.pop(); // удаляем элемент из стека
delete р; // возвращаем память
}
Этот фрагмент программы выведет на экран следующее:
3 2 1
Вообще-то при такой реализации рор() в некоторых редких случаях (при возникновении исключения см. главу 7) возможна потеря данных. Поэтому в стандартной библиотеке подобные методы в классах-контейнерах не возвращают результата, а только удаляют элемент из контейнера. |
Главная
Каталог файлов
