Стеки, очереди, деки

1.

Стеки
Стек является одной из наиболее используемых и наиболее важных структур
данных.
Стеки применяются очень часто, например :
• распознавание синтаксиса в компиляторе, как и оценка выражений, основано на
стеке;
• на нижнем уровне стеки используются для передачи параметров функциям,
выполнения вызова функции и возвращения из нее;
• реализация рекурсии;
• при работе с памятью, например, работа функций printf и scanf основана на
использовании стека;
• для того, чтобы определить, является ли предложение палиндромом
(палиндром – это строка, которая читается одинаково в прямом и в обратном
направлениях);
• для вывода данных с различными основаниями;
• при разработке электронных калькуляторов.

2.

Стек – это последовательный список переменной длины, включение и
исключение элементов из которого производится только с одной стороны.
(англ. stack [stæk] — стопка, пачка)
Стеки иногда называют магазинами.
Для обозначения стеков часто используется аббревиатура LIFO
( last-in / first-out – «последний вошел – первый вышел»).
Стек используют для хранения элементов, доступных в вершине списка (top).
Структура стека аналогична стопке тарелок на полке буфета или стопке книг.
В этих примерах можно взять только верхний предмет, а добавить новый
предмет можно, только положив его сверху.
В структуре стека важное место занимают операции добавления и удаления
элементов:
• Операция Push добавляет элемент в вершину стека.
• Операция Pop удаляет элемент из стека.
2

3.

Абстрактное понятие стека допускает неопределенно большой список.
Логически подносы в столовой могут складываться бесконечно. В
действительности подносы находятся на полке, а овощи нанизаны на
коротких шампурах. Когда полка или шампур переполнены, мы не можем
добавить (Push) еще один элемент в стек.
Стек достигает максимального количества элементов, которыми он может
управлять. Эта ситуация поясняет значение условия полного стека (stack full).
Другая крайность — вы не можете взять поднос с пустой полки. Условие
пустого стека (stack empty) подразумевает, что вы не можете удалить (Pop)
элемент.
Описание ADT Stack включает только условие пустого стека. Условие полного
стека является уместным в том случае, если реализация содержит верхнюю
границу размера стека.
3

4.

ADT Stack (абстрактный тип данных)
Данные
Список элементов с позицией top, указывающей на вершину стека.
Операции
Конструктор
Начальные значения: Нет.
Процесс:
Инициализация вершины стека.
StackEmpty
Вход:
Предусловия:
Процесс:
Выход:
Постусловия:
Нет
Нет
Проверка, пустой ли стек.
Возвращать True, если стек пустой, иначе возвращать False.
Нет
Push
Вход:
Предусловия:
Процесс:
Выход:
Постусловия:
Элемент для стека.
Нет.
Сохранение элемента в вершине стека.
Нет.
Стек имеет новый элемент в вершине.
4

5.

Pop
Вход:
Предусловия:
Процесс:
Выход:
Постусловия:
Нет
Стек не пустой.
Удаление элемента из вершины стека.
Возвращать элемент из вершины стека.
Элемент удаляется из вершины стека.
Peek
Вход:
Предусловия:
Процесс:
Выход:
Постусловия:
Нет.
Стек не пустой.
Нахождение значения элемента в вершине стека.
Возвращать значение элемента из вершины стека.
Стек неизменный.
ClearStack
Вход:
Предусловия:
Процесс:
Выход:
Постусловия:
Нет.
Нет.
Удаление всех элементов из стека и переустановка вершины стека.
Нет.
Стек переустановлен в начальные условия.
Конец ADT Stack
5

6.

LIFO (last-in/first-out – «последний вошел – первый вышел»)
C
B
B
B
D
A
A
A
A
A
A
Push A
Push B
Push C
Pop
Pop
Push D
При реализации стека на основе одномерного массива размер стека ограничен
максимальным количеством элементов массива. При этом может возникнуть
проблема переполнения.
6

7.

При реализации стека с помощью указателей размер стека ограничен
доступным объемом свободной памяти.
Графическая структура стека изображена на рисунке.
Вершина стека
top
Данные n
Указатель
Данные n-1
Указатель
…
Данные 2
Указатель
Данные 1
Указатель
NULL
7

8.

