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

1.

ФГБОУ ВО РГУПС
Алгоритмизация и
программирование
Динамические структуры данных.
Стеки, очереди и деки
Лекция 10
© Составление,
О.В. Игнатьева
Ростов-на-Дону
2020

2.

План лекции
Стеки
Очереди
Деки
2

3.

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

4.

Стеки

5.

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

6.

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

7.

Стек
В современных компьютерах стек используется
для:
размещения локальных переменных;
размещения параметров процедуры или
функции;
сохранения адреса возврата (по какому адресу
надо вернуться из процедуры);
временного хранения данных, особенно при
программировании на Ассемблере.
7

8.

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

9.

Стек
Стек можно реализовать на основе двухсвязного списка
Голова
списка
Узел1
Узел2
Ссылка на
предыдущий узел
Узел3
Хвост
списка
Ссылка на
следующий узел
Стек - это двухсвязный список, в котором разрешены
только операции добавления нового элемента в голову
списка и удаление элемента с головы списка, согласно
принципу LIFO.
9

10.

Стек
Для работы со стеком надо определить, как выполняются
две операции – добавление элемента на вершину стека
(Push) и снятие элемента с вершины стека (Pop). При этом
количество элементов стека ограничивается только доступным объемом памяти.
Голова
списка
Узел1
Узел2
Ссылка на
предыдущий узел
Узел3
Хвост
списка
Ссылка на
следующий узел
10

11.

Стек
В программе надо объявить два новых типа
данных – узел списка Node и указатель на него
PNode.
Синтаксис объявления стека в С++:
Чтобы не работать с отдельными
struct Node
указателями на хвост и голову
{
списка, объявим структуру, в
Тип1 поле1;
которой будет храниться вся
Тип2 поле2;
информация о стеке:
…..
Node *next;
Node *prev;
};
typedef Node * PNode;
struct Stack
{
PNode Head, Tail;
};
11

12.

Стек
Пример. Объявление стека словаря:
struct Node
{
string word;
Node *next;
Node *prev;
};
typedef Node *PNode;
struct Stack
{
PNode Head, Tail;
};
Stack S;
S.Head = NULL;
S.Tail = NULL;
Например, опишем стек для представления
словаря русских слов.
Область данных
ссылка на следующий узел
ссылка на предыдущий узел
тип данных - указатель на узел
Объявление структуры, где будет
храниться вся информация о стеке
Объявление стековой переменной
Указатель на начало списка. В начале
работы указатель Head равен NULL
Указатель на конец списка. В начале
работы указатель Tail равен NULL

13.

Стеки. Операции
Операции над стеком:
Добавление нового узла в список – операция Push
Извлечение (удаление) узла из списка – операция Pop
Pop
Push

14.

Создание нового узла
Для стека мы не будем отдельно создавать функцию для создания
нового узла, которая включала только выделение памяти под
новый узел и запоминание адреса выделенного блока, так как у
нас нет возможности вставлять узел в произвольное место списка.
В стеке новый узел можно вставить только в начало списка, поэтому
объединим вместе две операции CreateNode и AddFirst.
Также немного переделаем листинг кода, чтобы работать не с
отдельными указателями, а со структурой типа Stack.
Создание нового узла
PNode NewNode = new Node;
NewNode->word = NewWord;
NewNode->next = NULL;
NewNode->prev = NULL;
14

15.

Добавление узла на вершину стека
При добавлении нового узла NewNode на вершину стека надо:
2) установить ссылку next
узла NewNode на голову
существующего списка и его
ссылку prev в NULL;
NewNode->next = Head;
NewNode->prev= NULL;
1) создать новый узел
Null
3) установить ссылку prev
бывшего первого узла (если он
существовал) на NewNode;
if ( Head!=NULL )
Head->prev = NewNode;
5) если в списке не было ни одного
элемента, хвост списка также
устанавливается на новый узел.
4) установить голову списка на новый узел;
Head = NewNode;
if ( Tail == NULL ) Tail = Head;

