Ссылочная реализация стека в динамической памяти

Более гибким и экономичным способом с точки зрения затрат памяти является ссылочная реализация стека. В этом случае память под каждый новый элемент, помещаемый на вершину стека, выделяется динамически, поэтому теоретически размер стека не ограничен (на практике, конечно, существуют разумные ограничения). При удалении элемента занимаемая им память немедленно освобождается, таким образом, вся структрура занимает ровно столько ячеек памяти, сколько ей требуется в данный момент. Но не нужно забывать, что каждый элемент стека требует больше памяти, чем при реализации с помощью массива, так как в каждом элементе нужно хранить еще и указатель на предыдущий элемент.

Рисунок 2.2. поясняет идею cсылочной реализации стека. Отдельный указатель содержит адрес самого последнего элемента, который будет вершиной стека (top).

Рис.2.2. Ссылочная реализация стека с помощью списка в динамической памяти

Определим структуру элемента стека, продемонстрировав применение шаблонов для указания произвольного типа содержательной части:

template <class T> // шаблонный тип элементов стека

struct item //структура каждого элемента стека

{ T data; // данные

item<T> *prev; // указатель на предыдущий элемент

};

Как видно из рисунка 2.2, для реализации базовых функций стека требуется только один указатель на вершину (top). В остальном определение структуры выполняется аналогично определению предыдущей реализации на основе массива, небольшие отличия в синтаксисе связаны с использованием шаблонов.

template <class T> struct stack //структура стека

{ item<T> *top;

// базовые функции для работы со стеком

stack() {top=NULL;} //конструктор, создание пустого стека

void push (T x); // поместить значение x в стек

void pop();// извлечь элемент с вершины стека

T gettop();// получить вершину стека

bool isnull() {return top==NULL;} // проверка на пустоту

void makenull(); // дополнительная функция очистки стека

};

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

Для вставки необходимо:

· захватить память под новый элемент, заполнить данными содержательную часть;

· указующей части присвоить значение указателя на вершину;

· присвоить указателю на вершину адрес нового элемента (он теперь будет вершиной).

template <class T> void stack<T>::push(T x)

{ item<T> *p=new item<T>;

p->data=x; p->prev=top; // добавили элемент

top=p; // изменили указатель на вершину top

}

При извлечении элемента необходимо:

· изменить указатель на вершину стека (теперь вершиной будет предпослений элемент);

· освободить память, которую занимал последний элемент;

template <class T> void stack<T>::pop ()

{ if (isnull()) {cerr<< "Стек пуст \n"; exit(1);};

item<T> *p=top; top=top->prev; // изменили указатель top

delete p; // удалили элемент

}

Возвратить последний элемент из буфера не представляет труда:

template <class T> T stack<T>::gettop()

{ if (isnull()) {cerr<< "Стек пуст \n"; exit(1);};

return top->data;

}

Дополнительная функция очистки стека реализуется через базовые:

template <class T> void stack<T>::makenull()

{ while (!isnull()) pop(); // удаляем элементы по очереди

}

При использовании данной реализации описание конкретного стека с элементами, например, типа char, будет иметь вид

stack<char> имя;

В прикладных программах-клиентах, использующих стеки, можно пользоваться любой реализацией, при этом будем иметь одинаковую функциональность. В дальнейшем будем считать, что шаблон стека находится в файлах stack.h (интерфейс) и stack.cpp (реализация), который можно подключать к различным программам, использующим стек как элементарную структуру данных.

Примеры программ с использованием стеков

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

Пример 1.

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

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

Листинг 2.1 Проверка правильности расстановки всех видов скобок в строке

#include <iostream.h>

#include "stack.h"

#include "stack.cpp"

void main()

{ char s[80];

cout<<"Введите строку, содержащую скобки "; cin.getline(s,80);

stack<char> st;

char *kind1="([{", *kind2=")]}";

for (int i=0; i<strlen(s); i++)

{ if(strchr(kind1,s[i])) st.push(s[i]);

if(strchr(kind2,s[i]))

if((st.isnull())||(strchr(kind1,st.pop())-kind1!=strchr(kind2,s[i])-kind2))

    { cout<<"Ошибка!";cin.get(); return;

    }

}

if (!st.isnull()) cout<<"Ошибка!";

else cout<<"Ошибок нет";

st.makenull(); cin.get();

}

Пример 2.

Усложним задачу. Пусть имеется скобочное выражение, в котором присутствуют только круглые скобки. Требуется скобки самого глубокого уровня вложенности оставить без изменения, скобки следующего уровня заменить на квадратные, а все остальные скобки заменить на фигурные.

Листинг 2.2 Преобразование скобок

#include <iostream.h>

#include "stack.h"

#include "stack.cpp"

int main()

{ char s[80]; stack<char> st;

cout<<"Введите строку, содержащую только круглые скобки "; cin.getline(s,80);

int l; //Уровень вложеннности скобок в данный момент

for (int i=0; i<strlen(s); i++)

{ if (s[i]=='(') {st.push(i); l=1;}

  if (s[i]==')')

     if (st.isnull()) {cout<<"Ошибка!!!"; cin.get(); return 1;}

     else {

        int p=st.pop();

        if (l==2) {s[p]='['; s[i]=']';}

        if (l>2) {s[p]='{'; s[i]='}';}

        l++;

     }

}

if (!st.isnull()) cout<<"Ошибка!!!";

else cout<<"Получили:\n"<<s;

st.makenull(); cin.get();

}

Реализация очередей