Класс Stack
Члены класса Stack включают список, индекс или указатель на вершину стека и
набор стековых операций.
Для хранения элементов стека используется массив.
В результате размер стека не может превысить количества элементов в массиве.
Объявление объекта типа Stack включает размер стека, который определяет
максимальное количество элементов в списке.
Размер имеет значение по умолчанию MaxStackSize = 50.
Список (stacklist),
максимальное количество элементов в стеке (size)
и индекс (top) являются закрытыми членами,
а операции — открытыми.
8

9.

Первоначально стек пуст и top = -1.
Элементы вводятся в массив (функция Push) в возрастающем порядке индексов
(top = 0, 1, 2)
и извлекаются из стека (функция Pop) в убывающем порядке индексов
(top = 2, 1, 0).
Например, следующий объект является стеком символов (DataType = char).
После нескольких операций Push/Pop индекс top = 2,
а элемент в вершине стека - это stacklist [top] = С.
9

10.

Спецификация класса Stack
//ОБЪЯВЛЕНИЕ
//#include <iostream>
//#include <stdlib.h>
const int MaxStackSize = 50;
class Stack
{
private: // закрытые данные-члены, массив стека и вершина (индекс)
DataType stacklist [MaxStackSize];
int top;
public:
// конструктор; инициализирует вершину
Stack (void) ;
// операции модификации стека
void Push (const DataType& item);
DataType Pop (void) ;
void
ClearStack (void);
// доступ к стеку
DataType Peek (void) const;
// методы проверки стека
int StackEmpty (void) const;
int StackFull (void) const; // реализация массива
};
10

11.

ОПИСАНИЕ спецификации
Данные в стеке имеют тип DataType, который должен определяться с
использованием оператора typedef.
Пользователь должен проверять, полный ли стек, перед попыткой поместить в
него элемент и проверять, не пустой ли стек, перед извлечением данных из
него.
Если предусловия для операции push или pop не удовлетворяются, печатается
сообщение об ошибке и программа завершается.
StackEmpty возвращает 1(True), если стек пустой, и 0 (False) — в противном
случае.
Используется StackEmpty, чтобы определить, может ли выполняться операция
Pop.
StackFull возвращает l(True), если стек полный, и 0 (False) — в противном случае.
Используется StackFull, чтобы определить, может ли выполняться операция
Push.
ClearStack делает стек пустым, устанавливая top = -1. Этот метод позволяет
использовать стек для других целей.
11

12.

Допустим, объявление стека и реализация содержатся в файле astack.h.
typedef int DataType;
…..
#include astack.h;
……
Stack S;
S.Push(10);
cout << S.Peek() << endl;
if (!S.StackEmpty())
temp = S.Pop();
cout << temp << endl;
S.ClearStack();
// включить описание класса Stack
// объявить объект типа Stack
// поместить в стек S значение 10
// напечатать 10
// вытолкнуть 10 из стека и оставить стек пустым
//очистить стек
• ……
12

13.

Реализация класса Stack
// инициализация вершины стека
Stack::Stack (void) : top(-1) { }
//поместить элемент в стек
void Stack::Push (const DataType& item)
{
// если стек полный, завершить выполнение программы
if (top == MaxStackSize-1)
{ cerr << "Переполнение стека!" << endl;
exit(1);
}
// увеличить индекс top и копировать item в массив stacklist
top++;
stacklist[top] = item;
}
13

14.

// взять элемент из стека
DataType Stack::Pop (void)
{ DataType temp;
// стек пуст, завершить программу
if (top = = -1)
{ cerr << "Попытка обращения к пустому стеку! " << endl;
exit(1);
}
// считать элемент в вершине стека
temp = stacklist[top];
// уменьшить top и возвратить значение из вершины стека
top--;
return temp;
}
14

15.

// возвратить данные в вершине стека
DataType Stack::Peek (void) const
{ // если стек пуст, завершить программу
if (top = = - 1)
{cerr << "Попытка считать данные из пустого стека!" << endl;
exit(1);
}
return stacklist[top];
}
15

16.

