In JavaScript, a stack is a highly useful data structure that follows the Last In, First Out (LIFO) principle. This article delves into the concept of stacks and their practical applications in JavaScript.
1. Concept of a Stack
A stack is a linear data structure that allows insertion (called push) and deletion (called pop) only at one end, known as the top. Imagine a stack of plates—you can only add a plate to the top or remove the topmost plate.
Basic Stack Operations:
push(element): Adds an element to the top of the stack.
pop(): Removes and returns the top element of the stack.
peek(): Retrieves the top element without removing it.
isEmpty(): Checks whether the stack is empty.
2. Implementing a Stack in JavaScript
Below is a simple implementation of a stack in JavaScript:
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
if (this.isEmpty()) {
return "Underflow";
}
return this.items.pop();
}
peek() {
if (this.isEmpty()) {
return null;
}
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
}3. Practical Applications of Stacks
(1) Expression Evaluation
Converting Infix Expressions to Postfix:
In computer science, converting infix expressions (e.g., (2 + 3) * 4) to postfix expressions (e.g., 2 3 + 4 *) is a key application of stacks.
Algorithm Steps:
Initialize an empty stack for operators.
Traverse the infix expression from left to right.
If the current character is an operand, add it to the output.
If it's a left parenthesis, push it onto the stack.
If it's a right parenthesis, pop operators from the stack until a left parenthesis is encountered. Discard the left parenthesis.
If it's an operator, compare its precedence with the operator at the stack's top. Pop operators from the stack while their precedence is greater than or equal to the current operator's precedence. Push the current operator onto the stack.
After traversal, pop all remaining operators from the stack to the output.
JavaScript Implementation:
function infixToPostfix(expression) {
const stack = new Stack();
let postfix = "";
const precedence = {
'+': 1,
'-': 1,
'*': 2,
'/': 2
};
for (let char of expression) {
if (/[0-9]/.test(char)) {
postfix += char;
} else if (char === '(') {
stack.push(char);
} else if (char === ')') {
while (!stack.isEmpty() && stack.peek() !== '(') {
postfix += stack.pop();
}
stack.pop(); // Remove the left parenthesis
} else {
while (!stack.isEmpty() && precedence[stack.peek()] >= precedence[char]) {
postfix += stack.pop();
}
stack.push(char);
}
}
while (!stack.isEmpty()) {
postfix += stack.pop();
}
return postfix;
}Evaluating Postfix Expressions:
After converting an infix expression to postfix, evaluation becomes straightforward using stacks.
Algorithm Steps:
Traverse the postfix expression from left to right.
Push operands onto the stack.
When encountering an operator, pop two operands, apply the operator, and push the result back onto the stack.
At the end of traversal, the stack contains the result.
JavaScript Implementation:
function evaluatePostfix(postfix) {
const stack = new Stack();
for (let char of postfix) {
if (/[0-9]/.test(char)) {
stack.push(parseInt(char));
} else {
const operand2 = stack.pop();
const operand1 = stack.pop();
switch (char) {
case '+':
stack.push(operand1 + operand2);
break;
case '-':
stack.push(operand1 - operand2);
break;
case '*':
stack.push(operand1 * operand2);
break;
case '/':
stack.push(operand1 / operand2);
break;
}
}
}
return stack.pop();
}(2) Function Call Stack
In JavaScript, a call stack is used to manage the execution contexts of functions. When a function calls another function, its execution context is pushed onto the stack. Once the function completes, its execution context is popped from the stack.
Example:
function functionA() {
console.log("Inside functionA");
functionB();
}
function functionB() {
console.log("Inside functionB");
}
functionA();(3) Depth-First Search (DFS)
DFS is a graph traversal algorithm that can be implemented using a stack.
JavaScript Implementation:
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(vertex1, vertex2) {
this.adjacencyList[vertex1].push(vertex2);
this.adjacencyList[vertex2].push(vertex1);
}
dfs(startVertex) {
const stack = new Stack();
const visited = {};
stack.push(startVertex);
visited[startVertex] = true;
while (!stack.isEmpty()) {
const currentVertex = stack.pop();
console.log(currentVertex);
for (let neighbor of this.adjacencyList[currentVertex]) {
if (!visited[neighbor]) {
stack.push(neighbor);
visited[neighbor] = true;
}
}
}
}
}(4) Parentheses Matching
Stacks are useful for checking whether parentheses in a string are balanced.
JavaScript Implementation:
function isBalanced(str) {
const stack = new Stack();
for (let char of str) {
if (char === '(' || char === '[' || char === '{') {
stack.push(char);
} else if (char === ')' || char === ']' || char === '}') {
if (stack.isEmpty()) {
return false;
}
const top = stack.pop();
if ((char === ')' && top !== '(') ||
(char === ']' && top !== '[') ||
(char === '}' && top !== '{')) {
return false;
}
}
}
return stack.isEmpty();
}4. Conclusion
The stack is a powerful data structure with numerous applications in JavaScript, from expression evaluation to graph traversal and parentheses matching. Understanding the stack and its operations is crucial for writing efficient code and solving complex problems.
