Data Structures Series #1: Stacks - Implementation & Use Cases

Introduction

Welcome to my tech blog series, where I'll explore one data structure a day! In this first post, we’ll dive into Stacks, one of the fundamental data structures in computer science. We’ll cover its implementation in JavaScript, explore real-world use cases, and provide example code to reinforce your understanding.

What is a Stack?

A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle, meaning the last item added is the first one to be removed. Think of a stack of plates in a cafeteria—each new plate is placed on top, and you take the top plate first.

Key Operations in a Stack:

1. Push – Adds an element to the top of the stack.
2. Pop – Removes the top element from the stack.
3. Peek – Returns the top element without removing it.
4. isEmpty – Checks if the stack is empty.
5. Size – Returns the number of elements in the stack.

Implementing a Stack in JavaScript

1. Using an Array (Simplest Approach)

JavaScript arrays have built-in methods (push and pop) that make it easy to implement a stack.

class Stack { constructor() { this.items = []; } push(element) { this.items.push(element); } pop() { if (this.isEmpty()) { return null; } return this.items.pop(); } peek() { return this.isEmpty() ? null : this.items[this.items.length - 1]; } isEmpty() { return this.items.length === 0; } size() { return this.items.length; } } // Usage example const stack = new Stack(); stack.push(10); stack.push(20); console.log(stack.peek()); // 20 console.log(stack.pop()); // 20 console.log(stack.size()); // 1 

2. Using a Linked List (More Efficient for Large Data Sets)

For a more efficient stack (especially for large-scale applications), we can implement it using a linked list, avoiding array resizing overhead.

class Node { constructor(value) { this.value = value; this.next = null; } } class Stack { constructor() { this.top = null; this.length = 0; } push(value) { const newNode = new Node(value); newNode.next = this.top; this.top = newNode; this.length++; } pop() { if (this.isEmpty()) { return null; } const poppedValue = this.top.value; this.top = this.top.next; this.length--; return poppedValue; } peek() { return this.isEmpty() ? null : this.top.value; } isEmpty() { return this.length === 0; } size() { return this.length; } } // Usage example const stack = new Stack(); stack.push(10); stack.push(20); console.log(stack.peek()); // 20 console.log(stack.pop()); // 20 console.log(stack.size()); // 1 

Real-World Use Cases of Stacks

1. Browser History Navigation

When you visit a webpage, it gets pushed onto a stack. Pressing the back button pops the last visited page.

class BrowserHistory { constructor() { this.history = new Stack(); } visitPage(url) { this.history.push(url); } goBack() { return this.history.pop(); } } const browser = new BrowserHistory(); browser.visitPage('google.com'); browser.visitPage('dev.to'); console.log(browser.goBack()); // dev.to 

2. Undo/Redo Functionality

Text editors use two stacks—one for undo and one for redo actions.

3. Expression Evaluation - Postfix, Prefix

Stacks are used to evaluate expressions like Postfix (Reverse Polish Notation) and Prefix Notation.

function evaluatePostfix(expression) { const stack = new Stack(); const tokens = expression.split(' '); for (let token of tokens) { if (!isNaN(token)) { stack.push(parseInt(token)); } else { const b = stack.pop(); const a = stack.pop(); switch (token) { case '+': stack.push(a + b); break; case '-': stack.push(a - b); break; case '*': stack.push(a * b); break; case '/': stack.push(a / b); break; } } } return stack.pop(); } console.log(evaluatePostfix("2 3 + 5 *")); // 25 

4. Expression Evaluation - Syntax Parsing

Stacks are used in evaluating arithmetic expressions and validating balanced parentheses in expressions like:

function isBalanced(expression) { const stack = []; const pairs = { '(': ')', '{': '}', '[': ']' }; for (let char of expression) { if (pairs[char]) { stack.push(char); } else if (Object.values(pairs).includes(char)) { if (!stack.length || pairs[stack.pop()] !== char) { return false; } } } return stack.length === 0; } console.log(isBalanced("( [ { } ] )")); // true console.log(isBalanced("( [ { ] } )")); // false 

5. Backtracking Algorithms

Stacks are essential for solving problems using backtracking, such as maze solving, depth-first search (DFS) in graphs, etc.

Conclusion

Stacks are a fundamental data structure that power many real-world applications, from browser history management to expression evaluation. By understanding their implementation in JavaScript and their use cases, you’ll be well-equipped to use them effectively in your projects.

Stay tuned for the next post in this series, where we’ll explore Queues!

🔗 Connect with Me

If you found this post helpful, follow me on Dev.to for more insights on data structures and algorithms!