Для защиты целостности стека класс предусматривает операции тестирования
состояния стека.
// тестирование стека на наличие в нем данных
int Stack::StackEmpty(void) const
{
return (top = = -1);
}
// проверка, заполнен ли стек
int Stack::StackFull(void) const
{
return (top = = MaxStackSize-1);
}
// удалить все элементы из стека
void Stack::ClearStack(void)
{
top = -1;
}
16

17.

Пример применения
Палиндромы.
Когда DataType является типом char, приложение обрабатывает символьный
стек.
Приложение определяет палиндромы, являющиеся строками, которые
читаются одинаково в прямом и обратном порядке.
Пробелы не включаются.
Например, dad, sees являются палиндромами, a good — нет.
17

18.

#include <iostream>
// …
typedef char
DataType;
// элементы стека - символы
#include “astack.h"
// создает новую строку
void Deblank (char *s, char *t)
{
// цикл до тех пор, пока не встретится NULL-символ
while (*s != NULL)
{
//если символ - не пробел, копировать в новую строку
if (*s != ‘ ‘ )
*t++ = *s;
s++;
// передвинуться к следующем символу
}
*t = NULL;
// добавить NULL в конец новой строки
}
18

19.

int main ( )
{
const int True = 1, False = 0;
Stack S;
char palstr[80], destr[80], cr;
int i = 0;
int ispalin = 1;
// полагаем, что строка - палиндром
cin.getline ( palstr,80,’\n ’);
// считать в полную строку
Deblank( palstr, destr );
// удалить пробелы из строки и поместить результат в destr
i = 0;
// поместить символы выражения без пробелов в стек
while ( destr[i] != 0)
{ S.Push ( destr[i] );
i++;
}
i = 0;
// сравнение вершины стека с символами из оригинальной строки
while ( !S.StackEmpty( ) )
{сr= S. Pop ( );
// получить следующий символ из стека
if ( сr != destr [i] )
// если символы не совпадают, прервать цикл
{ ispalin = 0;
// не палиндром
break;
}
i++;
}
if (ispalin)
cout << ispalin<<"\t"<< palstr<<" - palindrom" << "\n";
else
cout << ispalin<<"\t"<<palstr<< " -not palindrom" << "\n";
}
19

20.

Стек является чрезвычайно удобной структурой данных для многих задач вычислительной
техники. Наиболее типичной из таких задач является обеспечение вложенных вызовов
процедур.
Предположим, имеется процедура A, которая вызывает процедуру B, а та в свою очередь процедуру C.
Когда выполнение процедуры A дойдет до вызова B, процедура A приостанавливается и
управление передается на входную точку процедуры B.
Когда B доходит до вызова C, приостанавливается B и управление передается на процедуру C.
Когда заканчивается выполнение процедуры C, управление должно быть возвращено в B,
причем в точку, следующую за вызовом C.
При завершении B управление должно возвращаться в A, в точку, следующую за вызовом B.
Правильную последовательность возвратов легко обеспечить, если при каждом вызове
процедуры записывать адрес возврата в стек.
Так, когда процедура A вызывает процедуру B, в стек заносится адрес возврата в A; когда B
вызывает C, в стек заносится адрес возврата в B.
Когда C заканчивается, адрес возврата выбирается из вершины стека - а это адрес возврата в B.
Когда заканчивается B, в вершине стека находится адрес возврата в A, и возврат из B
произойдет в A.
20

21.

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

22.

В микропроцессорах семейства Intel, как и в большинстве современных
процессорных архитектур, поддерживается аппаратный стек.
Аппаратный стек расположен в ОЗУ, указатель стека содержится в паре
специальных регистров - SS:SP, доступных для программиста.
Аппаратный стек расширяется в сторону уменьшения адресов, указатель его
адресует первый свободный элемент.
Выполнение команд CALL и INT, а также аппаратных прерываний включает в
себя запись в аппаратный стек адреса возврата.
Выполнение команд RET и IRET включает в себя выборку из аппаратного стека
адреса возврата и передачу управления по этому адресу.
Пара команд - PUSH и POP - обеспечивает использование аппаратного стека для
программного решения других задач.
22

23.

Очереди
Очередь (queue) — структура данных типа «список», позволяющая
добавлять элементы лишь в конец списка, и извлекать их из его начала.
Очереди похожи на стеки.
Они также не дают доступа к произвольному элементу.
Дисциплина обслуживания FIFO (first-in/first-out) или FCFS - (firstcome/first-served).
23

