6.18. Вернемся в классу iStack
6.18. Вернемся в классу iStack
У класса iStack, разработанного нами в разделе 4.15, два недостатка:
* он поддерживает только тип int. Мы хотим обеспечить поддержку любых типов. Это можно сделать, преобразовав наш класс в шаблон класса Stack;
* он имеет фиксированную длину. Это неудобно в двух отношениях: заполненный стек становится бесполезным, а в попытке избежать этого мы окажемся перед необходимостью отвести ему изначально слишком много памяти. Разумным выходом будет разрешить динамический рост стека. Это можно сделать, пользуясь тем, что лежащий в основе стека вектор способен динамически расти.
Напомним определение нашего класса iStack:
#include vector
class iStack {
public:
iStack( int capacity )
: _stack( capacity ), _top( 0 ) {};
bool pop( int value );
bool push( int value );
bool full();
bool empty();
void display();
int size();
private:
int _top;
vector int _stack;
};
Сначала реализуем динамическое выделение памяти. Тогда вместо использования индекса при вставке и удалении элемента нам нужно будет применять соответствующие функции-члены. Член _top больше не нужен: функции push_back() и pop_back() автоматически работают в конце массива. Вот модифицированный текст функций pop() и push():
bool iStack::pop( int top_value )
{
if ( empty() )
return false;
top_value = _stack.back(); _stack.pop_back();
return true;
}
bool iStack::push( int value )
{
if ( full() )
return false;
_stack.push_back( value );
return true;
}
Функции-члены empty(), size() и full() также нуждаются в изменении: в этой версии они теснее связаны с лежащим в основе стека вектором.
inline bool iStack::empty(){ return _stack.empty(); }
inline bool iStack::size() { return _stack.size(); }
inline bool iStack::full() {
return _stack.max_size() == _stack.size(); }
Надо немного изменить функцию-член display(), чтобы _top больше не фигурировал в качестве граничного условия цикла.
void iStack::display()
{
cout
Наиболее существенным изменениям подвергнется конструктор iStack. Никаких действий
от него теперь не требуется. Можно было бы определить пустой конструктор:
inline iStack::iStack() {}
Однако это не совсем приемлемо для пользователей нашего класса. До сих пор мы строго сохраняли интерфейс класса iStack, и если мы хотим сохранить его до конца, необходимо оставить для конструктора один необязательный параметр. Вот как будет выглядеть объявление конструктора с таким параметром типа int:
class iStack {
public:
iStack( int capacity = 0 );
// ...
};
Что делать с аргументом, если он задан? Используем его для указания емкости вектора:
inline iStack::iStack( int capacity )
{
if ( capacity )
_stack.reserve( capacity );
}
Превращение класса в шаблон еще проще, в частности потому, что лежащий в основе вектор сам является шаблоном. Вот модифицированное объявление:
#include
template
class Stack {
public:
Stack( int capacity=0 );
bool pop( elemType &value );
bool push( elemType value );
bool full();
bool empty();
void display();
int size();
private:
vector _stack;
};
Для обеспечения совместимости с программами, использующими наш прежний класс iStack, определим следующий typedef:
typedef Stackint iStack;
Модификацию операторов класса мы оставим читателю для упражнения.
Упражнение 6.29
Модифицируйте функцию peek() (упражнение 4.23 из раздела 4.15) для шаблона класса Stack.
Упражнение 6.30
Модифицируйте операторы для шаблона класса Stack. Запустите тестовую программу из раздела 4.15 для новой реализации
Упражнение 6.31
По аналогии с классом List из раздела 5.11.1 инкапсулируйте наш шаблон класса Stack в пространство имен Primer_Third_Edition
2011-09-30 22:30:08 Михаил
Спасибо за инф :) посмотрел по контейнерам.