Стек
В разделе 4.5 операции инкремента и декремента были проиллюстрированы на примере реализации абстракции стека. В общем случае стек является очень полезным механизмом для сохранения текущего состояния, если в разные моменты выполнения программы одновременно существует несколько состояний, вложенных друг в друга.
Поскольку стек– это важная абстракция данных, в стандартной библиотеке С++ предусмотрен класс stack, для использования которого нужно включить заголовочный файл:
#include <stack>
В стандартной библиотеке стек реализован несколько иначе, чем у нас. Разница состоит в том, что доступ к элементу с вершины стека и удаление его осуществляются двумя функциями – top() и pop(). Полный набор операций со стеком приведен в таблице 6.5.
Таблица 6.5. Операции со стеком
| Операция | Действие | ||
| empty() | Возвращает true, если стек пуст, и false в противном случае | ||
| size() | Возвращает количество элементов в стеке | ||
| pop() | Удаляет элемент с вершины стека, но не возвращает его значения | ||
| top() | Возвращает значение элемента с вершины стека, но не удаляет его | ||
| push(item) | Помещает новый элемент в стек |
В нашей программе приводятся примеры использования этих операций:
| #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 */ }; |
К двум стекам одного типа можно применять операции сравнения: равенство, неравенство, меньше, больше, меньше или равно, больше или равно, если они определены над элементами стека. Элементы сопоставляются попарно. Первая пара несовпадающих элементов определяет результат операции сравнения в целом.
Стек будет использован в нашей программе текстового поиска в разделе 17.7 для поддержки сложных запросов типа
Civil && ( War || Rights )
