06 Линейные списки, стеки, очереди

1. Алгоритмы и структуры данных

Списки, стеки, очереди
1

2. Контейнеры

В нашем курсе мы будем знакомиться со специальными
структурами данных – контейнерами различных типов.
Контейнер – это объект, который хранит некоторое
множество
объектов
другого
типа.
Контейнеры
различаются по способу организации и хранения данных.
Соответственно, методы доступа и операции над
данными также будут различаться.
Простыми, но часто используемыми контейнерами
являются массив, список (list), стек (stack), очередь
(queue).
2

3. Список

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

4. Список

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

5. Структура однонаправленного списка

pbeg – указатель на начальный элемент,
pend – указатель на конечный элемент
Доступ к элементам осуществляется последовательно.
Если включить в состав элементов еще одно поле –
указатель на предыдущий элемент (нуль для начального
элемента списка), то список станет двунаправленным.
5

6. Элемент списка

Для представления элемента списка нужно создать
соответствующий тип, т.е. описать структуру (класс).
Во многих случаях информационная часть элемента
включает всего одно значение. Пусть, например, нужно
построить некоторый список по заданному набору строк.
Чтобы не дублировать строки, достаточно хранить в
качестве информационной части указатели с их
адресами. Тогда тип элемента (назовем его ListElem)
может быть следующим:
struct ListElem
{
char *str;
ListElem *next;
}
6

7. Информационная часть элементов

Пусть нам нужно построить список объектов сложной
структуры, например, полилиний (ломаных, заданных
набором узловых точек), представленных следующим
классом:
class PLine
{
double *x, *y;
int length;
char type;
int color;
public:
...
};
7

8. Элемент списка полилиний

Если полилинии должны существовать только в списке, то
элементы списка могут включать сами объекты-полилинии:
struct ListElem
{
PLine line;
ListElem *next;
};
а в противном случае – указатели с адресами объектов:
struct ListElem
{
PLine *pline;
ListElem *next;
};
8

9. Элемент списка целых

Далее
мы
будем
использовать
список
неотрицательных чисел с типом элементов:
struct IListElem
{
int value;
IListElem *next;
целых
IListElem(int val)
{ value = val; next = NULL; }
};
В описание включен специальный метод – конструктор,
который вызывается автоматически при создании
любого объекта типа IListElem и инициализирует его
поля. Имя конструктора совпадает с именем типа.
9

10. Класс для списка целых

Определим класс IList, представляющий атрибуты
(поля) списка и некоторые методы для работы с ним:
class IList
{
private:
IListElem *pbeg, *pend;
public:
IList() { pbeg = pend = NULL; }
void push_back(int val);
void push_front(int val);
int pop_front();
void join(IList& lst);
};
10

11. Реализация методов

Метод push_back добавляет новый элемент со значением
val в конец текущего списка (который может быть и
пустым).
void IList::push_back(int val)
{
IListElem *pnew = new IListElem(val);
if (!pbeg) pbeg = pend = pnew;
else
{ pend->next = pnew; pend = pnew; }
}
11

12. Реализация методов

Метод push_front добавляет новый элемент со
значением val в начало текущего списка (который
может быть и пустым).
void IList::push_front(int val)
{
IListElem *pnew = new IListElem(val);
pnew->next = pbeg;
if (!pbeg) pbeg = pend = pnew;
else pbeg = pnew;
}
12

13. Реализация методов

Метод pop_front возвращает информационную часть
(целое число) начального элемента текущего списка и
удаляет этот элемент из списка (или возвращает -1, если
список был пустой).
int IList::pop_front()
{
if (!pbeg) return -1;
IListElem *ptr = pbeg; // запоминаем адрес
int val = pbeg->value; // запоминаем значение
pbeg = pbeg->next;
if (!pbeg) pend = NULL;
delete ptr; return val;
13
}

14. Реализация методов

Метод join объединяет 2 списка, присоединяя список
lst
к концу текущего списка. Элементы lst не
копируются и не дублируются, lst
в результате
освобождается (становится пустым). Метод работает и в
случае, когда lst и/или текущий список пустой.
void IList::join(IList& lst)
{
if (!lst.pbeg) return;
if (!pbeg) pbeg = lst.pbeg;
else pend->next = lst.pbeg;
pend = lst.pend;
lst.pbeg = lst.pend = NULL;
}
14

15. Использование методов

void main()
{
IList a, b;
for (int i = 10; i > 0; i--)
a.push_back(i);
int x = a.pop_front();
a.push_front(0);
b.push_front(20); b.push_back(30);
a.join(b);
}
15

16. Стек

Стек хранит набор объектов одного типа, обеспечивая в
любой момент доступ только к одному из них по правилу
LIFO (last in – first out, последний пришел – первый ушел).
Стек – динамическая структура данных.
Для стека определены 2 операции:
• push – добавить элемент в вершину (в конец) стека
• pop – извлечь последний элемент из стека.
16

17. Пример стека

В простейшем случае стек организуется на основе массива
с текущим указателем индекса последнего элемента без
создания пользовательского типа (struct / class).
Переменные для стека, хранящего целые числа:
int stack[N], curpos;
// массив и позиция вершины
Инициализация стека:
curpos = -1;
Добавление целого числа val в вершину стека:
if (curpos < N-1) stack[++curpos] = val;
Извлечение числа из вершины стека:
val = (curpos < 0)? -1 : stack[curpos--];
17

18. Пример стека

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

19. Разработчик и пользователь

