A Stack is a simple linear data structure that works like a stack of plates ๐ฝ๏ธ. It follows the Last In, First Out (LIFO) principle. Think of it as a pile of plates: you can only add or remove plates from the top of the pile.
For a better understanding of stack, let's embark on a short journey of imagination ๐.
Imagine you're at a fancy restaurant ๐ฝ๏ธ, and the kitchen staff is preparing for a busy night ๐จโ๐ณ. In the dish area, there's a tall stack of plates waiting to be used. As diners arrive and orders pour in, the staff takes plates from the top of the stack. When clean plates are added, they go right on top. This simple system ensures that the plates at the bottom of the stack which have been there the longest are used last, while the freshly cleaned plates on top are used first โจ.
This, in essence, is how a Stack data structure works. A Stack is a linear data structure that follows the Last In First Out (LIFO) principle. Just like with our stack of plates, the last item added to a Stack is the first one to be removed.
Table of Contents
In this comprehensive tutorial on the stack data structure, we'll explore the following topics with a simple, beginner-friendly approach:
- What is a Stack?
- Pros and Cons of Using Stack
- Real-World Applications of Stacks
- Key Operations on a Stack
- Stack Implementation in JavaScript
- Conclusion
Are you ready? Let's dive in
What is a Stack?
A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Think of it like a stack of books: you can only add or remove books from the top of the stack.
Pros and Cons of Using Stack
Before we continue with the flow and write some codes, it is great to understanding where and where not to use Stack. The table below give an explicit Pros and Cons of Stack in details.
| Pros | Cons |
|---|---|
| Simple and easy to implement | Limited access (only top element is directly accessible) |
| Efficient for Last-In-First-Out (LIFO) operations | Not suitable for random access of elements |
| Constant time O(1) for push and pop operations | Can lead to stack overflow if not managed properly |
| Useful for tracking state in algorithms (e.g., depth-first search) | Not ideal for searching or accessing arbitrary elements |
| Helps in memory management (e.g., call stack in programming languages) | Fixed size in some implementations (array-based stacks) |
| Useful for reversing data | May require resizing in dynamic implementations, which can be costly |
| Supports recursive algorithms naturally | Not efficient for large datasets that require frequent traversal |
| Helps in expression evaluation and syntax parsing | Potential for underflow if pop operation is called on an empty stack |
| Useful in undo mechanisms in software | Limited functionality compared to more complex data structures |
| Efficient for certain types of data organization (e.g., browser history) | Not suitable for problems requiring queue-like (FIFO) behavior |
Key Operations on a Stack
The fundamental operations that can be performed on a stack are:
-
push(): Adds an element to the top of the stack. -
pop(): Removes the topmost element from the stack. -
peek(): Returns the top element of the stack without removing it. -
isEmpty(): Checks if the stack is empty. -
size(): Returns the number of elements in the stack.
Real-World Applications of Stacks
Stacks are every where in computer science and software development. Here are some common applications:
Undo Functionality: In text editors or graphic design software, each action is pushed onto a stack. When you hit "undo," the most recent action is popped off the stack and reversed.
Browser History: When you visit a new page, it's pushed onto a stack. The "back" button pops the current page off the stack, revealing the previous one.
Function Call Stack: In programming languages, function calls are managed using a stack. When a function is called, it's pushed onto the call stack. When it returns, it's popped off.
Expression Evaluation: Stacks are used to evaluate arithmetic expressions, especially those in postfix notation.
Backtracking Algorithms: In problems like maze-solving or puzzle-solving, stacks can keep track of the path taken, allowing easy backtracking when needed.
Stack Implementation in JavaScript
Now, let's implement a Stack in JavaScript. It is important to know that there are different ways to implement a stack in JavaScript. One of the common ways to implement a stack is using array, another way is to use linked list. In this article, we'll implement a stack using linked list (singly linked list).
Implement Stack using Linked List
I hope you still remember how linked list works? You might need to check out the linked list implementation in one of our previous articles in this same series.
Now, let's start implementing our stack using singly linked list. Shall we?
First, we'll create a Node class to represent our stack individual item.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
Then, we'll create a Stack class to represent our stack.
class Stack {
constructor() {
this.top = null;
this.size = 0;
}
// Stack Operations will be implemented here ๐
}
Push Operation
The push operation adds a new element to the top of the stack. It creates a new StackNode, sets its next pointer to the current top, and then updates top to point to this new node. Finally, it increments the size.
// Push element to the top of the stack
push(element) {
const newNode = new Node(element);
newNode.next = this.top;
this.top = newNode;
this.size++;
}
Pop Operation
The pop operation removes the topmost element from the stack. It first checks if the stack is empty. If it is, it returns an error message. Otherwise, it removes the top element, updates the top pointer to the next node, and decrements the size. Finally, it returns the removed element.
// Remove and return the top element
pop() {
if (this.isEmpty()) {
return "Stack is empty";
}
const poppedElement = this.top.data;
this.top = this.top.next;
this.size--;
return poppedElement;
}
Peek Operation
The peek operation returns the top element without removing it. It first checks if the stack is empty. If it is, it returns an error message. Otherwise, it returns the data of the top element.
// Return the top element without removing it
peek() {
if (this.isEmpty()) {
return "Stack is empty";
}
return this.top.data;
}
isEmpty Operation
The isEmpty operation checks if the stack is empty. It returns true if the stack is empty, and false otherwise.
// Check if the stack is empty
isEmpty() {
return this.size === 0;
}
getSize Operation
The getSize operation returns the size of the stack. It returns the number of elements in the stack.
// Return the size of the stack
getSize() {
return this.size;
}
Print Operation
The print operation prints the stack. It returns the data of the top element.
// Print the stack
print() {
let current = this.top;
let result = "";
while (current) {
result += current.data + " ";
current = current.next;
}
console.log(result.trim());
}
Usage Example
// Usage example
const customStack = new CustomStack();
customStack.push(10);
customStack.push(20);
customStack.push(30);
console.log(customStack.pop()); // 30
console.log(customStack.peek()); // 20
console.log(customStack.getSize()); // 2
console.log(customStack.isEmpty()); // false
customStack.print(); // 20 10
In this implementation, we used a linked list (singly linked list) structure to represent our stack. Each element is a Node with a data value and a reference to the next Node. The top of the stack is always the most recently added Node.
Conclusion
Stacks are a fundamental data structure in computer science that follow the Last In, First Out (LIFO) principle. They are used in various applications, including managing function calls, implementing undo functionality, and evaluating arithmetic expressions.
In this tutorial, we've covered the basics of stacks, pros and cons of using them, and their implementation in JavaScript (using linked list). Understanding stacks is not just about knowing how to implement them, but also recognizing when they're the right tool for solving a problem.
As you continue your journey in software development, you'll find that stacks are an indispensable tool in your problem-solving toolkit. They're simple yet powerful, and mastering them will significantly enhance your ability to design efficient algorithms and data structures.
Stay Updated and Connected
To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:
Stay tuned and happy coding ๐จโ๐ป๐
Top comments (0)