24.

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

25.

Очередь может быть реализована двумя способами: на основе массивов и
списками при помощи указателей.
Начало очереди определяется первым элементом в очереди (front). Конец
очереди – это место после его последнего элемента (rear). Эти позиции
используются для вставки и удаления элементов очереди.
Подобно стеку, очередь сохраняет элементы параметризованного типа
DataType. Подобно стеку, абстрактная очередь не ограничивает количество
элементов ввода. Однако, если для реализации списка используется массив
может возникнуть условие полной очереди.
Реализовать очередь на основе массивов можно двумя способами –
линейной очередью и кольцевой очередью.
25

26.

Рассмотрим класс Queue - используется массив для сохранения списка элементов и
определяет переменные, которые поддерживают позиции front и rear.
Так как для реализации списка используется массив, класс содержит метод Qfull для
проверки, заполнен ли массив.
Этот метод будет не нужен, если очередь реализована связанным списком.
Параметризованный тип DataType позволяет очереди управлять различными типами
данных.
Класс Queue содержит список (qlist), максимальный размер которого определяется
константой MaxQSize.
Данное-член count содержит число элементов в очереди. Это значение также
определяет, является ли очередь полной или пустой.
Очередь следует тестировать при помощи метода QEmpty перед удалением элемента и
метода QFull перед вставкой новых данных для проверки, пуста ли очередь или
заполнена.
Если предусловия для QInsert или QDelete нарушаются, программа печатает сообщение
об ошибке и завершается.
26

27.

Спецификация класса Queue
ОБЪЯВЛЕНИЕ
#include <iostream>
…
const int MaxQSize = 50;
class Queue
{
private:
int front, rear, count;
DataType qlist [MaxQSize];
public:
Queue (void);
// максимальный размер списка очереди
// массив и параметры очереди
// конструктор
// операции модификации очереди
void
QInsert(const DataType& item); // item - вставляет в конец очереди
DataType QDelete(void);
// удаляет и возвращает элемент в начале очереди
void
ClearQueue(void);
// операции доступа
DataType QFront(void) const;
// возвращает значение элемента в начале очереди
// методы тестирования очереди
int
QLength(void) const;
int
QEmpty(void) const;
int
QFull(void) const;
};
27

28.

Пусть объявление очереди и реализация содержатся в файле aqueue.h.
ПРИМЕР
typedef int DataType;
#include aqueue.h
….
Queue Q;
Q.QInsert(30);
Q.QInsert(70);
cout << Q.QLength() << endl;
cout << Q.QFront () << endl;
if (!Q.QEmpty( ))
cout << Q.QDelete( );
cout << Q.QFront ( ) << endl;
Q.ClearQueue( );
…
//объявляем очередь
//вставляем 30 в очередь
//вставляем 70 в очередь
//печатает 2
//печатает 30
//печатает значение 30
//печатает 70
//очистка очереди.
28

29.

Схема организации линейной очереди на основе массива
Простейшая линейная очередь на основе одномерного массива.
При исключении элемента из очереди все оставшиеся элементы данных должны
смещаться вперед на одну позицию.
Начало очереди определяется первым клиентом в очереди. Конец очереди — это
место непосредственно за последним элементом очереди. Когда очередь полна,
клиенты должны идти к другой расчетной очереди.
Предположим, очередь ограничивается четырьмя клиентами.
29

30.

Вид 4: клиенты D, Е и F встают в очередь, заполняя ее, а клиент G
должен встать в другую очередь.
Данная модель не является эффективной.
Например, очередь содержит 1000 элементов.
Если один элемент удаляется из начала, тогда 999 элементов должны
сместиться влево.
Реализация очереди, где вводится круговая модель - вместо сдвига
элементов
влево,
когда
один
элемент
удаляется,
элементы
очереди
организованы логически в окружность.
30

31.

Кольцевая очередь является более эффективной.
Элементы кольцевой очереди организованы логически в окружность.
Переменная front всегда является местоположением первого элемента в очереди,
и она продвигается по кругу(«по часовой стрелке») по мере выполнения
удалений.
Переменная rear является местоположением, где происходит следующая вставка.
После вставки rear перемещается по кругу («по часовой стрелке») .
Переменная count поддерживает запись количества элементов в очереди, и если
счетчик count равен значению MaxQSize, очередь заполнена.
rear
front
rear
A
C
B
C
B
front
Удалить А
31

