What is stack data structure?
A stack is an abstract data type that stores an ordered collection of items which follow first in last out (FILO) or last in first out (LIFO) principle; with two principal operations: push, which adds an item to the stack, and pop, which removes the most recently added item.
Requirements
The stack data strucuture should contain the following methods:
push: add an item
pop: remove the most recently added item
peek: get the most recently added item
size: get the total number of items
isEmpty: return a boolean whether or not it is empty
clear: remove all the items
The data flow in and out from the stack should follow the first in last out (FILO) or last in first out (LIFO) principle. Think of this as a pile of books on your desk; the first book you put on the desk, is the last book you pick up. It is because when you pick up a book, you have to pick up the book that is on the top.
How to store the data?
There are two ways of storing the data in stack data structure; one is an array, the other is object. We will implement both of them.
Stack Data Structure Using Array
class Stack {
constructor() {
// AN ARRAY TO STORED AN ORDERED COLLECTION OF ITEMS
this._items = [];
}
/**
* Add an item
* @param {*} item
* @time complexity: O(1)
* @space complexity: O(N)
*/
push(item) {
this._items.push(item);
}
/**
* Remove the most recently added item
* @return {*}
* @time complexity: O(1)
* @space complexity: O(1)
*/
pop() {
return this._items.pop();
}
/**
* Get the most recently added item
* @return {*}
* @time complexity: O(1)
* @space complexity: O(1)
*/
peek() {
return this._items[this._items.length - 1];
}
/**
* Check whether it contains no items
* @return {boolean}
* @time complexity: O(1)
* @space complexity: O(1)
*/
isEmpty() {
return this._items.length === 0;
}
/**
* Get the total number of items
* @return {number}
* @time complexity: O(1)
* @space complexity: O(1)
*/
size() {
return this._items.length;
}
/**
* Remove all items
* @time complexity: O(1)
* @space complexity: O(1)
*/
clear() {
this._items = [];
}
}
Stack Data Structure Using Object
class Stack {
constructor() {
// STORED ITEMS
this._items = {};
// TOTAL NUMBER OF ITEMS
// ALSO USED AS A KEY TO KEEP ITEMS IN ORDER
this._count = 0;
}
/**
* Add an item
* @param {*} item
* @time complexity: O(1)
* @space complexity: O(N)
*/
push(item) {
this._items[this._count] = item;
this._count++;
}
/**
* Remove the most recently added item
* @return {*}
* @time complexity: O(1)
* @space complexity: O(1)
*/
pop() {
if (this.isEmpty()) {
return undefined;
}
this._count--;
const result = this._items[this._count];
delete this._items[this._count];
return result;
}
/**
* Get the most recently added item
* @return {*}
* @time complexity: O(1)
* @space complexity: O(1)
*/
peek() {
if (this.isEmpty()) {
return undefined;
}
return this._items[this._count - 1];
}
/**
* Check whether it contains no items
* @return {boolean}
* @time complexity: O(1)
* @space complexity: O(1)
*/
isEmpty() {
return this._count === 0;
}
/**
* Get the total number of items
* @return {number}
* @time complexity: O(1)
* @space complexity: O(1)
*/
size() {
return this._count;
}
/**
* Remove all items
* @time complexity: O(1)
* @space complexity: O(1)
*/
clear() {
this._items = {};
this._count = 0;
}
} Protecting the internal data
So far both implementation works, but are not protecting the data. What I mean is that, you or someone else still can access and modify the data directly without calling the functions. This is bad, because they might break the FILO or LIFO principle.
For this reason, we as developers prefer to use underscore ( _ ) naming convention to mark an attribute as private in javascript. But that doesn't prevent other people to modify it.
In order to protect the data, we have to use WeakMap. The following implementation uses WeakMap to store the data.
Stack Data Structure Using Object With WeakMap
const items = new WeakMap();
const count = new WeakMap();
class Stack {
constructor() {
// STORED ITEMS
items.set(this, {});
// TOTAL NUMBER OF ITEMS
// ALSO USED AS A KEY TO KEEP ITEMS IN ORDER
count.set(this, 0);
}
/**
* Add an item
* @param {*} item
* @time complexity: O(1)
* @space complexity: O(N)
*/
push(item) {
items.get(this)[count.get(this)] = item;
count.set(this, count.get(this) + 1);
}
/**
* Remove the most recently added item
* @return {*}
* @time complexity: O(1)
* @space complexity: O(1)
*/
pop() {
if (this.isEmpty()) {
return undefined;
}
count.set(this, count.get(this) - 1);
const item = items.get(this)[count.get(this)];
delete items.get(this)[count.get(this)];
return item;
}
/**
* Get the most recently added item
* @return {*}
* @time complexity: O(1)
* @space complexity: O(1)
*/
peek() {
if (this.isEmpty()) {
return undefined;
}
return items.get(this)[count.get(this) - 1];
}
/**
* Check whether it contains no items
* @return {boolean}
* @time complexity: O(1)
* @space complexity: O(1)
*/
isEmpty() {
return count.get(this) === 0;
}
/**
* Get the total number of items
* @return {number}
* @time complexity: O(1)
* @space complexity: O(1)
*/
size() {
return count.get(this);
}
/**
* Remove all items
* @time complexity: O(1)
* @space complexity: O(1)
*/
clear() {
items.set(this, {});
count.set(this, 0);
}
} Test with Jest
describe('Stack Data Structure', () => {
let stack;
beforeEach(() => {
stack = new Stack();
});
describe('push', () => {
test('should be a function', () => {
expect(typeof stack.push).toEqual('function');
});
});
describe('pop', () => {
test('should be a function', () => {
expect(typeof stack.pop).toEqual('function');
});
});
describe('push and pop', () => {
test('should add an item and remove an item', () => {
stack.push(1);
stack.pop();
expect(stack.size()).toEqual(0);
});
test('should implement FILO (First In Last Out) principle', () => {
stack.push(1);
stack.push(2);
stack.push(3);
expect(stack.pop()).toEqual(3);
expect(stack.pop()).toEqual(2);
expect(stack.pop()).toEqual(1);
});
});
describe('size', () => {
test('should be a function', () => {
expect(typeof stack.size).toEqual('function');
});
test('should return 0 at the beginning', () => {
expect(stack.size()).toEqual(0);
});
test('should return the total number of items', () => {
stack.push(1);
expect(stack.size()).toEqual(1);
stack.push(2);
expect(stack.size()).toEqual(2);
stack.push(3);
stack.push(4);
stack.push(5);
expect(stack.size()).toEqual(5);
});
});
describe('isEmpty', () => {
test('should be a function', () => {
expect(typeof stack.isEmpty).toEqual('function');
});
test('should return true if there is no item', () => {
expect(stack.isEmpty()).toEqual(true);
});
test('should return false if there is at least one item', () => {
stack.push(1);
expect(stack.isEmpty()).toEqual(false);
});
});
describe('peek', () => {
test('should be a function', () => {
expect(typeof stack.peek).toEqual('function');
});
test('should return undefined if there is no item', () => {
expect(stack.peek()).toEqual(undefined);
});
test('should return the last item', () => {
stack.push(1);
stack.push(2);
expect(stack.peek()).toEqual(2);
});
test('should not delete the item', () => {
stack.push(1);
stack.push(2);
stack.push(3);
expect(stack.peek()).toEqual(3);
expect(stack.peek()).toEqual(3);
});
});
describe('clear', () => {
test('should be a function', () => {
expect(typeof stack.clear).toEqual('function');
});
test('should delete all the items', () => {
stack.push(1);
stack.push(2);
stack.clear();
expect(stack.size()).toEqual(0);
});
});
});
Stack Data Structure
push
✓ should be a function (2 ms)
pop
✓ should be a function (1 ms)
push and pop
✓ should add an item and remove an item
✓ should implement FILO (First In Last Out) principle
size
✓ should be a function
✓ should return 0 at the beginning (1 ms)
✓ should return the total number of items
isEmpty
✓ should be a function
✓ should return true if there is no item
✓ should return false if there is at least one item (1 ms)
peek
✓ should be a function
✓ should return undefined if there is no item
✓ should return the last item
✓ should not delete the item
clear
✓ should be a function (1 ms)
✓ should delete all the items
