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

которых разрешены только операции вставки и удаления первого и/или последнего элемента.

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

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

На рисунке показан стек, содержащий 6 элементов.

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

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

нового элемента в голову списка и удаление элемента с головы списка, согласно принципу LIFO.

Стек можно реализовать на основе двухсвязного списка

Узел1

Узел2

Узел3

Голова
списка

Хвост
списка

добавление элемента на вершину стека (Push) и снятие элемента с вершины стека (Pop). При этом количество элементов стека ограничивается толь-
ко доступным объемом памяти.

Узел1

Узел2

Узел3

Голова
списка

Хвост
списка

Node *prev;
};
typedef Node * PNode;

Синтаксис объявления стека в С++:

Стек

В программе надо объявить два новых типа данных – узел списка Node и указатель на него PNode.

Чтобы не работать с отдельными указателями на хвост и голову списка, объявим структуру, в
которой будет храниться вся информация о стеке:

struct Stack
{
PNode Head, Tail;
};

*PNode;
struct Stack
{
PNode Head, Tail;
};
Stack S;
S.Head = NULL;
S.Tail = NULL;

Пример. Объявление стека словаря:

Стек

Например, опишем стек для представления словаря русских слов.

(удаление) узла из списка – операция Pop

Push

Pop

создания нового узла, которая включала только выделение памяти под новый узел и запоминание адреса выделенного блока, так как у нас нет возможности вставлять узел в произвольное место списка.
В стеке новый узел можно вставить только в начало списка, поэтому объединим вместе две операции CreateNode и AddFirst.
Также немного переделаем листинг кода, чтобы работать не с отдельными указателями, а со структурой типа Stack.

Создание нового узла

PNode NewNode = new Node;
NewNode->word = NewWord;
NewNode->next = NULL;
NewNode->prev = NULL;
return NewNode;

стека надо:

2) установить ссылку next узла NewNode на голову существующего списка и его ссылку prev в NULL;

NewNode->next = Head;
NewNode->prev= NULL;

3) установить ссылку prev бывшего первого узла (если он существовал) на NewNode;

if ( Head!=NULL )
Head->prev = NewNode;

4) установить голову списка на новый узел;

5) если в списке не было ни одного элемента, хвост списка также устанавливается на новый узел.

Head = NewNode;

if ( Tail == NULL ) Tail = Head;

создать новый узел

)
{
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;
}

// функция добавления нового узла в стек

Важно, что адрес стека передаётся по ссылке

Алгоритм создания нового узла

Алгоритм добавления нового узла в начало двухсвязного списка

возвращает его данные.

Pop

Эта операция идентична операции удаления узла из двухсвязного списка, но только при условии что он является первым.
Адрес OldNode нам передавать не нужно, так как мы знаем, что он первый

это был единственный элемент или нет. Если голова не пустая,
то устанавливаем предыдущую ссылку головы, а иначе все пусто!

S.Head = TopNode->next;

6) Освобождаем память, которую занимал узел.

delete TopNode;

Снятие (удаление узла) с вершины стека

if ( S.Head != NULL )
S.Head->prev = NULL;
else S.Tail = NULL;
}

PNode TopNode = S.Head;

Узнаем адрес первого узла

2) Если список пустой, то выведем сообщение и выходим из функции

if ( TopNode==NULL )
return “Список пустой”;

data = TopNode->word;

3) Сохраняем данные об узле

7) Выводим данные о узле

return data;

= 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;
}

// удаляем первый элемент

// изменяем ссылки головы

// освобождаем память

// Алгоритм удаления узла из списка, а
именно удаляем единственный элемент

// удаляем последний элемент

// возвращение данных, чтобы вывести
информацию о узле, который удалили

// если список пустой, то выведем сообщение и выходим из функции

// встали на начало списка

// иначе сохранили данные

= S.Head;
while (TopNode != NULL)
{
cout<word< TopNode=TopNode->next;
}
}

// переходим к следующему узлу

// Обход списка с головы списка

// начинаем с вершины стека

// пока не дошли до конца

// выводим данные узла

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

1) начать с головы списка;