Для устранения недостатков предыдущего подхода
определим новый пользовательский тип IStack с
необходимыми полями и методами обработки. Каждая
переменная данного типа будет отдельным объектомстеком со своими уникальными полями.
Сначала определим, что должны знать о новом типе его
разработчик и пользователь.
19

20. Разработчик и пользователь

Разработчик:
• определяет формат хранения данных
• задает набор полей (переменных)
• реализует все методы
• определяет,
какие
методы
будут
пользователю.
доступны
Пользователь:
• может создавать объекты нового типа
• не должен иметь доступа к полям (лишняя информация
+ возможность неправильного обращения)
• может использовать для работы с данными только
доступные ему методы.
20

21. Класс с динамическим массивом, конструктором с параметром и деструктором

class IStack
{
int *arr, length, curpos;
public:
IStack(int len);
~IStack();
void push(int val);
int pop();
};
Деструктор – специальный метод, который вызывается
автоматически перед уничтожением объекта и выполняет
необходимые завершающие действия.
21

22. Реализация методов класса IStack

IStack::IStack(int len)
{
arr = new int [len];
length = len; curpos = -1;
}
IStack::~IStack() { delete [] arr; }
void IStack::push(int val)
{
if (curpos < length-1)
arr[++curpos] = val;
}
int IStack::pop()
{
if (curpos < 0) return -1;
return arr[curpos--];
}
22

23. Использование стеков

void main()
{
int i;
IStack a(10), *pb;
for (i = 0; i < 10; i++)
a.push(i*2);
pb = new IStack(20);
for (i = 0; i < 20; i++)
pb->push(i+10);
for (i = 0; i < 20; i++)
cout << pb->pop() << endl;
delete pb;
}
23

24. Стек на основе списка

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

25. Стек на основе списка целых чисел

#include “IList.h”
class IStack
{
IList list;
// length и curpos не нужны
public:
// IStack();
// ~IStack();
void push(int val);
int pop();
};
Конструктор и деструктор здесь можно опустить –
транслятор построит эти методы по умолчанию. При
работе конструктора создается пустой список list, при
работе деструктора уничтожается текущий list.
25

26. Реализация методов класса IStack

В списке наиболее просто добавлять и удалять начальный
элемент – его мы и будем считать вершиной стека. Список
будет содержать только актуальные элементы.
#include “IList.h”
void IStack::push(int val)
{
list.push_front(val);
}
int IStack::pop()
{
return list.pop_front();
}
26

27. Изменения в программе

void main()
{
int i;
IStack a, *pb;
for (i = 0; i < 10; i++)
a.push(i*2);
pb = new IStack;
for (i = 0; i < 20; i++)
pb->push(i+10);
for (i = 0; i < 20; i++)
cout << pb->pop() << endl;
delete pb;
}
27

28. Очередь как динамическая структура

Контейнер «очередь» хранит набор объектов одного типа,
обеспечивая в любой момент доступ только к одному из
них по правилу FIFO (first in – first out, первый пришел –
первый ушел). Как и для стека, для очереди определены
2 операции:
• push – добавить элемент в конец очереди
• pop – извлечь начальный элемент очереди.
28

29. Очередь на основе массива

В простейшем случае очередь организуется на основе
массива с двумя указателям (индексами) – на начальный
(first) и конечный (last) элемент. Оба индекса
увеличиваются на 1: last при добавлении элемента, first –
при извлечении.
0
first
last
length-1
Очередь будет пустой, если first = last+1. Это условие нужно
проверять при извлечении элемента.
Начальные значения: first = 0, last = -1.
Добавление элемента возможно, если last < length-1.
29

30. Недостатки использованного подхода

Очередь – это динамическая структура: в разные моменты
времени элементы могут добавляться или извлекаться.
Но если новый элемент всегда добавлять в позицию
last+1, то всего в очередь нельзя поместить более length
элементов, даже если часть элементов уже извлечена.
0
first
last
30

31. Циклическое заполнение массива

Если last = length-1, но начальный элемент массива
свободен, то запишем новый элемент туда. Для этого
нужно вычислять новую позицию last по-другому:
last = (last+1) % length.
Аналогично должен изменяться и индекс first.
last
first
31

32. Очередь на основе списка

Очередь, как и стек, проще организовать на основе списка.
Начальный и конечный элементы очереди – это,
соответственно, начальный и конечный элементы списка.
Очередь пуста, если список пустой.
Описание нового типа IQueue
описание IStack.
будет очень похоже на
32

33. Очередь на основе списка целых чисел

#include “IList.h”
class IQueue
{
IList list;
// first и last не нужны
public:
// IQueue();
// ~IQueue();
void push(int val);
int pop();
};
Конструктор и деструктор здесь можно опустить
транслятор построит эти методы по умолчанию.
–
33

34. Реализация методов класса IQueue

Новый элемент добавляется в конец списка. Начальный
элемент очереди – это начальный элемент списка.
Очередь будет содержать только актуальные элементы.
#include “IList.h”
void IQueue::push(int val)
{
list.push_back(val);
}
int IQueue::pop()
{
return list.pop_front();
}
34

35. Использование очередей

void main()
{
int i;
IQueue a, *pb;
for (i = 0; i < 10; i++)
a.push(i*2);
pb = new IQueue;
for (i = 0; i < 20; i++)
pb->push(i+10);
for (i = 0; i < 20; i++)
cout << pb->pop() << endl;
delete pb;
}
35