Стек. Очередь. Куча.

Стек

Стеком называется структура данных, в которой данные, записанные в первую очередь, извлекаются в последнюю очередь, или по другому, когда последний добавленный элемент извлекается в первую очередь (LIFO, last-in, first-out). В питоне можно использовать список для представления стека. Тогда для извлечения элемента с вершины стека нужно использовать метод pop(), для добавления в стек метод append(). Для определение количества элементов в стеке можно использовать функцию len(). Пример:

stack = [1, 2, 3, 4, 5]		# создали стек из пети элементов
stack.append(6)				# поместили в стек элемент
stack.append(7)				# поместили в стек элемент
x = stack.pop()				# x = 7 извлекли элемент из стека
print (len(stack))				# 6 кол-во элементов в стеке выводим 

Очередь

Очередь - структура данных, в которой элементы извлекаются в том же порядке, в котором они добавлялись, т.е. по принципу первый добавленный элемент извлекается первым (FIFO, first-in, first-out). В питоне списки можно использовать для представления очереди. Для извлечения элемента нужно использовать метод pop(0) с индексом 0. Для добавления элемента используем метод append(). Для определения количества элементов в очереди функцию len(). Пример:

queue = [1, 2, 3, 4, 5]  		# создали очередь из пети элементов
queue.append(6)				# поместили в очередь элемент
queue.append(7)				# поместили в очередь элемент
x = queue.pop(0)				# извлекли элемент из очереди
print (x)						# 1
print (len(queue))				# 6 кол-во элементов в очереди выводим

Куча

Python имеет модуль heapq, который реализует очереди с приоритетами с помощью бинарной кучи.

Алгоритмы на графах

Определения
Базовые понятия

Представление матрицы в виде графа

Дана матрица MxN ходить можно по диагонали и по вертикали. Для решения различного рода задач представим матрицу в виде графа. Итак, количество вершин будет MxN, количество ребер