16.

Добавление узла на вершину стека
// функция добавления нового узла в стек
void Push ( Stack &S, string data )
{
PNode NewNode;
NewNode = new Node;
NewNode->word = data;
NewNode->next = S.Head;
NewNode->prev = NULL;
if ( S.Head !=NULL)
S.Head->prev = NewNode;
S.Head = NewNode;
if ( S.Tail ==NULL)
S.Tail = S.Head;
}
Важно, что адрес стека
передаётся по ссылке
Алгоритм создания нового
узла
Алгоритм добавления нового
узла в начало двухсвязного
списка
16

17.

Снятие (удаление узла) с
вершины стека
Функция Pop удаляет верхний элемент и возвращает его
данные.
Эта операция идентична операции
Pop
удаления узла из двухсвязного списка,
но только при условии что он является
первым.
Адрес OldNode нам передавать не
нужно, так как мы знаем, что он первый

18.

Снятие (удаление узла) с
вершины стека
1) Узнаем адрес первого узла
PNode TopNode = S.Head;
2) Если список пустой, то выведем
сообщение и выходим из функции
if ( TopNode==NULL )
return “Список пустой”;
3) Сохраняем данные об узле
data = TopNode->word;
4) Рассмотрим только один случай
если удаляемый элемент
является первым!!
S.Head = TopNode->next;
5) Проверяем , это был единственный
элемент или нет. Если голова не пустая,
то устанавливаем предыдущую ссылку
головы, а иначе все пусто!
if ( S.Head != NULL )
S.Head->prev = NULL;
else S.Tail = NULL;
}
6) Освобождаем память, которую
занимал узел.
delete TopNode;
7) Выводим данные о узле
return data;

19.

Снятие узла с вершины стека
string Pop ( Stack &S )
{
PNode TopNode = S.Head;
string data;
if ( TopNode==NULL )
return “Список пустой”;
data = TopNode->word;
S.Head = TopNode->next;
if ( S.Head != NULL )
S.Head->prev = NULL;
else
S.Tail = NULL;
delete TopNode;
return data;
}
// удаляем первый элемент
// встали на начало списка
// если список пустой, то
выведем сообщение и
выходим из функции
// иначе сохранили данные
// Алгоритм удаления узла из списка, а
именно удаляем единственный элемент
// изменяем ссылки головы
// удаляем последний элемент
// освобождаем память
// возвращение данных, чтобы вывести
информацию о узле, который удалили
19

20.

Вывод всех элементов стека
// Обход списка с головы списка
void Print ( Stack &S )
{
PNode TopNode = S.Head;
// начинаем с вершины стека
// пока не дошли до конца
while (TopNode != NULL)
{
cout<<TopNode->word<<endl;
// выводим данные узла
TopNode=TopNode->next;
// переходим к следующему
узлу
}
}
20

21.

Поиск узла в списке
Часто требуется найти в списке нужный элемент (его адрес или данные).
Надо учесть, что требуемого элемента может и не быть, тогда просмотр
заканчивается при достижении конца списка.
Такой подход приводит к следующему алгоритму:
1) начать с головы списка;
PNode q = S.Head;
2) пока текущий элемент существует
(указатель – не NULL), проверить
нужное условие и перейти к
следующему элементу;
3) закончить, когда найден
требуемый элемент или все элементы
while (q->word != NewWord && q!=NULL)
списка
q = q->next;
просмотрены.
return q;
Поиск по данным
21

22.

Поиск узла в списке
Например, следующая функция ищет в списке элемент,
соответствующий заданному слову (для которого поле word
совпадает с заданной строкой NewWord), и возвращает его адрес
или NULL, если такого узла нет.
// функция поиска узла в списке
PNode Find (Stack S, string NewWord)
//пока текущий элемент существует
{ //начать с головы списка
(указатель – не NULL), проверить
PNode q = S.Head;
нужное условие и перейти к
следующему элементу
while (q->word != NewWord && q != NULL)
q = q->next;
return q;
}
закончить, когда найден
требуемый элемент или все
элементы списка
просмотрены
22