32.

Круговая модель очереди
Реализуем круговое движение, используя операцию остатка от деления:
Перемещение конца очереди вперед:
rear = (rear+1)%MaxQSize;
Перемещение начала вперед:
front = (front+1)%MaxQSize;
32

33.

Используем целый массив qlist (размер = 4) из четырех элементов для реализации
круговой очереди.
Первоначально count = 0, и индексы front и rear имеют значение 0.
Последовательность вставок и удалений круговой очереди
33

34.

Конструктор Queue
Конструктор инициализирует элементы данных front rear и count нулевыми
значениями.
Это задает пустую очередь.
Queue::Queue (void) : front(0), rear(0), count(0) { }
Операции класса Queue
Для работы с очередью предоставляется ограниченный набор операций, которые
добавляют новый (метод QInsert) или удаляют (метод Qdelete) элемент.
Класс имеет также метод QFront, который позволяет делать выборку первого
элемента очереди.
34

35.

Перед началом процесса вставки индекс rear указывает на следующую позицию в
списке.
Новый элемент помещается в это место, и переменная count увеличивается на 1.
qlist[rear] = item;
count++;
После помещения элемента в список индекс rear должен быть обновлен для
указания на следующую позицию [Рис. (А)].
Так как мы используем круговую модель, вставка может появиться в конце массива
(qlist[size-l]) с перемещением rear к началу списка [рис. (В)].
Вычисление выполняется с помощью оператора остатка (%).
rear = (rear+1) % MaxQSize;
35

36.

Qinsert
// вставить item в круговую очередь
void Queue::QInsert (const DataType& item)
{ if (count = = MaxQSize) // закончить программу, если очередь заполнена
{ cerr << "Переполнение очереди!" << endl;
exit(l);
}
count++;
qlist[rear] = item;
rear = (rear+1) % MaxQSize;
}
36

37.

Операция QDelete удаляет элемент из начала очереди, позиции, на которую
ссылается индекс front.
Процесс удаления начинается с копирования значения во временную
переменную и уменьшения счетчика очереди.
item = qlist[front];
count --;
В круговой модели необходимо перенести front в позицию следующего
элемента в списке, используя оператор остатка от деления (%) (рисунок
далее).
front = (front + 1) % MaxQSize;
Значение из временной позиции становится возвращаемым значением.
37

38.

Qdelete // удалить элемент из начала очереди и возвратить его значение
DataType Queue::QDelete(void)
{
DataType temp;
if (count = = MaxQSize) // если очередь пуста, закончить программу)
{cerr << "Удаление из пустой очереди!" << endl; exit(l); }
temp = qlist[front];
// уменьшить count на единицу продвинуть начало очереди
//и возвратить значение из начала
count--;
front = (front+1) % MaxQSize;
return temp;
}
38

39.

Реализация очереди с помощью указателей
front
val1
rear
next
val2
next
...
valN-1
next
valN
next
NULL
struct SQueue { int dann;
SQueue *next;
};
SQueue * front=NULL, * rear=NULL;
int k=0;
// количество элементов очереди
39

40.

Очереди приоритетов
(Ранее дано определение, что очередь — это структура данных, которая обеспечивает
FIFO-порядок элементов. Очередь удаляет самый «старый» элемент списка.)
Очередь приоритетов – это модифицированная версия очереди, в которой из списка
удаляется элемент с высшим приоритетом.
Элементы в очереди приоритетов рассматриваются как пара «ключ-значение» (key-value
pair), в которой ключ определяет уровень приоритета. Приоритет оценивается по
некоторому внешнему критерию.
Очереди приоритетов находят применение в операционной системе, которая записывает
процессы в список и затем выполняет их в порядке приоритета.
Например, большинство операционных систем присваивают более низкий, чем другим
процессам, приоритет выполнению печати.
Приоритет 0 часто определяется как высший приоритет, а менее приоритетные имеют
большее значение.
40

41.

