Динамические линейные структуры данных. Стеки и очереди

1.

Динамические линейные
структуры данных
Стеки и очереди

2.

Стек (stack)

3.

Определение
Структура данных, в которой
1. Элементы хранятся в виде
последовательности (линейно)
2. Элементы добавляются в стек и
извлекаются из него только с одного
конца (вершина стека)
3. Работать можно только с самым верхним
элементом стека

4.

Иллюстрация

5.

Иллюстрация

6.

Обозначения

7.

Основные операции

8.

Принцип стека
LIFO (Last In First Out)
Последним вошёл, первым вышел

9.

Возможные ошибки

10.

Реализация стека. Функция push

11.

Переполнение стека

12.

Проверка на переполнение стека
В самом начале функции push:
Если (top == размер_стека - 1), то выходим
из функции
* выход из функции – оператор return

13.

Реализация стека. Функция pop

14.

Извлечение из пустого стека

15.

Проверка на извлечение из пустого
стека
В самом начале функции pop:
Если (top == - 1), то выходим из функции

16.

Стек пуст и стек заполнен
• top == -1 => стек пуст (извлекать нельзя)
• top == N -1 => стек заполнен (добавлять
нельзя)

17.

Функции push и pop

18.

Пример: расстановка скобок

19.

Пример: расстановка скобок

20.

Пример: расстановка скобок

21.

Стек вызовов

22.

Стек вызовов

23.

Очередь (queue)

24.

Определение
Структура данных, в которой
1. Элементы хранятся в виде
последовательности (линейно)
2. Элементы добавляются в конец очереди,
извлекаются с начала
3. Работать можно с первым и последним
элементами очереди

25.

Иллюстрация

26.

Принцип очереди
FIFO (First In First Out)
Первым вошёл, первым вышел

27.

Реализация очереди

28.

Реализация очереди. Функция push

29.

Реализация очереди. Функция pop

30.

Проверки на переполнение очереди
и извлечение из пустой очереди
см. стек (аналогично)

31.

Применение очереди. Очередь
событий

32.

Применение очереди

33.

Реализация стека/очереди
• Одномерный/двумерный массив
• Односвязный/двусвязный список
• Необходимы функции push и pop для
добавления/извлечения элементов