In this article, we are going to create our own class to represent a Stack in JavaScript.
The Stack Data Structure Overview
What is a Stack?
A stack is an ordered list in which insertion and deletion are done at one end, called a top. The last element inserted is the first one to be deleted. Hence, it is called the Last in First out (LIFO) or First in Last out (FILO) list.
Stack Real-World Examples
1. In the below diagram, the first image shows a container is filled with balls we will try to always take a last inserted ball so it is a last in first out. The second image is a list of mail envelopes and most of the peoples will always take the topmost envelope and then second top etc.
2. A pile of plates in a cafeteria is a good example of a stack. The plates are added to the stack as they are cleaned and they are placed on the top. When a plate, is required it is taken from the top of the stack. The first plate placed on the stack is the last one to be used.
Let's first understand the step by step implementation of Stack using Array.
Creating a Stack
Let's declare our JavaScript class:
class Stack {
//properties and methods go here
}
First, we need a data structure that will store the elements of the stack. We can use an array to do this:
let items = [];
Next, we need to declare the methods available for our stack:
- push(element(s)): This adds a new item (or several items) to the top of the stack.
- pop(): This removes the top item from the stack. It also returns the removed element.
- peek(): This returns the top element from the stack. The stack is not modified (it does not remove the element; it only returns the element for information purposes).
- isEmpty(): This returns true if the stack does not contain any elements, and false if the size of the stack is bigger than 0.
- clear(): This removes all the elements of the stack.
- size(): This returns the number of elements that the stack contains. It is similar to the length property of an array
Pushing elements to the Stack
The first method that we will implement is the push method. This method is responsible for adding new elements to the stack with one very important detail: we can only add new items to the top of the stack, meaning at the end of the stack. The push method is represented as follows:
push(element) {
this.items[this.count] = element;
this.count++;
}
Note that we are using the in-built push() method from the JavaScript Array class.
Popping elements from the stack
Next, we are going to implement the pop method. This method is responsible for removing the items from the stack. As the stack uses the LIFO principle, the last item that we added is the one that is removed. The pop method is represented as follows:
pop() {
if (this.isEmpty()) {
return undefined;
}
this.count--;
const result = this.items[this.count];
delete this.items[this.count];
return result;
}
Verifying if the stack is empty
The next method is the isEmpty method, which returns true if the stack is empty (no item has been added), and false otherwise:
isEmpty() {
return this.count === 0;
}
Clearing and printing the elements of the stack
Finally, we are going to implement a clear method. The clear method simply empties the stack, removing all its elements.
The simplest way of implementing this method is as follows:
clear() {
this.items = {};
this.count = 0;
}
Let's implement a helper method called print that is going to output the content of the stack on the console:
toString() {
if (this.isEmpty()) {
return '';
}
let objString = `${this.items[0]}`;
for (let i = 1; i < this.count; i++) {
objString = `${objString},${this.items[i]}`;
}
return objString;
}
Complete Example and Output
class Stack {
constructor() {
this.count = 0;
this.items = {};
}
push(element) {
this.items[this.count] = element;
this.count++;
}
pop() {
if (this.isEmpty()) {
return undefined;
}
this.count--;
const result = this.items[this.count];
delete this.items[this.count];
return result;
}
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1];
}
isEmpty() {
return this.count === 0;
}
size() {
return this.count;
}
clear() {
/* while (!this.isEmpty()) {
this.pop();
} */
this.items = {};
this.count = 0;
}
toString() {
if (this.isEmpty()) {
return '';
}
let objString = `${this.items[0]}`;
for (let i = 1; i < this.count; i++) {
objString = `${objString},${this.items[i]}`;
}
return objString;
}
}
Using Stack
const stack = new Stack();
console.log('stack.isEmpty() => ', stack.isEmpty()); // outputs true
stack.push(12);
stack.push(13);
console.log('stack after push 12 and 13 => ', stack.toString());
console.log('stack.peek() => ', stack.peek()); // outputs 13
stack.push(14);
console.log('stack.size() after push 11 => ', stack.size()); // outputs 3
console.log('stack.isEmpty() => ', stack.isEmpty()); // outputs false
stack.push(15);
stack.pop();
stack.pop();
console.log('stack.size() after push 15 and pop twice => ', stack.size()); // outputs 2
Output
stack.isEmpty() => true
stack after push 12 and 13 => 12,13
stack.peek() => 13
stack.size() after push 11 => 3
stack.isEmpty() => false
stack.size() after push 15 and pop twice => 2
Comments
Post a Comment
Leave Comment