Структура, называемая очередью приоритетов (priority queue), имеет опeрации
PQInsert и PQDelete:
• PQInsert просто вставляет элемент данных в список;
• PQDelete удаляет из списка наиболее важный элемент (с высшим приоритетом),
оцениваемый по некоторому внешнему критерию, который различает элементы в
списке.
Порядок хранения
Элемент № 1
20
Элемент № 2
0
Элемент № 3
40
Элемент № 4
30
Элемент № 5
20
Порядок выполнения
Элемент № 2
0
Элемент № 1
20
Элемент № 5
20
Элемент № 4
30
Элемент № 3
40
При удалении элемента из очереди приоритетов в списке может быть несколько
элементов с одним и тем же уровнем приоритета.
Можно потребовать, чтобы эти элементы рассматривались как очередь, т.е.
элементы с одним и тем же приоритетом обслуживались бы в порядке их
поступления.
В ADT не делается никаких допущений по поводу порядка элементов с одним и
тем же уровнем приоритета.
41

42.

Очередь приоритетов можно представить в виде нескольких очередей, где каждая
очередь используется для своего приоритета.
Приоритет 1
R1
R2
...
Rn
O2
...
On
B2
...
Bn
Приоритет 2
O1
Приоритет 3
B1
42

43.

ADT - очередь приоритетов описывается как список с операциями для
добавления или удаления элементов из списка.
Имеется серия операций, которая определяет длину списка и указывает, пуст ли
список.
Существуют различные реализации очереди приоритетов.
Для очереди приоритетов рассмотрим Класс Pqueue.
Используется параметр count и методы доступа к списку для вставки и
удаления элементов.
Элементы, сохраняемые в массиве, имеют параметризованный тип DataType
(чаще используются упорядоченные списки и динамические области для
сохранения элементов в очереди приоритетов).
43

44.

Спецификация класса PQueue
ОБЪЯВЛЕНИЕ
#include <iostream>
…
const int MaxPQSize = 50;
class PQueue
{ int count;
// массив очереди приоритетов и счетчик
DataType pqlist [ MaxPQSize ];
public:
PQueue (void);
// конструктор
// операции, модифицирующие очередь приоритетов
void
PQInsert(const DataType& item);
DataType
PQDelete(void);
void
ClearPQ(void);
int
int
int
// тестирующие методы
PQEmpty(void) const;
PQFull(void) const;
PQLength(void) const;
};
44

45.

Метод PQDelete удаляет элемент с высшим приоритетом из списка.
Полагаем, что элемент с высшим приоритетом — это элемент с
наименьшим значением.
Наименьшее значение определяется с использованием оператора
сравнения "<", который должен быть определен для DataType.
Пример
typedef int DataType;
…
PQueue PQ;
PQ.PQInsert(20);
PQ.PQInsert(10) ;
cout << PQ.PQLength( ) << endl;
N= PQ.PQDelete();
…
// печать 2
// извлечь N = 10
45

46.

PQInsert
// вставить элемент в очередь приоритетов
void PQueue::PQInsert (const DataType& item)
{ //если уже вcе элементы массива pqlist
//использованы, завершить программу
if (count == MaxPQSize)
{ cerr << "Переполнение очереди приоритетов!" << endl;
exit(1);
}
// поместить элемент в конец списка и увеличить
//count на единицу
pqlist[count] = item;
count++;
}
46

47.

PQDelete// удаляет элемент из очереди приоритетов и возвращает его значение
DataType PQueue::PQDelete(void)
{ DataType min;
int i, minindex = 0;
if (count > 0)
{
// найти минимальное значение и его индекс в массиве pqlist
min = pqlist[0];
// просмотреть остальные элементы изменяя минимум и его
индекс
for (i = 1; i < count; i++)
if (pqlist[i] < min)
{// новый минимум в элементе pqlist[i]. новый индекс - i
min = pqlist[i];
minindex = i;
}
pqlist[minindex] = pqlist[count-1];
count--;
}
else
//массив qlist пуст, завершить программу
{ cerr << "Удаление из пустой очереди приоритетов!" << endl; exit(1);}
return min;
}
47

48.

Операция PQInsert имеет время вычисления (порядок) О(1), так как она
непосредственно добавляет элемент в конец списка.
С другой стороны, операция PQDelete требует начального просмотра списка для
определения минимального значения и его индекса.
Эта операция имеет время вычисления О(п), где n— это текущая длина очереди
приоритетов.
Данное-член count содержит количество элементов в списке.
Это значение используется в реализации методов PQLength, PQEmpty и PQFull.
48