23.

Очередь

24.

Очередь
Очередь - список, операции
чтения и добавления
элементов в котором
подвержены правилу «Первый
пришел, первый вышел»
(FIFO — first in, first out) .
При этом, при чтении элемента,
он удаляется из очереди. Таким
образом, для чтения в очереди
доступна только голова, в то
время как добавление
проводится только в хвост.
24

25.

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

26.

Очередь
Очередь называют структурой типа FIFO (First In
– First Out) – первым пришел, первым ушел.
Хорошо знакомой моделью является очередь в
магазине. На рисунке изображена очередь из 3-х
элементов.
26

27.

Очередь
Наиболее известные примеры применения очередей в
программировании – очередь событий системы Windows
и ей подобных.
Очереди используются также для моделирования в
задачах массового обслуживания (например,
обслуживания клиентов в банке).
27

28.

Очередь
Очередь можно реализовать на основе двухсвязного списка
Голова
списка
Узел1
Узел2
Ссылка на
предыдущий узел
Узел3
Хвост
списка
Ссылка на
следующий узел
Очередь - это двухсвязный список, в котором разрешены
только операции добавления нового элемента в хвост
списка и удаление элемента с головы списка, согласно
28
принципу FIFO.

29.

Очередь
Для работы с очередью надо определить, как выполняются
две операции – добавление элемента в конец очереди
(Push) и снятие (удаление) элемента с головы списка (Pop).
Голова
списка
Узел1
Узел2
Ссылка на
предыдущий узел
Узел3
Хвост
списка
Ссылка на
следующий узел
29

30.

Очередь
В программе надо объявить два новых типа
данных – узел списка Node и указатель на него
PNode.
Синтаксис объявления очереди в С++:
Чтобы не работать с отдельными
struct Node
указателями на хвост и голову
{
списка, объявим структуру, в
Тип1 поле1;
которой будет храниться вся
Тип2 поле2;
информация о очереди:
…..
Node *next;
Node *prev;
};
typedef Node * PNode;
struct Queue
{
PNode Head, Tail;
};
30

31.

Очередь
Пример. Объявление очереди словаря:
struct Node
{
string word;
Node *next;
Node *prev;
};
typedef Node *PNode;
struct Queue
{
PNode Head, Tail;
};
Queue Q;
Q.Head = NULL;
Q.Tail = NULL;
Например, опишем очередь для
представления словаря русских слов.
Область данных
ссылка на следующий узел
ссылка на предыдущий узел
тип данных - указатель на узел
Объявление структуры, где будет
храниться вся информация о очеред
Объявление переменной очереди
Указатель на начало списка. В начале
работы указатель Head равен NULL
Указатель на конец списка. В начале
работы указатель Tail равен NULL

32.

Очередь. Операции
Операции над очередью:
Добавление нового узла в конец очереди – операция Push
Извлечение (удаление) узла с начала очереди – операция
Pop
Pop
Push

33.

Добавление узла в очередь
Фактически это добавление нового элемента в конец двусвязного
списка. Объединим две операции создание нового узла и добавление в
конец списка.
Null
1) Создать новый узел
3) установить ссылку next
бывшего конечного узла (если
он существовал) на NewNode;
if ( Tail!=NULL )
Tail->next = NewNode;
4) установить хвост списка на новый узел;
Tail = NewNode;
2) установить ссылку prev
узла NewNode на хвост
существующего списка и его
ссылку next в NULL;
NewNode->prev = Tail;
NewNode->next = NULL;
5) если в списке не было ни одного
элемента, голову списка также
устанавливается на новый узел.
if ( Head == NULL )
Head = Tail;

34.

