2.2.2 Примеры реализации динамических структур на основе указателей
В качестве примеров рассмотрим реализацию двух часто используемых структур данных – стека и очереди. В связи с большой востребованностью в стандартной библиотеке C++ имеются шаблонные типы stack и queue, на основании которых можно создавать стеки и очереди с любым типом элементов (например, stack<int>, queue<char> и т.д.). Так что наши примеры имеют чисто учебное назначение. Тем не менее, на них можно хорошо понять логику реализации любой динамической структуры.
Стек (stack) — это специальный тип списка, в котором все вставки и удаления элементов выполняются только на одном конце, называемом вершиной (top). Такой метод доступа обозначается аббревиатурой LIFO (last-in-first-out — последним пришел — первым вышел).
Основные операции со стеками имеют сложившиеся названия, которыми мы, естественно, воспользуемся.
Вставка значения х в вершину стека (элемент заталкивается в стек) — операция Push.
Извлечение элемента с вершины непустого стека (элемент выталкивается из стека) — операция Pop;
Проверка стека на наличие в нем хотя бы одного элемента – логическая функция empty
Добавим ещё дополнительную функцию size, которая вычисляет количество элементов в стеке, - с её помощью можно продемонстрировать обход стека.
память под каждый новый элемент, помещаемый на вершину стека, выделяется динамически, поэтому теоретически размер стека не ограничен (на практике, конечно, существуют разумные ограничения). При удалении элемента занимаемая им память немедленно освобождается, таким образом, вся структура занимает ровно столько ячеек памяти, сколько ей требуется в данный момент. Но не нужно забывать, что каждый элемент стека требует больше памяти, чем при реализации с помощью массива, так как в каждом элементе нужно хранить еще и указатель на предыдущий элемент.
Рисунок 2.3. поясняет идею cсылочной реализации стека. Отдельный указатель содержит адрес самого последнего элемента, который будет вершиной стека ( top).
Рисунок 2.3. Ссылочная реализация стека с помощью списка в динамической памяти
При такой организации можно легко добавлять элементы на вершину, а также удалять их.
Для вставки необходимо:
захватить память под новый элемент, заполнить данными содержательную часть;
указующей части присвоить значение указателя на вершину;
присвоить указателю на вершину адрес нового элемента (он теперь будет вершиной).
Для извлечения элемента:
запомнить в буфере данные, хранящиеся в последнем элементе;
освободить память, которую занимал последний элемент;
изменить указатель на вершину стека (теперь вершиной будет предпоследний элемент);
возвратить последний элемент из буфера.
Представленный листинг программы содержит реализацию всех перечисленных операций над стеком – каждая в виде отдельной функции. Конечно, мы могли бы представить здесь и шаблонный класс, как в стандартной библиотеке, но не будем забегать вперёд в процессе обучения. А для того, чтобы сделать реализацию относительно независимой от типа элементов стека, воспользуемся скромными возможностями оператора typedef.
Обратите внимание, что в функции push и pop указатель передаётся по ссылке (*&top).
Пример получился довольно объёмным, потому что в функции main() представлена одна из задач, для решения которой удобно использовать стек. Суть задачи такова – вводится выражение, содержащее круглые скобки. Требуется скобки самого глубокого уровня вложенности оставить без изменения, скобки следующего уровня заменить на квадратные, а все остальные скобки заменить на фигурные.
// Пример 2.2 - реализация стека с примером использования стека
// для замены скобок в скобочном выражении
#include <iostream>
using namespace std;
typedef int type_of_data; // тип элементов (может быть любым, int - пример)
struct item //структура каждого элемента стека
{
type_of_data data; // данные
item *prev; // указатель на предыдущий элемент
};
// прототипы функций
void push (type_of_data, item *&); // поместить значение в стек
type_of_data pop(item *&);// извлечь элемент с вершины стека
int size(item *); //размер стека
bool empty(item *top) {return top==NULL;} // проверка на пустоту
void push (type_of_data x, item *&top)
{
item *p=new item; p->data=x; p->prev=top; // добавили элемент
top=p; // изменили указатель на вершину top
}
type_of_data pop ( item *&top)
{
if (empty(top)) {cerr<< "Error"; return 1;} // аварийная ситуация
type_of_data d=top->data; // запомнили данные последнего элемента
item *p=top; top=top->prev;delete p;//удалили элемент и изменили top
return d; // возвратили данные
}
int size(item *top)
{
item *p=top; int cnt=0;
while (p) {p=p->prev; cnt++;} //обошли все элементы стека
return cnt;
}
int main(){ замена круглых скобок на квадратные и фигурные
item *top=NULL; // создали пустой стек
char s[80]; cout<<"? "; cin.getline(s,80);
int l; //Уровень вложенности скобок в данный момент
for (int i=0; s[i]!=0; i++)
{
if (s[i]=='(') {push(i,top); l=1;}
if (s[i]==')')
if (empty(top)) {cout<<"Error!!!";}
else
{
int p=pop(top);
if (l==2) {s[p]='['; s[i]=']';}
if (l>2) {s[p]='{'; s[i]='}';}
l++;
}
}
if (!empty(top)) cout<<"Error!!!";
else cout << s;
system("pause"); return 0;
}
Здесь хотелось бы обратить внимание на тот факт, что в процессе извлечения данных из стека может возникнуть аварийная (исключительная) ситуация, если стек оказался пустым. Проблема корректной обработки исключительных ситуаций будет далее подробно обсуждаться в пособии, в данном случае мы пошли по самому простому пути – вывода сообщения об ошибке в выходной поток cerr (вместо cout). Такой способ сейчас используется редко, но другого мы пока не знаем.
Очередь (queue) - это другой специальный тип списка, где элементы вставляются в конец списка, называемый хвостом, а удаляются из начала списка, называемого головой. Очереди также называют "списками типа FIFO" (аббревиатура FIFO расшифровывается как first-in-first-out: первым вошел — первым вышел). Операции, выполняемые с очередями, аналогичны операциям со стеками.
Для обозначения операций над очередью воспользуемся теми же словами push и pop, как и для стека, поскольку так они обозначаются в стандартной библиотеке. Для головы и хвоста очереди тоже будем использовать обозначении из библиотеки – front (начало, голова) и back (конец, хвост).
Для реализации очереди, как и стека, достаточно иметь в каждом элементе по одному указателю на следующий элемент, как показано на рисунке 2.4. Но поскольку вставка и удаление выполняются на разных концах, то для эффективной реализации нужно хранить два дополнительных указателя — на хвост и голову очереди.
Рисунок 2.4 Представление очереди при помощи связного списка
Выполнение операций добавления и удаления элементов выполняются немного сложнее, чем для стека, поэтому поясним их рисунками 2.5. и 2.6.
При добавлении элемента в хвост очереди достаточно:
захватить под него память, заполнить информационную часть данными, указателю присвоить пустое значение;
изменить указующую часть элемента, бывшего последним;
присвоить указателю на хвост адрес добавленного элемента — он теперь будет хвостом очереди (рисунок 2.5)
Рис.2.5. Добавление элемента в очередь
Удаление из головы очереди также выполняется просто — достаточно изменить указатель на голову и освободить память, которую занимал элемент, воспользовавшись буферной переменной (рисунок 2.6).
Рисунок 2.6 Удаление (извлечение) элемента из очереди
Ниже приведена реализация очереди в динамической памяти. Функция main на этот раз просто демонстрирует работоспособность основных функций для работы с очередью.
// Пример 2.3 - реализация очереди
#include <iostream>
using namespace std;
typedef int type_of_data; // тип элементов (может быть любым, int - пример)
struct item //структура каждого элемента очереди (аналогична стеку)
{
type_of_data data; // данные
item *next; // указатель на следующий элемент
};
void push (type_of_data, item *&, item *&);// добавить элемент
type_of_data pop(item *&);// извлечь элемент
void show_queue(item *); //вывести элементы очереди на экран
bool empty(item *front) {return front==NULL;} // проверка на пустоту
void push (type_of_data x, item *&front, item *&back)
{
if (empty(front)) //добавление первого элемента в пустую очередь
{ front=new item; front->data=x; front->next=NULL; back=front;
}
else // добавление в непустую очередь
{
item *i=new item; i->data=x;
i->next=NULL; back->next=i; back=i;
}
}
type_of_data pop ( item *&front)
{
if (empty(front)) { cerr << "Error!"; return 1; }
// запомнили данные и указатель
type_of_data x=front->data; item *i=front->next;
delete front; front=i; // удалили голову и переставили указатель
return x; // возвратили данные
}
void show_queue(item *front)
{
item *p=front;
while (p) {
// выводим элемент и идём дальше
cout << p->data <<' '; p=p->next;
}
cout<<endl;
}
int main(){
item *front=NULL, *back=NULL;
for( int i=1; i<=10; i++) push(i, front,back);
show_queue(front);
cout<<pop(front)<<endl; show_queue(front);
system("pause"); return 0;
}
Заметим, что кроме традиционных указателей, в C++ можно (и рекомендуется) использовать так называемые "умные" указатели, реализованные в виде шаблонных классов − о них речь пойдёт в главе 8.