Greetings! Today, we're drawing back the curtains on Stacks in JavaScript, a crucial data structure. A stack
is like a pile of dishes: you add a dish to the top (Last In) and take it from the top (First Out). This Last-In, First-Out (LIFO) principle exemplifies the stack. JavaScript executes stacks effortlessly using Arrays
. This lesson will illuminate the stack data structure, operations, and their JavaScript applications. Are you ready to start?
A stack
is an elongated storehouse permitting Push
(addition) and Pop
(removal) operations. It's akin to a stack of plates in a cafeteria where plates are added (pushed
) and removed (popped
) from the top. No plate can be taken from the middle or the bottom, exemplifying a Last-In, First-Out (LIFO) operation.
To create a stack, JavaScript employs a built-in data structure known as an Array
. For the Push
operation, we use push()
, which adds an element at the array's end. For the Pop
operation, there's the pop()
function that removes the last element, simulating the removal of the 'top' element in a stack. Here's how it looks:
JavaScript1let stack = []; // A new empty stack 2 3// Push operations 4stack.push('John'); 5stack.push('Mary'); 6stack.push('Steve'); 7 8stack.pop(); // Pop operation removes 'Steve' 9console.log(stack); // Outputs: ['John', 'Mary']
In the example provided, we push 'John'
, 'Mary'
, and 'Steve'
into the stack and then pop 'Steve'
from the stack.
Stacks' operations go beyond merely push
and pop
. For example, to verify if a stack is empty, we can use the length
property. If it returns 0, that means the stack is empty. Conversely, if it returns a nonzero value, we can infer the stack is not empty. To peek at the top element of the stack without popping it, merely indexing with stack[stack.length - 1]
is handy.
Here's an example:
JavaScript1stack.push('Sam'); 2console.log(stack[stack.length - 1]); // Outputs: 'Sam'
In this example, 'Sam'
is added (pushed
), and then the topmost stack element, which is 'Sam'
, is peeked at.
Practical applications of stacks in JavaScript are plentiful. Here is one of them — reversing a string.
We will push all characters into a stack and then pop them out to get a reversed string!
JavaScript1function reverseString(inputString) { 2 let stack = inputString.split(''); 3 4 let reversedString = ''; 5 while (stack.length > 0) { 6 reversedString += stack.pop(); 7 } 8 return reversedString; 9} 10 11console.log(reverseString('HELLO')); // Outputs: OLLEH
A stack can be utilized to verify if parentheses in an expression are well-matched, i.e., every bracket has a corresponding pair. For example, parentheses in the string "()[{}]"
are well-matched, while in the strings "([]()"
, ")()[]{}"
, "([)]"
, and "[{})"
they are not.
Let's break down the solution into simple steps:
We start by creating an object that maps each closing bracket to its corresponding opening bracket and an empty stack. Then, we iterate over each character paren
in the string parenString
:
paren
is an opening bracket, it gets appended to the stack.paren
is a closing bracket and the top element in the stack is the corresponding opening bracket, we remove the top element from the stack.false
.Finally, if the stack is empty (all opening brackets had matching closing brackets), we return true
. If there are some unmatched opening brackets left, we return false
.
JavaScript1function isParenBalanced(parenString) { 2 let stack = []; 3 let isBalanced = true; 4 let index = 0; 5 const openingParen = {')': '(', ']': '[', '}': '{'}; // a matching opening parenthesis for every closing one 6 7 // Traversing all string characters 8 while (index < parenString.length && isBalanced) { 9 let paren = parenString[index]; 10 if (paren in openingParen) { 11 if (stack.length === 0 || stack[stack.length - 1] !== openingParen[paren]) { 12 isBalanced = false; 13 } else { 14 stack.pop(); 15 } 16 } else if ("([{".includes(paren)) { 17 stack.push(paren); 18 } 19 index++; 20 } 21 22 if (stack.length !== 0) { 23 // If after traversing all characters, there is something left, it's bad 24 isBalanced = false; 25 } 26 return isBalanced; 27} 28 29console.log(isParenBalanced("(())")); // Outputs: true 30console.log(isParenBalanced("({[)}")); // Outputs: false
Kudos to you! Having covered the stack data structure, operations, and their JavaScript applications is a commendable feat. Next up, you'll encounter practice exercises that will solidify your newly acquired knowledge. Dive into them and master Stacks in JavaScript!