It's Friday night, and after a hard week, all you want is to play ranked matches in Street Fighter 6 for that dopamine rush from defeating novice players. But before that, you realize your dishes have gone unwashed for three days, and your wife is as furious as a Ken player who failed to trap you in the corner.
You need to tackle this stack of plates before you can even think about putting your hands on that controller. When you reach the last plate, you realize that you forgot to throw away the food remains, and now it's an indescribable, amorphous thing staring directly at you. This plate was the first in and the last out—and now you regret not maintaining this basic habit.
LIFO in Action
This is a great example of the LIFO principle, this means that the last item to be added to the stack is going to be the first to be removed.
This has great usability in scenarios when you need to keep track of function calls, undo operations or manage resources in a controlled manner.
Stacks are there in our daily basis, so today we are going to implement our own custom stack in typescript.
All About Nodes
To store each item in the stack, we'll create a Node class. We'll take an approach similar to linked lists, where each node connects to the next one. This structure allows us to efficiently add or remove items from the same side of the stack.
export class Node<T> {
value: T;
next: Node<T> | null;
constructor(value: T) {
this.value = value;
this.next = null;
}
}
This is a simple yet effective implementation that serves two essential purposes: storing the actual value we want to keep in our stack and maintaining a reference to the next Node in the sequence. The Node class uses generics (represented by ) to allow for type flexibility, meaning our stack can store any data type—whether numbers, strings, objects, or custom types—while maintaining type safety throughout the application. When we instantiate a new Node, the next property is initially set to null, indicating it's not connected to any other node yet.
Creating our Stack Class
Now, let's proceed with creating our Stack class implementation using TypeScript generics. Generics allow us to build reusable components that can work with different data types while maintaining type safety throughout our application. By leveraging TypeScript's type system, we'll ensure our stack operates consistently regardless of what type of data it stores.
export class Stack<T> {}
This class will have two properties: first, which stores the top item in our stack, and size, which keeps track of our stack's length.
first: Node<T> | null;
size: number;
Then, in our constructor, when our stack is instantiated, we are going to initialize our stack with the necessary properties. This initialization process establishes the foundation of our data structure by setting up the first node and determining the initial size. The constructor takes a value parameter, which becomes the first element in our stack, ensuring that our stack begins with at least one item. This approach provides a clean starting point for stack operations and maintains type safety throughout the implementation.
constructor(value: T){
const newNode = new Node(value);
this.first = newNode;
this.size = 1;
}
Popping Up
This method removes the top node from our stack. First, we need to check our first variable to ensure the stack isn't empty.
if(this.first === null) {
return null; // Stack is empty
}
Now that we've ensured our stack isn't empty, we retrieve the top node's value in a temporary variable called poppedNode. Then we set our first pointer to the next node in line, making it the new top of our stack.
const poppedNode = this.first;
this.first = this.first.next;
Finally, we decrement our size property to reflect the removal and return the value of the poppedNode.
this.size--;
return poppedNode.value;
And there you go, our pop method is now fully implemented and ready to efficiently remove items from the top of our stack. This implementation follows the LIFO principle we discussed earlier, ensuring that only the most recently added element can be removed.
Pushing a New Item
This method adds a new node to the top of our stack. Similar to the pop method, we first check if our stack is empty. If it is, this new node becomes the first one in our stack.
if(this.first === null) {
this.first = new Node(value);
this.size = 1;
return;
}
If the stack is not empty, we need to add the new node to the top. First, we create a new Node instance. Then we link our existing first node as the next value of our new node and reassign the first pointer to this new node. Finally, we increment the size of our stack.
const newNode = new Node(value);
newNode.next = this.first;
this.first = newNode;
this.size++;
And there you go, our stack implementation now has the ability to efficiently push new nodes to the top of the stack. This method adheres to the LIFO principle by ensuring that newly added elements become immediately accessible at the top of the stack, ready to be the first ones removed when a pop operation is performed.
Peeking the Top Node
This method allows us to examine the top node of our stack without removing it, providing a valuable way to inspect the most recently added element. When implementing the peek operation, we first need to perform a crucial validation to verify that our stack contains at least one element.
if(this.first === null) {
return null; // Stack is empty
}
Once we confirm the stack isn't empty, we can simply return the value of the top node. Since we've already stored this in the first variable, we just need to return the value property of this node.
return this.first.value;
And there you have it. Our stack implementation now allows us to peek at the top node without removing it.
The Stack is Empty?
This method will check if our stack has nodes in it. It serves as a useful utility function that allows us to determine whether our stack contains any elements or if it's completely empty. To determine this, we simply check whether the size property equals zero.
return this.size === 0;
Complete Typescript Implementation
export class Node<T> {
value: T;
next: Node<T> | null;
constructor(value: T) {
this.value = value;
this.next = null;
}
}
export class Stack<T> {
first: Node<T> | null;
size: number;
constructor(value: T){
const newNode = new Node(value);
this.first = newNode;
this.size = 1;
}
push(value: T): void {
if(this.first === null) {
this.first = new Node(value);
this.size = 1;
return;
}
const newNode = new Node(value);
newNode.next = this.first;
this.first = newNode;
this.size++;
}
pop(): T | null {
if(this.first === null) {
return null;
}
const poppedNode = this.first;
this.first = this.first.next;
this.size--;
return poppedNode.value;
}
peek(): T | null {
if(this.first === null) {
return null;
}
return this.first.value;
}
isEmpty(): boolean {
return this.size === 0;
}
}
Final Thoughts
Stacks play a crucial role in recursive algorithms, offering an elegant solution for managing function calls and tracking execution states. Implementing a stack from scratch, as we've done here, provides valuable insight into the inner workings of this fundamental data structure. It serves as an excellent exercise for strengthening your understanding of both data structures and TypeScript's type system, while also developing practical skills that can be applied to solve complex programming challenges in real-world applications.
As usual, you can find this code and other Data Structures implementations in my GitHub repository: https://github.com/RubenOAlvarado/data-structures
Continue your learning journey and stay persistent with DSA challenges. See you in the next article!
Photo belongs to Jeremy Thomas in Unsplash
Top comments (0)