49.

Деки
Дек (от англ. deq - double ended queue, очередь с двумя концами) - это такой
последовательный список, в котором как включение, так и исключение
элементов может осуществляться с любого из двух концов списка.
Частный случай дека - дек с ограниченным входом и дек с ограниченным
выходом.
Логическая и физическая структуры дека аналогичны логической и физической
структуре кольцевой FIFO-очереди.
Однако, применительно к деку целесообразно говорить не о начале и конце, а о
левом и правом конце.
Операции над деком:
включение элемента справа;
включение элемента слева;
исключение элемента справа;
исключение элемента слева;
определение размера;
очистка.
Дек проще всего реализовать с помощью двусвязного списка. Он позволяет
просматривать, удалять и добавлять элементы в начало и в конец списка.
49

50.

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

51.

Вся организация дека выполняется программистом без каких-либо специальных
средств системной поддержки.
Однако, в качестве примера такой системной поддержки можно привести
организацию буфера ввода в языке REXX (REstructured eXtended eXecutor,
произносится «рекс», интерпретируемый язык программирования,
разработанный фирмой IBM).
В обычном режиме буфер ввода связан с клавиатурой и работает как FIFOочередь.
Однако, в REXX имеется возможность назначить в качестве буфера ввода
программный буфер и направить в него вывод программ и системных утилит.
В распоряжении программиста имеются операции QUEUE - запись строки в
конец буфера и PULL - выборка строки из начала буфера.
Дополнительная операция PUSH - запись строки в начало буфера - превращает
буфер в дек с ограниченным выходом.
Такая структура буфера ввода позволяет программировать на REXX весьма
гибкую конвейерную обработку с направлением выхода одной программы на
вход другой и модификацией перенаправляемого потока.
51

52.

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

53.

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

54.

54

55.

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

56.

Каждая подзадача работает со своим подмножеством как с линейным списком,
используя для этого определенное поле связок.
Специфика мультисписка проявляется только в операции исключения элемента из
списка.
Исключение элемента из какого-либо одного списка еще не означает необходимости
удаления элемента из памяти, так как элемент может оставаться в составе других списков.
Память должна освобождаться только в том случае, когда элемент уже не входит ни в
один из частных списков мультисписка.
Обычно задача удаления упрощается тем, что один из частных списков является
главным: в него обязательно входят все имеющиеся элементы.
Тогда исключение элемента из любого неглавного списка состоит только в
переопределении указателей, но не в освобождении памяти.
Исключение же из главного списка требует не только освобождения памяти, но и
переопределения указателей как в главном списке, так и во всех неглавных списках, в которые
удаляемый элемент входил.
56

57.

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

58.

Часто в виде мультисписков представляют матрицы очень большой
размерности, в которых большинство элементов равны 0 (такие матрицы
называются разреженными).
Мультисписки обеспечивают эффективное хранение таких структур в
памяти: хранятся только те элементы, которые отличны от 0.
Каждый элемент входит в два списка: в список-строку и список-столбец.
Вся матрица представлена m + n списками, где m и n — соответственно
число строк и число столбцов матрицы, каждый элемент хранит значение
элемента матрицы и две ссылки: на следующий элемент в строке и на
следующий элемент в столбце, указатели на начала этих списков хранятся в
двух массивах.
Описание типа данных одного элемента матрицы-мультисписка
аналогично описанию элемента-очереди или узла дерева.
Для описания матрицы потребуется два массива — массив указателей на
первые элементы списков—строк и на первые элементы списков-столбцов.
58

59.

59

60.

Нелинейные разветвленные списки
Нелинейным разветвленным списком является список, элементами которого могут
быть тоже списки.
(a,(b,c,d),e,(f,g))
()
((a))
Схематическое представление разветвленного списка
60

61.

Схема списка, представляющего алгебраическое выражение
Выражение: (a+b)*(c-(d/e))+f
будет вычисляться в следующем порядке:
a+b
d/e
c-(d/e)
(a+b)*(c-d/e)
(a+b)*(c-d/e)+f
61