2) пока текущий элемент существует (указатель – не NULL), проверить нужное условие и перейти к следующему элементу;

3) закончить, когда найден
требуемый элемент или все элементы списка
просмотрены.

Поиск по данным

PNode q = S.Head;

while (q->word != NewWord && q!=NULL)
q = q->next;

return q;

= S.Head;
while (q->word != NewWord && q != NULL)
q = q->next;
return q;
}

закончить, когда найден требуемый элемент или все элементы списка просмотрены

// функция поиска узла в списке

//начать с головы списка

//пока текущий элемент существует
(указатель – не NULL), проверить
нужное условие и перейти к
следующему элементу

Например, следующая функция ищет в списке элемент, соответствующий заданному слову (для которого поле word совпадает с заданной строкой NewWord), и возвращает его адрес или NULL, если такого узла нет.

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

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

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

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

нового элемента в хвост списка и удаление элемента с головы списка, согласно принципу FIFO.

Очередь можно реализовать на основе двухсвязного списка

Узел1

Узел2

Узел3

Голова
списка

Хвост
списка

добавление элемента в конец очереди (Push) и снятие (удаление) элемента с головы списка (Pop).

Узел1

Узел2

Узел3

Голова
списка

Хвост
списка

Node *prev;
};
typedef Node * PNode;

Синтаксис объявления очереди в С++:

Очередь

В программе надо объявить два новых типа данных – узел списка Node и указатель на него PNode.

Чтобы не работать с отдельными указателями на хвост и голову списка, объявим структуру, в
которой будет храниться вся информация о очереди:

struct Queue
{
PNode Head, Tail;
};

*PNode;
struct Queue
{
PNode Head, Tail;
};
Queue Q;
Q.Head = NULL;
Q.Tail = NULL;

Пример. Объявление очереди словаря:

Очередь

Например, опишем очередь для представления словаря русских слов.

Push
Извлечение (удаление) узла с начала очереди – операция Pop

Push

Pop

списка. Объединим две операции создание нового узла и добавление в конец списка.

2) установить ссылку prev узла NewNode на хвост существующего списка и его ссылку next в NULL;

NewNode->prev = Tail;
NewNode->next = NULL;

3) установить ссылку next бывшего конечного узла (если он существовал) на NewNode;

if ( Tail!=NULL )
Tail->next = NewNode;

4) установить хвост списка на новый узел;

5) если в списке не было ни одного элемента, голову списка также устанавливается на новый узел.

Tail = NewNode;

if ( Head == NULL )
Head = Tail;

Создать новый узел

{
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;
}

// функция добавления нового узла в очередь

Важно, что адрес очереди передаётся по ссылке

Алгоритм создания нового узла

Алгоритм добавления нового узла в конец двухсвязного списка

возвращает его данные.

Pop

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

это был единственный элемент или нет. Если голова не пустая,
то устанавливаем предыдущую ссылку головы, а иначе все пусто!

Q.Head = TopNode->next;

6) Освобождаем память, которую занимал узел.

delete TopNode;

Снятие (удаление узла) с начала очереди

if ( Q.Head != NULL )
Q.Head->prev = NULL;
else Q.Tail = NULL;
}

PNode TopNode = Q.Head;

Узнаем адрес первого узла

2) Если список пустой, то выведем сообщение и выходим из функции

if ( TopNode==NULL )
return “Список пустой”;

data = TopNode->word;

3) Сохраняем данные об узле

7) Выводим данные о узле

return data;

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;
}

// удаляем первый элемент

// изменяем ссылки головы

// освобождаем память

// Алгоритм удаления узла из списка, а
именно удаляем единственный элемент

// удаляем последний элемент

// возвращение данных, чтобы вывести
информацию о узле, который удалили

// если список пустой, то выведем сообщение и выходим из функции

// встали на начало списка

// иначе сохранили данные

Q.Head;
while (TopNode != NULL)
{
cout<word< TopNode=TopNode->next;
}
}

// переходим к следующему узлу

// Обход списка с головы списка

// начинаем с вершины очереди

// пока не дошли до конца

// выводим данные узла

и удаление существующих элементов допустимо с любого конца.

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