Адаптеры контейнеров

5.1. Стеки

Стек (stack) представляет собой структуру данных, которая допускает только две операции, изменяющие ее размер: push (для добавления элемента в конце) и pop (для удаления элемента в конце). Иными словами, стек работает по принципу последний пришел - первый ушел (также называемому LIFO от английского Last In - First Out). Кроме push и pop для стека определены также функции-члены empty и size, имеющие обычное значение, и top (вместо back) для доступа к последнему элементу.

Стек может быть реализован с помощью каждого из трех последовательных контейнеров STL: вектора, двусторонней очереди и списка. Следовательно, стек не является новым типом контейнера, а особым вариантом вектора, двусторонней очереди либо списка, отсюда и происхождение термина адаптер контейнера.

В качестве примера используем стек для чтения последовательности целых чисел и отображения их в обратном порядке. Любой нецифровой символ будет признаком конца ввода. В следующей программе стек реализован вектором, но программа также будет работать, если мы заменим всюду vectoma deque или list. Кроме тогр, программа показывает, как работают функции-члены empty, top и size.

stackl.cpp: Используем стек для чтения

последовательности целых чисел произвольной длины

и отображения этой последовательности

в обратном порядке.

Iinclude <iostream> Iinclude <vector> Iinclude <stack> using namespace std;

int mainO

{ stack <int, vector<int> > S; int x; cout

Enter some integers, followed by a letter:\n ; while (cin x) S.push(x); while (!S.empty0) { X = S.top();

cout Size: S.sizeO

Element at the top: x endl;

S.popO ;

return 0;

Согласно проекту стандарта С++ шаблон stack имеет два параметра, как написано в приведенной программе:

stack <int, vector<int> > S;

В версии HP STL первый из этих аргументов отсутствует, поэтому, если вы используете эту (устаревшую) версию, необходимо данную строчку программы заменить на

stack < vector<int> > S;

После того как числа, введенные пользователем, будут положены на стек, программа последовательно нужное количество раз отобразит текущий размер стека и элемент, который будет удален следующим, как в приведенном примере:

Enter some integers, followed by a letter: 10 20 30 A

Size: 3 Element at the top: 30 Size: 2 Element at the top: 20 Size: 1 Element at the top: 10

Для стеков мы не можем использрвать итераторы, а также не можем получить доступ к произвольному элементу стека без изменения его размера.

СтекЗ < Стеки Рисунок 5.1. Лексикографическое сравнение стеков

Первыми сравниваются элементы в низу стека. Поскольку оба они равны 10, происходит сравнение следующих за ними элементов 20 и 21. В нашем примере S < U, потому что 20 < 21. Это сравнение выполняется таким же образом, как и сравнение строк, только для строк мы начинаем сравнение с первых символов, а для стека - с нижних элементов.

Стек определяет операторы присваивания (=) и сравнения (== и <). Отсюда следует (см. раздел 2.8), что для стеков можно использовать также остальные четыре оператора сравнения. Оператор < осуществляет лексикографическое сравнение, как показывает следующая программа:

stackcmp.cpp: Сравнение и присваивание для стеков, ♦include <iostream> ♦include <vector> ♦include <stack> using namespace std;

int mainO

{ stack <int, vector<int> > S, T, U; S.push(lO); S.push(20); S.push(30); cout Pushed onto S: 10 20 30\n ; T = S;

cout After T = S; we have ;

cout (S == T ? S == T : S != T ) endl;

U.push(lO); U.push(21);

cout Pushed onto U: 10 21\n ;

cout << We now have ;

cout (S < и ? S < U : S >= U ) endl; return 0;

Вывод программы:

Pushed onto S: 10 20 30 After T = S; we have S == T Pushed onto U: 10 21 We now have S < U

Рисунок 5.1 иллюстрирует последнее сравнение.