firstPtr

iBStPtr

currentPtr

lastPtr

firstPtr

tempPtr

Рис. 15.8. Графическое представление выполнения функции removeFromBack

8) Операция delete освобождает область памяти, выделенную для узла, на который указывает tempPtr.

9) Возвращается 1, что указывает на успешное удаление.

Рис. 15.8 иллюстрирует выполнение функции removeFromFront. На рис. 15.8 а) показано состояние списка до операции удаления. На рис. 15.8 Ь) показаны реализованные операции с указателями.

Функция print сначала определяет, не является ли список пустым, Если он пустой, то функция print печатает сообщение Список пуст и завершает работу. В противном случае, она печатает данные, входящие в список. Функция создает экземпляр указателя currentPtr как копию указателя firstPtr и затем печатает сообщение Список состоит из: . Пока указатель currentPtr не является нулевым, в цикле печатается currentPtr->data и указателю currentPtr присваивается значение currentPtr->nextPtr. Заметим, что, если указатель связи в последнем узле списка не является нулевым, то алгоритм печати будет ошибочно выводить на печать данные после конца списка. Алгоритм печати является одинаковым для связных списков, стеков и очередей.

15.5. Стеки

Стек является частным случаем связного списка, в котором новые узлы Morjrr добавляться в стек и удаляться (выталкиваться) из него только на его вершине. По этой причине, стек является структурой данных типа последним вошел - первым вышел (last-in, first-out - LIFO). Элемент связи в последнем узле стека устанавливается на нуль для того, чтобы показать дно стека.

Типичная ошибка программирования 15.6

Не осуществляется уаановка указателя связи на нуль в узле, являющемся дном стека.

Основными функциями-элементами, используемыми для манипуляций со стеком, являются push и pop. Функция push добавляет новый узел на вершину стека. Функция pop удаляет (выталкивает) узел из вершины стека, сохраняет удаляемое значение в переменной ссылке, которая передается вызывающей программе, и возвращает 1, если действие функции pop было успешным, или О в противном случае.

У стеков имеется много интересных приложений. Например, когда происходит вызов функции, вызываемая функция должна знать, как вернуться в вызывающую функцию; в этом случае адрес возвращения помещается в стек. Если происходит ряд обращений к функциям, то последовательность адресов возвращения помещается в стек по принципу последним вошел - первым вышел для того, чтобы каждая функция могла вернуться в свою вызывающую функцию. Стеки поддерживают как рекурсивные вызовы функций, так и обычные нерекурсивные.

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

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

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

Программа на рис. 15.9 (вывод данных этой программы показан на рис. 15.10) создает шаблон класса стеков главным образом посредством скрытого наследования шаблона класса списков. Потребуем, чтобы у стека имелись фунции-элементы push, pop, isStackEmpty и printStack. Заметим, что они, по существу, являются соответственно функциями шаблона класса списков insertAtFront, removeFromFront, isEmpty и print. Конечно, шаблон класса списков включает и другие функции-элементы (например, insertAtBack и removeFromBack), которые нам не хотелось бы делать доступными через открытый интерфейс класса стеков. Так что когда мы указываем, что шаблон класса стеков должен наследовать шаблон класса списков, то задаем скрытое наследование. Это приводит к тому, что все функции-элементы шаблона класса списков в шаблоне класса стеков становятся скрытыми. Когда мы реализуем функции-элементы стека, они должны вызывать соответствующие функции-элементы класса списков: push должна вызывать insertAtFront, pop - removeFromFront, isStackEmpty - isEmpty, a функция-элемент print-Stack должна вызывать print.

STACK.Н

Огфеделение шаблона класса Stack, производного от класса List #ifndef STACK H #define STACK H

#include list.h

Hjj

template<class STACKTyPE>

class Stack : private List<STACKTYPE> {

public:

void push(const STACKTYPE &d) { insertAtFront(d); } int pop(STACKTYPE &d) { return removeFromPront(d); } int isStackEmpty() const { return isEmpty(); } void printStackO const { print (); }

#endif

STACKDRV.CPP

Драйвер проверки шаблона класса Stack tinclude <iostream.h> tinclude stack.h

main ( ) {

Stack<int> intStack; int poplnteger;

cout << обработка стека с целыми числами << endl;

for (int i = 0; i < 4; i++) { intStack.push(i); intStack.printStack();

while (!intStack.isStackEmpty0) (

intStack.pop(poplnteger); cout << poplnteger << выталкивается из стека <<endl; intStack.printStack(); }

Stack<float> floatStack; float val = 1.1, popFloat;

cout << обработка стека с числами с плавающей точкой << endl;

for (i = 0; i < 4; i++) { floatStack.push(val) ; floatStack.printStack() ; val += 1.1;

while (tfloatStack.isStackEmpty0) { floatStack.pop(popFloat) ;

cout << popFloat << выталкивается из стека floatStack.printStack() ;

endl;

Ш }

return 0;

Рис. 15.9. Простая программа стека