Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
Определение стека
Изначально я хотел сегодня рассказать вам об алгоритме быстрого выбора, но обнаружил, что написал несколько статей, связанных с сортировкой, поэтому временно сменил тему, сегодня я расскажу о структуре данных, а давайте посмотрим на классическая и простая структура данных - стек.
Я думаю, что каждый должен быть знаком со структурой стека, особенно во многих местах он будет соседствовать с кучей, и он более широко известен как «стек». Но на самом деле куча и стек — это по сути две разные структуры данных, и мы не можем их просто спутать. Давайте начнем с более простого стека.
Суть стеков и очередей — это фактически массивы (строго говоря, линейные списки). Просто мы добавили некоторые ограничения на массив, чтобы он удовлетворял определенным условиям, поэтому многие студенты, которые робко относятся к структурам данных, могут расслабиться — в стеке нет особых ухищрений, просто особый вид массива.
По сравнению с другими линейными табличными структурами данных в широком смысле у стека есть только две особенности: одна — «первым пришел — последним вышел», а другая — чтение и запись в него можно производить только с одной стороны массива. Но по сути это одно и то же.Поскольку мы можем читать и записывать элементы только с одной стороны, чем раньше мы входим, тем позже мы выходим.Конечно, это первый вход и последний выход. Это должно быть легко понять из рисунка ниже.
В стеке указано, что мы можем читать и писать только с одной стороны.Обычно мы называем сторону, которая может читать и писать, вершиной стека. Другая сторона, которая не может быть прочитана или записана, называется дном стека. Как видно из рисунка выше, доступ к элементам в нижней части стека возможен только после извлечения элементов из верхней части стека.
Мы используем массивы Python для реализации структуры данных стека.На самом деле для удаления комментариев требуется менее 30 строк.Можно сказать, что это очень просто.Давайте сначала посмотрим на код.
class Stack(object):
def __init__(self, size_limit=None):
self._size_limit = size_limit
self.elements = []
self._size = 0
# 进栈，判断是否越界
def push(self, value):
if self._size_limit is not None and len(self.elements) > self._size_limit:
raise IndexError("Stack is full")
else:
self.elements.append(value)
self._size += 1
# 判断栈是否为空
def is_empty(self):
return self._size == 0
# 栈清空
def clear(self):
self.elements = []
self._size = 0
# 访问元素数量
def size(self):
return self._size
# 查询栈顶元素
def top(self):
return self.elements[-1]
# 弹出栈顶元素
def pop(self):
val = self.elements.pop()
self._size -= 1
return val
По сути, общая реализация стека имеет только перечисленные выше методы, а может быть и меньше. Из-за стека в некоторых языках top и pop объединяются. Означает, что доступ должен быть извлечен, доступ без извлечения не поддерживается. Поэтому логика реализации стека очень проста, и можно даже сказать, что в ней нет технического содержания, что очень подходит для структур данных начального уровня.
Конечно, с другой стороны, можно также сказать, что принцип реализации стека не очень важен, напротив, важнее то, где стек вообще используется.
приложение стека
Наиболее широко используемый стек находится в операционной системе, например, когда программа выполняет вызов метода внутри компилятора, она фактически записывает стек вызываемого в данный момент метода. Например, если в настоящее время вызывается метод A, если метод B вызывается в методе A, компьютер сохранит указатель на метод B в стеке системных методов, если метод B снова вызывает метод C. быть добавлено. Когда выполнение метода C закончится, появится C, компьютер перенесет результат C в B и продолжит выполнение предыдущего B, и так далее, пока стек не станет пустым.
Итак, вопрос в том, что если метод A вызывает сам себя?
Ответ заключается в том, что компьютер создаст новый указатель A и заполнит его стек.Если A продолжит рекурсию, то система создаст новый указатель и поместит его в стек...
Из описанного выше процесса мы можем определить две вещи. Во-первых, рекурсия, когда мы пишем программу, фактически выполняется в виде стека внутри компилятора. Во-вторых, если мы используем бесконечный цикл для непрерывной рекурсии из-за ограничения размера стека, когда глубина стека превышает ограничение, возникает ошибка SystemStackExceed. Другими словами, рекурсия не бесконечна, потому что в дополнение к ограничению оперативной памяти операционной системы компилятор также имеет ограничение на максимальную глубину рекурсии, чтобы предотвратить сбой системы из-за бесконечного цикла рекурсии. Хотя механизм реализации каждого языка не совсем одинаков, одно можно сказать наверняка: глубина рекурсии ограничена, и мы не можем рекурсировать бесконечно.
Вопрос в том, что если наша система имеет крупномасштабную рекурсию? Должен ли я вручную добавлять память на машину?
Это одна из проблем, с которой игроки ACM часто сталкиваются на поле.Что опытные игроки должны сделать в разминочном матче в первый день, так это протестировать максимальную глубину рекурсии компьютера, в дополнение к настройке vim или других IDE. . В C++ поддерживается принудительное открытие предела глубины рекурсии через язык ассемблера, но даже это ограничено, и насколько я знаю, это может сделать только C++.Для других языков, а глубины рекурсии недостаточно, только один способ - вручную построить стек для имитации рекурсии.
Ручная рекурсия
Многим студентам рекурсия может показаться болезненной, но если они попытаются построить стек вручную для имитации рекурсии, они найдут ее еще более болезненной. Мало того, что необходимо добавлять дополнительные переменные для хранения промежуточного состояния, это еще и огромная проблема для программирования.
Давайте посмотрим на пример:
class Node:
def __init__(self, val):
self.val = val
# 左孩子
self.lchild = None
# 右孩子
self.rchild = None
if __name__ == "__main__":
# 建树
root = Node(0)
node1 = Node(1)
root.lchild = node1
node2 = Node(2)
root.rchild = node2
node3 = Node(3)
node1.lchild = node3
node4 = Node(4)
node1.rchild = node4
node5 = Node(5)
node2.rchild = node5
Это простое бинарное дерево, нарисованное так:
0
/ \
1 2
/ \ \
3 4 5
Затем нам нужно пройти по стеку по порядку без рекурсии.Все мы знаем, что неупорядоченный обход состоит в том, чтобы сначала пройти по левому поддереву, затем вывести текущий узел, а затем пройти по правому поддереву. Очень удобно писать рекурсивно, всего несколько строк:
def dfs(node):
if node is None:
return
dfs(node.lchild)
print(node.val)
dfs(node.rchild)
Подумайте об этом, что, если вы не используете рекурсию? Если вы действительно попытаетесь писать, то обнаружите, что, казалось бы, простые проблемы могут стать очень сложными. Легко представить, что мы храним узлы в стеке, но хранение данных — это только видимость. Важный вопрос: когда мы получаем узел из стека, как мы оцениваем, что он должен делать? Должен ли быть пройден левый узел, должен ли быть пройден вывод или должен быть пройден правый узел?
После тщательного анализа и размышлений над этими проблемами мы можем обнаружить, что все они связаны с рекурсивным поиском с возвратом.
В рекурсии, после того как мы прошли поддерево текущего узла, мы вернемся к этому узлу при извлечении стека. Например, в приведенном выше дереве во время рекурсивного процесса мы дважды столкнемся с узлом 1. В первый раз он не выведет 1, а сначала пройдет свое левое поддерево, равное 3, а затем снова вернется к 1. Поскольку его левое поддерево было пройдено, он выведет 1. Этот процесс ухода и возвращения называется возвратом. Если вы думаете о древовидной структуре как о водопаде, процесс немного похож на движение вниз и вверх по течению, что вполне разумно означает возврат.
Вернемся к предыдущему вопросу.Суть всей путаницы происходит от нашей неспособности судить, является ли текущий узел, с которым мы сталкиваемся, первой встречей или воссоединением после долгой разлуки. И речь идет о том, что мы собираемся с этим делать. Изначально в рекурсии, так как программа будет записывать состояние рекурсии и позицию выполняемого кода, а после рекурсивного возврата она вернется на позицию последнего вызова, так что эту проблему можно игнорировать. Теперь, поскольку мы больше не используем рекурсию, нам нужно самим судить о состоянии узла.
Разобрались, на самом деле это очень просто, нам нужно только добавить поле состояния к узлу, чтобы указать, будет ли узел откатываться. Очевидно, что вначале все состояния узлов имеют значение True.
class Node:
def __init__(self, val):
self.val = val
self.lchild = None
self.rchild = None
self.flag = True
Мы добавляем флаг в класс Node в качестве записи, и по умолчанию для него установлено значение True во время инициализации. Дальше все очень просто.Обходим узлы в порядке левый,средний и правый.Пока существует левое поддерево,обходим налево.Флажки этих узлов,встречающиеся в процессе прохождения до конца left для всех установлено значение False, потому что их поиск с возвратом уже начался, и в будущем возврата не будет. Так как проблемы с возвратом при обходе вправо нет, то его можно не учитывать, если вы его понимаете, то код будет логичным.
# 使用我们自己刚刚创建的数据结构
stack = Stack()
# 插入根节点
stack.push(root)
while not stack.is_empty():
# 获取栈顶元素，也就是当前遍历的节点
tmp = stack.top()
# 如果不曾回溯过，并且左子树存在
while tmp.flag and tmp.lchild is not None:
# 回溯标记置为False
tmp.flag = False
# 栈顶push左孩子
stack.push(tmp.lchild)
# 往左遍历
tmp = tmp.lchild
# 弹出栈顶
tmp = stack.pop()
# 此时说明左节点已经遍历完了，输出
print(tmp.val)
# 往右遍历
if tmp.rchild is not None:
stack.push(tmp.rchild)
Несмотря на то, что этот код короткий, он не прост, и для полного его понимания требуется глубокое понимание рекурсии и циклов. Это типичный вопрос, который выглядит простым и непростым. Лично мне нравятся такие вопросы. В дополнение к тренировке мышления, он также очень подходит для собеседований. Способность кандидата к мышлению и способность управлять кодом в основном очевидны. Студенты, которые не понимают этого, не должны беспокоиться, потому что такая сцена не встретится в реальных сценариях, и в будущем будут выпущены другие статьи о рекурсии и алгоритмах поиска.Пока вы продолжаете читать, я верю ты поймешь это.
На сегодняшней статье все, если вы найдете что-то полезное, пожалуйстаОтсканируйте код и обратите вниманиеЧто ж, твое маленькое усилие много значит для меня.