#include <vector>

class iStack { public:

iStack( int capacity )

: stack( capacity ), top( 0 ) {}

bool pop( int &va1ue ); boot push( int value );

bool full();

bool empty();

void display(); int size();

private:

int top;

vector< int > stack; типа int. Вот объявление нашего класса:

В данном случае мы используем вектор фиксированного размера: для иллюстрации использования префиксных и постфиксных операций инкремента и декремента этого достаточно. (В главе 6 м1 модифицируем наш стек, придав ему возможность динамически меняться.)

Элементы стека хранятся в векторе stack. Переменная top содержит индекс первой свободной ячейки стека. Этот индекс одновременно представляет количество заполненных ячеек. Отсюда реализация функции size() : она должна просто возвращать текущее значение top.

inline int iStack::size() { return top; };

empty() возвращает true, если top равняется 0; full() возвращает true, если top равен stack.size()-1 (напомним, что индексация вектора начинается с 0, поэтому мы

inline bool iStack::empty() { inline bool iStack::full() {

{ return top ? false : true; } return top < stack.size()-l ? false : true;

должны вычесть 1).

4.15. Пример: реализация класса Stack

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

Как уже было сказано, с этой структурой возможны две основные операции - поместить элемент (push) и извлечь (pop) его. Другие операции позволяют получить информацию о текущем состоянии стека - пуст он (empty() ) или полон (full() ), сколько элементов в нем содержится (size()). Для начала наш стек будет предназначен лишь для элементов

bool iStack::pop( int stop va1ue ) {

if ( empty() )

return false;

top value = stack[ -- top ];

cout << iStack::pop(): << top value << endl; return true;

bool iStack::push( int value ) {

cout << iStack::push( << value << )\n ;

if ( full() )

return false;

stack[ top++ ] = value; return true;

них, чтобы следить за ходом выполнения:

Прежде чем протестировать наш стек на примере, добавим функцию display() , которая позволит напечатать его содержимое. Для пустого стека она выведет:

i ( 0 )

Для стека из четырех элементов - 0, 1, 2 и 3 - результатом функции display() будет:

[ ( 4 )( bot: 0 1 2 3 :top )

void iStack::display() {

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

for ( int ix = 0; ix < top; ++ix )

cout << stack[ ix ] << ;

cout << :top )\n ; Вот реализация функции display() :

А вот небольшая программа для проверки нашего стека. Цикл for выполняется 50 раз. Четное значение (2, 4, 6, 8 и т.д.) помещается в стек. На каждой итерации, кратной 5 (5, 10, 15...), распечат1вается текущее содержимое стека. На итерациях, кратных 10 (10, 20, 30...), из стека извлекаются два элемента и его содержимое распечатывается еще раз.

Вот реализация функций pop() и push() . Мы добавили операторы вывода в каждую из

#inc1ude <iostream> #inc1ude iStack.h

int main() {

iStack stack(

32 ) ;

stack.display();

for ( int ix = 1; ix < 51; ++ix )

if ( ix%2 == 0 )

stack.push( ix );

if ( ix%5 == 0 )

stack.display();

if ( ix%10 == 0 ) {

int dummy;

stack.pop( dummy ); stack.pop( dummy stack.display();

Вот результат работы программы:

( 0 )( bot: :top )

iStack push( 2 ) iStack push( 4 ) ( 2 )( bot: 2 4 :top )

iStack push( 6 )

iStack push( 8 )

iStack push ( 10 )

( 5 )( bot: 2 4 6 8 10 :top )

iStack pop(): 10

iStack pop(): 8

( 3 )( bot: 2 4 6 :top )

iStack push( 12 )

iStack push( 14 )

( 5 )( bot: 2 4 6 12 14 :top )

iStack::push( 16 ) iStack::push( 18 ) iStack::push( 20 )

( 8 )( bot: 2 4 6 12 14 16 18 20 :top )

iStack::pop(): 20

iStack::pop(): 18

( 6 )( bot: 2 4 6 12 14 16 :top )

iStack::push( 22 )

iStack::push( 24 )

( 8 )( bot: 2 4 6 12 14 16 22 24 :top ) iStack::push( 26 ) iStack::push( 28 ) iStack::push( 30 )

( 11 )( bot: 2 4 6 12 14 16 22 24 26 28 30 :top ) iStack::pop(): 30 iStack::pop(): 28

( 9 )( bot: 2 4 6 12 14 16 22 24 26 :top )

iStack::push( 32 )

iStack::push( 34 )

( 11 )( bot: 2 4 6 12 14 16 22 24 26 32 34 :top )

iStack::push( 36 )

iStack::push( 38 )

iStack::push( 40 )

( 14 )( bot: 2 4 6 12 14 16 22 24 26 32 34 36 38 40 :top ) iStack:: рор(): 40 iStack::popQ: 38

( 12 )( bot: 2 4 6 12 14 16 22 24 26 32 34 36 :top )

iStack::push( 42 )

iStack::push( 44 )

( 14 )( bot: 2 4 6 12 14 16 22 24 26 32 34 36 42 44 :top )

iStack::push( 46 )

iStack::push( 48 )