Have you ever used Undo or Redo when working on something?
Have you ever wondered how your favorite programming languages tend to turn the things you write into sequential steps that your computer knows what to do? Have you ever gone forward and backward in your browser? Do you like pancakes?
If you answered Yes to any of the above questions, then you have probably run into the star of this tutorial, the stack data structure. In the following sections, we'll learn more about stacks and how you can use one in JavaScript.
Onwards!
At some point in your life, I am pretty sure you have seen a stack of things arranged on top of each other...such as these pancakes:
The thing about stacks of things is that you always add items to the top. You remove items from the top as well:
This concept applies to things in the computer world as well. The stack is a well known data structure you will frequently encounter where, just like our pancakes, you keep adding data sequentially:
You remove the data from the end of your stack in the same order you added them:
In computer speak, this is known as a Last In First Out system - more commonly abbreviated as LIFO. The data that you end up accessing (aka removing) is the last one you added. That's really all there is to knowing about stacks, at least conceptually.
To use stacks in JavaScript and see the awesomeness for yourself, just add the following lines of code to your project:
class Stack {
constructor(...items) {
this.items = items;
}
clear() {
this.items.length = 0;
}
clone() {
return new Stack(...this.items);
}
contains(item) {
return this.items.includes(item);
}
peek() {
let itemsLength = this.items.length;
let item = this.items[itemsLength - 1];
return item;
}
pop() {
let removedItem = this.items.pop();
return removedItem;
}
push(item) {
this.items.push(item);
return item;
}
}
This code defines our Stack object and the various methods that you can use. To use it, all you have to do is something like the following:
let myStack = new Stack();
// Add items
myStack.push("One");
myStack.push("Two");
myStack.push("Three!");
// Preview the last item
myStack.peek(); // Three
// Remove item
let lastItem = myStack.pop();
console.log(lastItem) // Three
myStack.peek(); // Two
// Create a copy of the stack
let newStack = myStack.clone();
// Check if item is in Stack
newStack.contains("Three") // false
The first thing you need to do is create a new Stack object. You can create it an empty stack as shown or pre-fill it with some items as follows:
let stuffStack = new Stack("One", "Two", "Three");
To add items to the stack, use the push method and pass in whatever you wish to add. To remove an item, use the pop method. If you want to preview what the last item is without removing it, the peek method will help you out. The clone method returns a copy of your stack, and the contains method allows you to see if an item exists in the stack or not.
If you glance at the code, our stack implementation is just a wrapper over the Array object. Because items are added to the end and removed from the end, using the array's push and pop method works without any extra modification. The performance of adding and removing items from the end of an array is really good - constant time aka O(1) if you are keeping track.
For a discussion about this approach, check out the Simple Stack Implementation in JavaScript thread where senocular gave some great suggestions that made their way into the Stack code you saw earlier.
Just a final word before we wrap up. If you have a question and/or want to be part of a friendly, collaborative community of over 220k other developers like yourself, post on the forums for a quick response!