, Обработка стека с целыми числами

ИТ Список состоит иэ: О

Список состоит иэ: 10

Список состоит из: 2 1 О

Список состоит иэ: 3 2 10

13 выталкивается из стека

Список состоит из: 2 10

2 выталкивается иэ стека Список состоит из: 10

1 выталкивается иэ стека Список состоит из: О

О вытсшкивается из стека Список пуст

г; обработка стека с числгши с плавгиощей точкой

Список состоит из: 1.1

Список состоит из: 2.2 1.1

Список состоит иэ: 3.3 2.2 1.1

: Список состоит иЭ: 4.4 3.3 2.2 1.1

4.4 выталкивается из стека Список состоит из: 3.3 2.2 1.1

3.3 выталкивается из стека Список состоит из: 2.2 1.1

2.2 выталкивается из стека Список состоит из: 1.1

J 1.1 вытсшкивается иэ стека Список пустой

Все узлы удалены - Все узлы удалены

Рис. 15.10. Пример вывода программы, приведенной на рис. 15.9

Шаблон класса стеков используется в функции main для реализации стека intStack типа Stack<int> с целыми числами. Целые значения от О до 3 помещаются в стек intStack и затем выталкиваются из него. Шаблон класса стеков используется также для реализации стека со значениями с плавающей запятой floatStack типа Stack<float>. Значения с плавающей точкой 1.1, 2.2, 3.3 и 4.4 помещаются в стек floatStack и затем выталкиваются из него.

/ / Значение помещается в стек template<class STACKTYPE>

void Stack<STACKTYPE>::push(const STACKTYPE Svalue) { s.insertAtFront(value) ; }

Значение выталкивается из стека template<class STACKTYPE>

int Stack<STACKTYPE>::pop(STACKTYPE Svalue) { return s.removeFromFront(value) ; }

Является ли стек пустым ? template<class STACKTYPE>

int Stack<STACKTYPE>::isStackEmpty0 const { return s.isEmpty(); }

Оотображение содержимого стека template<class STACKTYPE>

void Stack<STACKTYPE>::printStack0 const { s.printO; } #endif

Рис. 15.11. Пример программы стека, использующей композицию

Другим способом реализации шаблона класса стеков является повторное использование шаблона класса списков посредством создания композиции. Программа, приведенная на рис. 15.11, использует заголовочные файлы list.h и listnd.h. Она также использует ту же самую программу драйвер, что и предыдущая программа для стека, за исключением нового заголовочного файла stack c.h, который заменяет заголовочный файл stack.h. Вывод является тем же самым. Определение шаблона класса стеков теперь включает объект-элемент s типа List<STACKTYPE>.

STACK C.H

Определение класса Stack как композиции объектов класса List ifndef STACK C define STACK C

iinclude list.h

,emplate<class STACKTYPE> ass Stack { )lic:

конструктор отсутствует; инициализируется конструктор класса List

void push(const STACKTYPE &); int pop(STACKTYPE &); int isStackEmpty() const; void printStack0 const; private:

List<STACKTYPE> s;

15.6. Очереди

Другой стандартной структурой данных является очередь. Очередь аналогична очереди людей в супермаркете: первый клиент в ней обслуживается первым, а другие клиенты занимают очередь с конца и ожидают, когда их обслужат. Узлы очереди удаляются только из головы очереди, а помещаются в очередь только в ее хвосте. По этой причине, очередь - это структура данных типа первым вошел - первым вышел ( first-in, first-out - FIFO). Операции поместить в очередь и удалить из нее известны как enqueue и dequeue соответственно.

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

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

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

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

QUEUE.Н

Определение шаблона класса Queue (производного от класса List) #ifndef QUEUE H #define QUEUE H #include list.h

template<class QUEUETYPE> class Queue: private List<QUEUETYPE> { public:

void enqueue (const QUEUETYPE &d) { insertAtBacl< (d) ; } int dequeue(QUEUETYPE &d) { return removeFromFront(d); } int isQueueEmpty () const { return isEmptyO; } void printQueueO const { print () ; }