В структуре данных стек представляет собой последовательность объектов или элементов в формате линейной структуры данных. Некоторые из вас могут не понять концепцию стека, прочитав определение. Поэтому я решил объяснить это как можно проще с помощью рисунка. Вот простой пример стека:
Это стек. Он имеет линейную структуру с единственным способом входа и выхода. Следовательно, он должен следовать принципу LIFO (последний пришел первым ушел). Если я положу что-то внутрь стопки, она начнет заполняться снизу. По мере того, как я продолжаю добавлять вещи в стек, он начнет «складываться» и в итоге получится вот так:
Как я упоминал ранее, стек следует принципу LIFO, и доступ к элементу внизу невозможен без удаления элементов вверху.
В JavaScript есть различные методы, которые мы можем использовать для внесения любых изменений, но я расскажу только о методах push и pop.
Метод push просто «проталкивает» новый элемент на самый верх стека. Это похоже на изображение сверху, где я нажимаю буквы алфавита сверху вниз.
Метод pop удаляет элементы в самом верху стека. Итак, если я применю метод pop один раз, он удалит букву «f» из стека, поскольку в данный момент она находится на самом верху стека.
Применить к коду
Теперь, когда мы понимаем, как работает стек, давайте применим это к реальной проблеме кодирования. Допустим, мне нужно создать функцию, которая может проверять, является ли строка, содержащая связку «{» и «}», сбалансированной или нет.
Во-первых, я создам стек, используя обычный массив, с которым мы все знакомы.
function checkBracesString(s){ // This is our stack! // Yes, I know it's an array but, we are using it as a stack. let stack = []; } console.log(checkBracesString('{{{}}}')) // expecting: true console.log(checkBracesString('}{{{}}}}}}')) //expecting: false
Я создал функцию, которая содержит стек. Теперь я хочу проверить каждую букву на фигурные скобки, используя цикл for. Здесь я хочу проверить каждую букву, используя операторы if и else. Остальной код выглядит так.
function checkBracesString(s){ let stack = []; // Looping through each letters using a for loop. for(let i = 0; i < s.length; i++){ // If there the letter at the position s[i] is equal to '{', push it into the stack if(s[i] === '{'){ stack.push(s[i]) // Else if the letter is equal to '}', then move onto next if statement. }else if(s[i] === '}'){ // First, I want to check the stack itself if it's empty. If it's empty, that means there's no '{' to cancel out. So return false. if(stack.length === 0){ return false; // If the stack is not empty, then move onto next condition. // Else if the letter at the very top of the stack is equal to '{', pop out from the stack. } else if(stack[stack.length-1] === '{'){ stack.pop(); // Else, return false } else { return false; } } } // The stack must be empty at the end to return true(Balanced). Otherwise, it's a false(unbalanced). return stack.length === 0; } console.log(checkBracesString('{{{}}}')) // expecting: true console.log(checkBracesString('}{{{}}}}}}')) //expecting: false
Для визуалов я нарисовал процесс, который может вам помочь. Хотя я не лучший художник. Кроме того, я добавил изображение моего действительно работающего кода.
Я надеюсь, что это поможет тем, кто в настоящее время изучает структуру данных и алгоритмы, как я. Попробуйте решить эту проблему самостоятельно и дайте мне знать, какими еще способами вы можете решить эту проблему.
В остальном, хорошего дня!