Добавление узла в конец очереди
// функция добавления нового узла в очередь
void Push (Queue &Q, string data )
{
PNode NewNode;
NewNode = new Node;
NewNode->word = data;
NewNode->prev = Q.Tail;
NewNode->next = NULL;
Важно, что адрес очереди
передаётся по ссылке
Алгоритм создания нового
узла
Алгоритм добавления нового
узла в конец двухсвязного
списка
if ( Q.Tail != NULL )
Q.Tail->next = NewNode;
Q.Tail = NewNode;
if (Q.Head == NULL) Q.Head = Q.Tail;
}
34

35.

Снятие (удаление узла) с начала
очереди
Функция Pop удаляет верхний элемент и возвращает его
данные.
Более того, функция для получения
первого элемента очереди (Pop)
совпадает с функцией снятия
элемента с вершины стека.
Pop

36.

Снятие (удаление узла) с начала
очереди
1) Узнаем адрес первого узла
PNode TopNode = Q.Head;
2) Если список пустой, то выведем
сообщение и выходим из функции
if ( TopNode==NULL )
return “Список пустой”;
3) Сохраняем данные об узле
data = TopNode->word;
4) Рассмотрим только один случай
если удаляемый элемент
является первым!!
Q.Head = TopNode->next;
5) Проверяем , это был единственный
элемент или нет. Если голова не пустая,
то устанавливаем предыдущую ссылку
головы, а иначе все пусто!
if ( Q.Head != NULL )
Q.Head->prev = NULL;
else Q.Tail = NULL;
}
6) Освобождаем память, которую
занимал узел.
delete TopNode;
7) Выводим данные о узле
return data;

37.

Снятие узла с головы очереди
string Pop (Queue &Q )
{
PNode TopNode = Q.Head;
string data;
if ( TopNode==NULL )
return “Список пустой”;
data = TopNode->word;
Q.Head = TopNode->next;
if ( Q.Head != NULL )
Q.Head->prev = NULL;
else
Q.Tail = NULL;
delete TopNode;
return data;
}
// удаляем первый элемент
// встали на начало списка
// если список пустой, то
выведем сообщение и
выходим из функции
// иначе сохранили данные
// Алгоритм удаления узла из списка, а
именно удаляем единственный элемент
// изменяем ссылки головы
// удаляем последний элемент
// освобождаем память
// возвращение данных, чтобы вывести
информацию о узле, который удалили
37

38.

Вывод всех элементов очереди
// Обход списка с головы списка
void Print (Queue &Q )
{
PNode TopNode = Q.Head;
// начинаем с вершины очереди
// пока не дошли до конца
while (TopNode != NULL)
{
cout<<TopNode->word<<endl;
// выводим данные узла
TopNode=TopNode->next;
// переходим к следующему
узлу
}
}
38

39.

Дек

40.

Дек
Дек (deque) - это упорядоченный набор
элементов, в котором добавление новых и
удаление существующих элементов
допустимо с любого конца.
40

41.

Дек
Дек может быть реализован на основе двусвязного
списка. Для дека разрешены четыре операции:
1) добавление элемента в начало;
2) добавление элемента в конец;
3) удаление элемента с начала;
4) удаление элемента с конца.
Их можно реализовать, используя написанные
выше функции для стека и очереди.
41

42.

Спасибо за внимание!

43.

Литературные источники
1) К. Поляков. Программирование на языке С++.
2). Харви Дейтел, Пол Дейтел. Как программировать на
С++. - М: Вильямс, - 1011 с.
3). Струструп Б. Программирование: принципы и
практика использования С++. – М. : Вильямс, 2011. –
1248 с.
4). Струструп Б. Язык программирования С++. – М.:
Бином. - 1054 с.
5). Лафоре Р. Объектно-ориентированное
программирование в С++. Питер, 2004. – 922 с.
6). Шилдт Г. С++: руководство для начинающих, 2-е
издание. – М: Вильямс, 2005. -672 с.