6.16. Стек

В разделе 4.5 операции инкремента и декремента были проиллюстрированы на примере реализации абстракции стека. В общем случае стек является очень полезным механизмом для сохранения текущего состояния, если в разные моменты выполнения программы одновременно существует несколько состояний, вложенных друг в друга. Поскольку стек – это важная абстракция данных, в стандартной библиотеке С++ предусмотрен класс stack, для использования которого нужно включить заголовочный файл:

#include <stack>

В стандартной библиотеке стек реализован несколько иначе, чем у нас. Разница состоит в том, что доступ к элементу с вершины стека и удаление его осуществляются двумя функциями – top() и pop(). Полный набор операций со стеком приведен в таблице 6.5.

Таблица 6.5. Операции со стеком

В нашей программе приводятся примеры использования этих операций:

#include <stack> #include <iostream> int main()

{

const int ia_size = 10;

int ia[ia_size ]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // заполним стек

int ix = 0;

stack< int > intStack;

for ( ; ix < ia_size; ++ix ) intStack.push( ia[ ix ] );

int error_cnt = 0;

if ( intStack.size() != ia_size ) {

cerr << "Ошибка! неверный размер IntStack: "

<<intStack.size()

<<"\t ожидается: " << ia_size << endl, ++error_cnt;

}

int value;

while ( intStack.empty() == false )

{

// считаем элемент с вершины value = intStack.top();

if ( value != --ix ) {

cerr << "Ошибка! ожидается " << ix

<< " получено " << value << endl; ++error_cnt;

}

// удалим элемент intStack.pop();

}

cout << "В результате запуска программы получено

"

<< error_cnt << " ошибок" << endl;

}

Объявление

stack< int > intStack;

определяет intStack как пустой стек, предназначенный для хранения элементов типа int. Стек является надстройкой над некоторым контейнерным типом, поскольку реализуется с помощью того или иного контейнера. По умолчанию это deque, поскольку именно эта структура обеспечивает эффективную вставку и удаление первого элемента, а vector эти операции не поддерживает. Однако мы можем явно указать другой тип контейнера, задав его как второй параметр:

stack< int, list<int> > intStack;

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

#include <stack>

class NurbSurface { /* mumble */ };

stack< NurbSurface* > surf_Stack;

К двум стекам одного типа можно применять операции сравнения: равенство, неравенство, меньше, больше, меньше или равно, больше или равно, если они определены над элементами стека. Элементы сопоставляются попарно. Первая пара несовпадающих элементов определяет результат операции сравнения в целом.

Стек будет использован в нашей программе текстового поиска в разделе 17.7 для поддержки сложных запросов типа

Civil && ( War || Rights )

6.17. Очередь и очередь с приоритетами

Абстракция очереди реализует метод доступа FIFO (first in, first out – “первым вошел, первым вышел”): объекты добавляются в конец очереди, а извлекаются из начала. Стандартная библиотека предоставляет две разновидности этого метода: очередь FIFO, или простая очередь, и очередь с приоритетами, которая позволяет сопоставлять элементы с их приоритетами. Текущий элемент помещается не в конец такой очереди, а перед элементами с более низким приоритетом. Программист, определяющий такую структуру, задает способ вычисления приоритетов. В реальной жизни подобное можно увидеть, скажем, при регистрации багажа в аэропорту. Как правило, пассажиры, чей рейс через 15 минут, передвигаются в начало очереди, чтобы не опоздать на самолет. Примером из практики программирования служит планировщик операционной системы, определяющий последовательность выполнения процессов.

Для использования queue и priority_queue необходимо включить заголовочный файл:

#include <queue>

Полный набор операций с контейнерами queue и priority_queue приведен в таблице 6.6.

Таблица 6.6. Операции с queue и priority_queue

Элементы priority_queue отсортированы в порядке убывания приоритетов. По умолчанию упорядочение основывается на операции “меньше”, определенной над парами элементов. Конечно, можно явно задать указатель на функцию или объектфункцию, которая будет использоваться для сортировки. (В разделе 12.3 можно найти более подробное объяснение и иллюстрации использования такой очереди.)

6.18. Вернемся в классу iStack

Укласса iStack, разработанного нами в разделе 4.15, два недостатка:

∙он поддерживает только тип int. Мы хотим обеспечить поддержку любых типов. Это можно сделать, преобразовав наш класс в шаблон класса Stack;

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

Напомним определение нашего класса iStack:

Надо немного изменить функцию-член display(), чтобы _top больше не фигурировал в

void iStack::display()

{

cout << "( " << size() << " )( bot: ";

for ( int ix=0; ix < size(); ++ix ) cout << _stack[ ix ] << " ";

cout << " stop )\n";

качестве граничного условия цикла.

}

Наиболее существенным изменениям подвергнется конструктор iStack. Никаких действий от него теперь не требуется. Можно было бы определить пустой конструктор:

inline iStack::iStack() {}

Однако это не совсем приемлемо для пользователей нашего класса. До сих пор мы строго сохраняли интерфейс класса iStack, и если мы хотим сохранить его до конца, необходимо оставить для конструктора один необязательный параметр. Вот как будет

class iStack { public:

iStack( int capacity = 0 );

// ...

выглядеть объявление конструктора с таким параметром типа int:

};

inline iStack::iStack( int capacity )

{

if ( capacity ) _stack.reserve( capacity );

Что делать с аргументом, если он задан? Используем его для указания емкости вектора:

}

Превращение класса в шаблон еще проще, в частности потому, что лежащий в основе вектор сам является шаблоном. Вот модифицированное объявление:

#include <vector>

template <class elemType> 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< elemType > _stack;

};

Для обеспечения совместимости с программами, использующими наш прежний класс iStack, определим следующий typedef:

typedef Stack<int> iStack;

Модификацию операторов класса мы оставим читателю для упражнения. Упражнение 6.29

Модифицируйте функцию peek() (упражнение 4.23 из раздела 4.15) для шаблона класса

Stack. Упражнение 6.30

Модифицируйте операторы для шаблона класса Stack. Запустите тестовую программу из раздела 4.15 для новой реализации

Упражнение 6.31

По аналогии с классом List из раздела 5.11.1 инкапсулируйте наш шаблон класса Stack

в пространство имен Primer_Third_Edition

Часть III

Процедурно-ориентированное программирование

В части II были представлены базовые компоненты языка С++: встроенные типы данных (int и double), типы классов (string и vector) и операции, которые можно совершать над данными. В части III мы увидим, как из этих компонентов строятся функции, служащие для реализации алгоритмов.

В каждой программе на С++ должна присутствовать функция main(), которая получает управление при запуске программы. Все остальные функции, необходимые для решения задачи, вызываются из main(). Они обмениваются информацией при помощи параметров, которые получают при вызове, и возвращаемых значений. В главе 7 представлен соответствующие механизмы С++.