Cover image by Clem Onojeghuo on Unsplash
¿Español? Puedes encontrar la versión traducida de este artículo aquí: Estructuras de datos con JavaScript — Parte 1: Pilas (Stacks)
Data Structures! - Now, now, before we start to panic, let's just take a deep breath and jump into this (not so) magical adventure to unveil the mysteries of the commonly feared data structures in JavaScript: What are they, what are they good for and most important of all, how to implement them.
In this article, we'll start with what's probably one of the most common ones: Stacks. So where do we start? At the beginning!
What is a stack?
A stack is a structure used to store data that functions in a linear and unidirectional way. That last part is really important because it sets the rules that we'll need to follow when working with stacks: Every element or piece of data added to a stack will be included in the same order and direction (from start to end).
Stacks manage their data under a principle called LIFO (Last In First Out). This means that the last element we add will always be the first one that will be extracted from it.
A commonly used analogy to describe stacks is to think of the way that plates are stored in a kitchen cabinet. Every time we go to grab a new plate, we'll always take the one that sits at the top, which coincidentally was the last one we put there. (Sometimes we'll try to be clever and take the one in the middle, but then the plates fall, break, and we'll get in trouble 🤕)
Let's look at a graphical representation of how a stack would work: (we'll go through what every part of this is later):
When to use a stack
There are a lot of practical examples that we can find nowadays where stacks are being used. There is also a good chance that we've been using them on a daily basis without even knowing. In fact, to get to this article, we did it with one of the most used stacks that there is: the navigation history of our browser. Every new page that we visit is stored on top of the previous one, and it creates a stack of values that allows us to go back, one by one (with the back button).
Additionally, stacks are useful when we need a data structure to store data that will be displayed in chronological order (such as a list of latest tweets or articles). For this example, the most recent piece of data added will be the first one shown, and so on, and so on.
So every time that we need to store data in order, and then remove that data from the last one to the first one added, a stack will be your best friend.
Complexity of a stack
Depending on the type of implementation of a stack (by using an array or an object), there are different levels of complexity, both for space (amount of memory that it will use) and time (how long it will take to perform operations on that stack, such as: adding, reading, searching and deleting elements).
(Note: Let's consider n = depending on the number of elements in the structure, 1 = direct access).
Space complexity
- Array: O(n).
- Object: O(n).
For both cases, the space complexity will be O(n), meaning that it will increase or decrease proportionally to the number of elements that are stored.
Time complexity
For an implementation using arrays:
- Read: O(1)
- Search: O(n)
- Insert: O(n)
- Delete: O(n)
An using objects:
- Read: O(n)
- Search: O(n)
- Insert: O(1)
- Delete: O(1)
Methods and/or functionality of a stack
Traditionally, a stack needs to have functionality that allows to add new elements, extract them, and review them. Even though we can choose whatever name we want for these methods, there is a convention of using the following names to define them:
- push: Adds a new value at the end of the stack.
- pop: Returns the last value, removing it from the stack.
- peek: Returns the last value inserted, without removing it from the stack.
- size: Returns the number of elements that the stack has.
- print: Displays the contents of the stack.
How to implement a stack
Option 1: Using an array
Implementing a stack using arrays in JavaScript is relatively straightforward since most of the methods from the previous list are already included in the Array prototype implementation, so we only need to write a small wrapper that interacts with these methods and return the corresponding values.
The only method that we'll need to implement manually is peek, which will return the last value of the array, equal to the length of the array minus one (since arrays are zero index-based, but length shows the total amount of elements that the array contains, starting from 1).
The implementation would look something like this.
class Stack {
constructor() {
// we create and initialize the stack as an empty array.
this.stack = [];
}
push(element) {
// pushing an element uses the native push method.
this.stack.push(element);
return this.stack;
}
pop() {
// pop will return the last element by using the native pop method.
return this.stack.pop();
}
peek() {
// peek checks the last element of the array by using the length
// (total number of elements) minus 1 to find the right index.
return this.stack[this.stack.length - 1];
}
size() {
// size just returns the length of the array.
return this.stack.length;
}
print() {
// print will do a console log of the array
console.log(this.stack);
}
}
const stack = new Stack();
console.log(stack.size()); // 0
console.log(stack.push("Stone Cold Steve Austin")); // ["Stone Cold Steve Austin"]
console.log(stack.push("The Rock")); // ["Stone Cold Steve Austin", "The Rock"];
console.log(stack.size()); // 2
stack.print(); // ["Stone Cold Steve Austin", "The Rock"];
console.log(stack.peek()); // The Rock
console.log(stack.pop()); // The Rock
console.log(stack.peek()); // Stone Cold Steve Austin
Option 2: Using an object
Implementing a stack with an object requires a bit of additional work since the native methods of the arrays will not be available here, so we'll have to implement them manually.
One of the ways to achieve this is, when creating the stack, initialize a variable that will act as a cursor and keep the current position of the last element added, as well as the total number of elements inserted. Since the default behavior of a stack just requires us to add/remove the last element added, as long as we keep track of the current position, we should be able to achieve this.
constructor() {
this.stack = {};
this.count = 0;
}
To add elements, we'll use this.count as a reference of the current position and we'll use JavaScript's bracket notation to do a direct insertion in the object.
push(element) {
this.stack[this.count] = element;
this.count++;
return this.stack;
}
For peek, print y size, the implementation is basically the same as with arrays. The main difference is that we'll use this.count instead of Array.length to identify the index of the element that we'll need to show or to return the total number of elements added.
peek() {
return this.stack[this.count - 1];
}
size() {
return this.count;
}
print() {
console.log(this.stack);
}
Finally, for pop it'll be necessary to do some extra work. The difference with the last case is that after returning the element, we'll need to delete it from the object and move the cursor back to track the new last element.
pop() {
this.count--;
const element = this.stack[this.count];
delete this.stack[this.count];
return element;
}
The full implementation would be as follows:
class Stack {
constructor() {
this.stack = {};
this.count = 0;
}
push(element) {
this.stack[this.count] = element;
this.count++;
return this.stack;
}
pop() {
this.count--;
const element = this.stack[this.count];
delete this.stack[this.count];
return element;
}
peek() {
return this.stack[this.count - 1];
}
size() {
return this.count;
}
print() {
console.log(this.stack);
}
}
const stack = new Stack();
console.log(stack.size()); // 0
console.log(stack.push("Stone Cold Steve Austin")); // { "0": "Stone Cold Steve Austin" }
console.log(stack.size()); // 1
console.log(stack.peek()); // Stone Cold Steve Austin
console.log(stack.push("The Rock")); // { "0": "Stone Cold Steve Austin", "1": "The Rock" }
console.log(stack.size()); // 2
stack.print(); // { "0": "Stone Cold Steve Austin", "1": "The Rock" }
console.log(stack.peek()); // The Rock
console.log(stack.pop()); // The Rock
stack.print(); // { "0": "Stone Cold Steve Austin" }
console.log(stack.size()); // 1
console.log(stack.peek()); // Stone Cold Steve Austin
Source Code
You can find the source code of this example here:https://github.com/Xabadu/js-data-structures
Originally published on my blog at xabadu.dev
Top comments (0)