Одним из типов структур данных, которые вы можете использовать при решении алгоритмов, является стек. Стек — это линейная структура, в которой добавление или удаление элемента происходит в определенном порядке: LIFO (последним пришел — первым ушел) или FILO (первым пришел — последним ушел).
Я буду использовать пример задачи из LeetCode под названием Действительные скобки.
В этой задаче вы получаете строку символов, которая может быть только «()», «[]», «{}», и вы должны создать алгоритм, чтобы проверить, является ли строка допустимой (т. е. все отверстия закрыты) и она дает вам примеры того, что квалифицируется как допустимая строка, а также примеры входных данных с соответствующими выходными данными.
Мой мыслительный процесс для этого состоял в том, чтобы проверить каждый символ, начинающийся с начала, и добавить его в структуру данных, если это открытие (
«(« , »[« », {«) и если это закрытие закрытия («)», «]», «}») проверить, является ли последний элемент в моей структуре данных соответствующим открытием, и если это так, удалить этот символ из моей структуры данных. Если ни одно из этих условий не выполняется, вернуть «false», так как закрытие не соответствует последнему открытию, следовательно, недействительная строка, и если в конце строки моя структура данных пуста, то вернуть «true», потому что все отверстия были закрыты, в противном случае ложно, потому что отверстие осталось незакрытым.
Я понял, что структура данных, которая хорошо подходит для этого, — это стек (поскольку мне понадобится метод LIFO для добавления/удаления). Два способа, которыми я научился их реализовывать, — это создание класса Stack (я называю это «формальным» способом) или использование массива (я называю это «неформальным» способом). Хотя просто использовать массив намного проще, я включил «формальный» способ на тот случай, если вам понадобится реализовать его в более сложной задаче.
- Создание класса стека
class Stack {
constructor () {
this.head = null;
this.tail = null;
this.length = 0;
this.data = []
}
push(element){
this.data.push(element)
}
pop(){
if (this.data.length == 0){
return false
}else{
this.data.pop()
}
}
peek(){
return this.data[this.data.length-1]
}
isEmpty(){
return this.data.length == 0
}
}
Для этого метода вы создаете класс с именем Stack, в конструкторе вы объявляете начальные значения для класса и объявляете вспомогательные методы, которые вам понадобятся, в этом случае это будет push (для добавления элемента), pop ( чтобы удалить элемент), peek (чтобы увидеть последний элемент) и isEmpty (чтобы увидеть, пуст ли стек. С этим вы можете реализовать решение ниже
var isValid = function(s) {
let stack = new Stack
for (let i=0; i < s.length; i++){
if (s[i] === "(" || s[i] === "[" || s[i] === "{"){
stack.push(s[i])
} else if (s[i] === ")" && stack.peek() === "("){
stack.pop()
} else if (s[i] === "]" && stack.peek() === "["){
stack.pop()
} else if (s[i] === "}" && stack.peek() === "{"){
stack.pop()
} else{
return false
}
}
return stack.isEmpty()
}
Обратите внимание, как я создаю новый экземпляр класса «Стек» и присваиваю его переменной «стек». Это позволит мне использовать вспомогательные методы в стеке по мере необходимости (нажать, чтобы добавить любые открытия, заглянуть, чтобы проверить последний элемент в моем стеке, вытолкнуть, чтобы удалить последний элемент, isEmpty, чтобы проверить, остался ли стек пустым после того, как мы итерируем через строку).
Примечание для себя — я только что понял, что вместо «заглянуть» я мог бы назвать вспомогательный метод «последним» или что-то подобное для ясности.
Вы, наверное, заметили, что я создал целый класс для одного экземпляра, который создает массив, чтобы использовать вспомогательные методы, которые в любом случае работали бы непосредственно с массивом (или имели бы простой обходной путь). Вот почему я остановился на втором методе: просто используя массив.
2. Использование массива
Для этого метода я полностью избегаю класса и просто назначаю массив в качестве своего стека:
var isValid = function(s) {
let stack = []
for (let i=0; i < s.length; i++){
if (s[i] === "(" || s[i] === "["|| s[i] === "{"){
stack.push(s[i])
} else if (s[i] === ")" && stack[stack.length-1] === "("){
stack.pop()
} else if (s[i] === "]" && stack[stack.length-1] === "["){
stack.pop()
} else if (s[i] === "}" && stack[stack.length-1] === "{"){
stack.pop()
} else{
return false
}
}
return !stack.length
};
Обратите внимание, что push и pop остаются неизменными, и вместо peek я просто ищу последний элемент в массиве напрямую, а вместо isEmpty проверяю, равна ли длина 0 (falsy) или нет (trueth), и возвращаю наоборот, поскольку длина 0 означает, что строка действительна (все отверстия правильно закрыты).
Хотя это работает просто отлично, это не очень СУХОЕ (т.е. много повторений) и не повторное использование (подходит только для этой конкретной ситуации), поэтому я хотел придумать способ немного подсушить его. Я понял, что все отверстия имеют одинаковую реакцию (добавить в стек), поэтому создал массив для группировки всех отверстий:
var isValid = function(s) {
let stack = []
const openings = ["(","[","{"]
for (let i=0; i < s.length; i++){
if (openings.includes(s[i])){
stack.push(s[i])
} else if (s[i] == ")" && stack[stack.length-1] === "("){
stack.pop()
} else if (s[i] == "]" && stack[stack.length-1] === "["){
stack.pop()
} else if (s[i] == "}" && stack[stack.length-1] === "{"){
stack.pop()
} else{
return false
}
}
return !stack.length
};
Хотя это немного помогает, особенно в крайнем случае, когда добавляется еще одно открытие, это ничего не делает с закрытием. Немного подумав, я пришел к следующему:
var isValid = function(s) {
const ref = {
')' : '(',
']' : '[',
'}' : '{',
}
const stack = []
for (const char of s) {
if (char in ref) {
if (ref[char] === stack[stack.length - 1]) {
stack.pop()
} else {
return false
}
} else {
stack.push(char)
}
}
return !stack.length
}
Вот что я сделал:
- Я создал эталонный объект для сохранения всех закрытий и соответствующих им открытий, таким образом, если есть другие пары, которые необходимо добавить, это можно сделать легко, и код будет работать.
- Я использовал цикл for of, так как он оптимизирован для массивов и строк.
- Я переключил оператор if, чтобы я мог искать ключи, чтобы проверить, является ли символ закрытием, и является ли последний элемент в стеке (массиве) подходящим открытием, если не соответствует, возвращает false. Если это не ключ, он предполагает, что это открытие, и добавляет его в стек (нет необходимости проверять, является ли это открытием).
- Я использовал «if(char in ref)» для поиска ключа объекта ref. В отличие от создания массива ключей и поиска в нем, это увеличит временную сложность до O (n²) (поиск в массиве внутри строки).
Я понял, что вышеупомянутые улучшения приносят в жертву немного времени, но временная сложность по-прежнему O (n) (линейное время), и требуется больше использования памяти с использованием объекта, но это незначительно, поскольку пространственная сложность по-прежнему O (n) . Однако код намного чище и допускает любое количество открывающих и закрывающих пар.
Вот статья, которая помогла мне понять это: https://www.geeksforgeeks.org/implementation-stack-javascript
Если вам нужна помощь в визуализации того, как работает стек, посетите этот сайт: http://visualgo.net/en/list.
