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

Зачем использовать стек?

У стеков есть несколько реальных приложений, начиная от простых задач, таких как обращение строки, и заканчивая более сложными, такими как алгоритмы поиска с возвратом. Концепция относительно проста, но ее полезность невозможно переоценить. Давайте посмотрим, как работает стек.

В стеках реализована структура «Первым пришел, последним вышел». Это означает, что при сохранении элементов у вас есть доступ только к последнему добавленному элементу в стек.

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

stack.add(Banana)
stack.add(Durian)
stack.add(Blueberry)
stack.add(Cheery)

Наши элементы будут добавлены в стек следующим образом:

Обратите внимание, мы также отслеживаем указатель, который всегда указывает на последний добавленный элемент в наш стек. Это ключ к функции стека. Мы можем получить только самый последний элемент и ни один из элементов, находящихся ниже в стеке, до тех пор, пока более свежие элементы не будут «вытолкнуты» из стека. На первый взгляд это кажется ограничением, но именно эта функциональность делает эту структуру данных такой эффективной. Я наткнулся на прекрасную статью, в которой рассказывается о реализации всех необходимых функций для реализации стека в JavaScript:



Реализация стека в JavaScript
Они похожи на массивы с большей структурой и правиламиbetterprogramming.pub



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

Крыса в лабиринте

Это очень известный вопрос, и у него есть несколько решений. Давайте пройдемся по подсказке и настройке.

  1. Лабиринт задается через двоичную матрицу блоков с N*N пробелами. бывший:
const maze = [
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]

В этом лабиринте блоки с пометкой «1» доступны, а блоки «0» заблокированы.

2. Исходная или начальная позиция — это верхний правый угол матрицы: maze[0][0], а конечная или конечная точка — нижний правый угол: maze[N-1][N-1].

3. Крыса начинает с источника и должна добраться до места назначения. Он может двигаться только вправо или вниз. Мы можем упростить это позже, рассмотрев следующие варианты: "Переместить x" или "Переместить y".

Концептуальное решение

Давайте подумаем обо всей информации, необходимой для решения этой задачи. В идеале мы хотели бы, чтобы возвращался список ходов, который ведет нас от источника к месту назначения, или возвращался false, если их не существует. Давайте рассмотрим координаты (X, Y), начиная с самого верхнего левого блока, и используем рекурсивную функцию, чтобы доставить нашу крысу к месту назначения. Во-первых, всякий раз, когда крыса движется, нам нужно проверить, достигла ли крыса места назначения. Если так, то у нас есть свой путь. Таким образом, нам нужно будет отслеживать четыре элемента информации по мере рекурсии:

  1. Сам лабиринт
  2. Положение крыс X
  3. Положение крысы Y
  4. Матрица решений для отслеживания посещенных нами блоков

Наша рекурсивная функция должна делать несколько вещей:

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

Давайте запустим нашу доску. Начнем с крысы в ​​исходном положении: maze[0][0]

Ход №1

// using this recursive function with these arguments:
function solveMaze(maze, xPos, yPos, solMatrix) {
   ...
}
solveMaze(maze, 0, 0, sol)
// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]
// sol matrix
[
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]
  1. Отметьте матрицу sol
  2. Не пункт назначения
  3. Переместить Х недоступно
  4. Переместить Y

Ход №2

solveMaze(maze, 0, 1, sol)
// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]
// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]
  1. Отметьте матрицу sol
  2. Не пункт назначения
  3. Переместить X

Ход №3

solveMaze(maze, 1, 1, sol)
// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]
// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Ход №4

solveMaze(maze, 2, 1, sol)
// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]
// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Ход № 5

solveMaze(maze, 2, 2, sol)
// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]
// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Ход № 6

solveMaze(maze, 3, 2, sol)
// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]
// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Ход №7

solveMaze(maze, 4, 2, sol)
// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]
// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Наконец мы достигли точки, где нам нужно вернуться назад. Поскольку мы использовали стек для отслеживания наших ходов, мы сохранили эти 7 ходов.

stack = [
    solveMaze(maze, 0, 0, sol),
    solveMaze(maze, 0, 1, sol),    
    solveMaze(maze, 1, 1, sol),
    solveMaze(maze, 2, 1, sol),
    solveMaze(maze, 2, 2, sol),
    solveMaze(maze, 3, 2, sol),
    solveMaze(maze, 4, 2, sol)
]

На этом этапе мы можем «вытащить» последний ход из стека [тот, что с позицией (4,2)] и попробовать еще раз:

Ход №8

solveMaze(maze, 3, 2, sol)
// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]
// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]
  1. Отметьте sol-матрицу (уже сделано)
  2. Не пункт назначения
  3. Move X недоступен (поскольку он уже был посещен)
  4. Перемещение Y недоступно
  5. Возврат еще на один шаг

Ход № 9

solveMaze(maze, 2, 2, sol)
// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]
// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]
  1. Отметьте sol-матрицу (уже сделано)
  2. Не пункт назначения
  3. Move X недоступен (поскольку он уже был посещен)
  4. Переместить Y

Теперь мы отступили достаточно далеко, чтобы найти развилку, которая повела нашу крысу в неправильном направлении, и наш стек «выскочил» из неправильных ходов, которые больше не занимают место в памяти.

stack = [
    solveMaze(maze, 0, 0, sol),
    solveMaze(maze, 0, 1, sol),    
    solveMaze(maze, 1, 1, sol),
    solveMaze(maze, 2, 1, sol),
    solveMaze(maze, 2, 2, sol)
]

Давайте продолжим отсюда и посмотрим, что произойдет:

Ход №10

solveMaze(maze, 2, 3, sol)
// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]
// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0]
]

Ход №11

solveMaze(maze, 2, 4, sol)
// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]
// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 1, 0, 0],
    [0, 0, 1, 0, 0]
]

Ход №12

solveMaze(maze, 3, 4, sol)
// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]
// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 1, 0, 0],
    [0, 0, 1, 1, 0]
]

Ход №13

solveMaze(maze, 4, 4, sol)
// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]
// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 1, 0, 0],
    [0, 0, 1, 1, 1]
]
  1. Отметьте матрицу sol
  2. Пункт назначения достигнут! Возврат стека.
stack = [
    solveMaze(maze[4][4], 0, 0, sol[4][4]),
    solveMaze(maze[4][4], 0, 1, sol[4][4]),    
    solveMaze(maze[4][4], 1, 1, sol[4][4]),
    solveMaze(maze[4][4], 2, 1, sol[4][4]),
    solveMaze(maze[4][4], 2, 2, sol[4][4]),
    solveMaze(maze[4][4], 2, 3, sol[4][4]),
    solveMaze(maze[4][4], 2, 4, sol[4][4]),
    solveMaze(maze[4][4], 3, 4, sol[4][4]),
    solveMaze(maze[4][4], 4, 4, sol[4][4])
]

И из стека мы можем вывести путь крыс:

(0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2) -> (2,3) -> (2,4) -> (3,4) -> (4,4)

Вывод

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

Если вы хотите увидеть реализацию решения этого вопроса, перейдите по этой ссылке, которая включает несколько языков:



Крыса в лабиринте | Backtracking-2 - GeeksforGeeks
Мы обсуждали Backtracking и задачу путешествия Найта в Наборе 1. Давайте обсудим Крысу в лабиринте в качестве другого примера…www.geeksforgeeks.org



Спасибо за внимание и счастливого кодирования!