6.16. Стек

6.16. Стек

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

#include stack

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

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

Операция

Действие

empty()

Возвращает true, если стек пуст, и false в противном случае

size()

Возвращает количество элементов в стеке

pop()

Удаляет элемент с вершины стека, но не возвращает его значения

top()

Возвращает значение элемента с вершины стека, но не удаляет его

push(item)

Помещает новый элемент в стек

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

#include

#include

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 intStack;

for ( ; ix

Объявление

stack int intStack;

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

stack int, listint intStack;

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

#include stack

class NurbSurface { /* mumble */ };

stack NurbSurface* surf_Stack;

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

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

Civil ( War || Rights )

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

Стек (Stack)

Из книги Руководство по стандартной библиотеке шаблонов (STL) автора Ли Менг

Стек (Stack) Любая последовательность, поддерживающая операции back, push_back и pop_back, может использоваться для модификации stack. В частности, могут использоваться vector, list и deque.template ‹class Container›class stack { friend bool operator==(const stack‹Container›& х, const stack‹Container›& y); friend bool operator‹(const


Ошибка 0x0000002B: стек переполнен

Из книги Очень хороший самоучитель пользователя компьютером. Как самому устранить 90% неисправностей в компьютере и увеличить его возможности автора Колисниченко Денис Николаевич

Ошибка 0x0000002B: стек переполнен Ошибка переполнения стека. Встречается довольно редко. Нужно выяснить виновника «торжества» – проследите, после чего возникает данная ошибка, при каких условиях. Хотя, скорее всего, данную ошибку вы не увидите – такая она


Класс стек

Из книги Основы объектно-ориентированного программирования автора Мейер Бертран

Класс стек Этот пример даст возможность ознакомиться с практическим использованием утверждений. В предыдущей лекции была дана схема параметризованного класса "стек" в форме:class STACK [G] feature... Объявление компонент:count, empty, full, put, remove, itemendРеализация появится ниже. До


Класс стек

Из книги Серверные технологии хранения данных в среде Windows® 2000 Windows® Server 2003 автора Дайлип Наик

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


3.2 Сетевой стек Windows NT

Из книги О чём не пишут в книгах по Delphi автора Григорьев А. Б.

3.2 Сетевой стек Windows NT Разобраться в особенностях стека сетевого ввода-вывода Windows NT важно по нескольким причинам. Клиент Windows NT использует стек сетевого ввода-вывода для получения доступа к ресурсам, которые находятся под управлением сервера, а также для передачи данных.


2.1.4. Стек TCP/IP

Из книги Программирование на языке Ruby [Идеология языка, теория и практика применения] автора Фултон Хэл

2.1.4. Стек TCP/IP Физический и канальный уровни полностью реализуются сетевой картой или модемом (или другим устройством, выполняющим ту же функцию) и ее драйвером. Здесь действительно достигнута настолько полная абстракция, что программист обычно не задумывается о том,


9.2.3. Стек и рекурсия

Из книги QNX/UNIX [Анатомия параллелизма] автора Цилюрик Олег Иванович

9.2.3. Стек и рекурсия В качестве примера изоморфизма, существующего между стеком и рекурсией, рассмотрим классическую задачу о Ханойской башне.По легенде где-то далеко на востоке существует старинный храм. Обитающие в нем монахи заняты решением единственной задачи:


Стек

Из книги Искусство программирования на языке сценариев командной оболочки автора Купер Мендель

Стек Стек – абстрактная структура данных, устроенная по принципу LIFO «последний вошел – первый вышел» (last in, first out – LIFO). Наглядно стек может быть представлен стопкой подносов в кафетерии. Например, если кто-то кладет поднос на вершину стопки, то этот поднос будет первым,


Пример 25-9. Эмуляция структуры "СТЕК" ("первый вошел -- последний вышел")

Из книги Недокументированные и малоизвестные возможности Windows XP автора Клименко Роман Александрович

Пример 25-9. Эмуляция структуры "СТЕК" ("первый вошел -- последний вышел") #!/bin/bash# stack.sh: Эмуляция структуры "СТЕК" ("первый вошел -- последний вышел")# Подобно стеку процессора, этот "стек" сохраняет и возвращает данные по принципу#+ "первый вошел -- последний вышел".BP=100 #


Стек протоколов TCP/IP

Из книги Разработка ядра Linux автора Лав Роберт

Стек протоколов TCP/IP Стек протоколов TCP/IP является основным и единственным способом взаимодействия конечного компьютера с глобальной сетью Интернет, а также основным стеком взаимодействия с другими компьютерами сети. Именно поэтому было решено рассказать в этой главе и


Маленький стек фиксированного размера

Из книги автора

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