My point of view and usage of Stacks | maikomiyazaki

Course Recap(2): My point of view and usage of Stacks/Queues

21/12/2019

JavaScript

In the previous article, I wrote about implementing linked lists on my Chrome Extension project. I ended up not using them on the project, but I could understand why it will be useful for certain situations.

https://miyazakimaiko.com/course-recap-1-introduction-and-my-point-of-view-for-linked-lists/

So as I wrote in the previous article, I’m still looking for a data structure that is better than O(n) time complexity, for editing/deleting data.

Currently, I’m storing the main data of my project as objects like this:

// Result of console.log(main-data)

0: {category: "cat1", id: "4", meaning: "information of the vocabulary.", tag: ["tag1", "tag2"], word: "Example Vocab 1"}
1: {category: "cat3", id: "3", meaning: "Hello World", tag: ["tag1", "tag4"], word: "Example Vocab 2"}
2: {category: "cat2", id: "2", meaning: "This is new vocabulary.", tag: ["tag4"], word: "Example"}
3: {category: "cat4", id: "1", meaning: "You can write anything.", tag: ["tag2", "tag4", "tag5"], word: "Sample"}

The data structure that I learned after the linked list was stacks and queues, so in this article, I’m going to think about implementing it.

Is stack the best choice?

As we can call stacks ‘Last in first out’ data structure, the last element that added to the stack will be removed first.

It is just like a stack of anything in real life, like a pile of dirty dishes in the sink. You put another dish to be washed on top of the pile, and once you decide to wash them, you wouldn’t pick one up from the bottom of the pile — you will pick the one you just put it last. It’s the same in stacks for the data structure.

To implement it as a singly linked list, JavaScript code will be like this:

class Node {
    constructor(value) {
        this.val = value;
        this.next = null;
    }
}

class Stack {
    constructor() {
        this.first = null;
        this.last = null;
        this.size = 0;
    }
}

We are going to push a node to the beginning of the list instead of the end. So when you pop, it’ll be much easier. So we can write code like this:

push(val) {
    const newNode = new Node(val);
    if(this.size === 0) {
        this.first = newNode;
        this.last = this.first;
    } else {
        newNode.next = this.first;
        this.first = newNode;
    }
    return this.size++;
}
pop() {
    const remove = this.first;
    if(this.size === 1) {
        this.first = null;
        this.last = null;
        this.size = 0;
    } else {
        const newFirst = this.first.next;
        remove.next = null;
        this.first = newFirst;
    }
    this.size--;
    return remove.val;
}

This structure works best when you want to especially record the current action, and want to make the action to be able to go back/forth. Your text editor can be a good example of this — you can Undo and Redo, but it doesn’t need to be able to pick up one certain point of the previous action.

It is not the best way for my project to store the main data because I want the data to be faster than O(n) when an element is removed/edited not only at the end of the list but anywhere.

How about queues?

I have already the answer to this question. It is not suitable for the main data of my project, because the structure is almost the same as the stack which is linked list or array.

The difference from the stack is that the first element that was added to the queue will be removed first — which we can call it ‘First in First out’ structure. 

To implement it in a singly linked list, JavaScript code will be like this:

class Node {
    constructor(value) {
        this.val = value;
        this.next = null;
    }
}

class Queue {
    constructor() {
        this.first = null;
        this.last = null;
        this.size = 0;
    }
}

Initialization is the same as a stack. To make it easier when you remove the first node that you added, we are going to add a node at the end, and remove a node from the beginning of the queue.

enqueue(val) {
    const newNode = new Node(val);
    if(!this.first) {
        this.first = newNode;
        this.last = this.first;
    } else {
        this.last.next = newNode;
        this.last = newNode;    
    }
    this.size++
    return this;
}
dequeue() {
    const remove = this.first;
    if(this.size === 1) {
        this.first = null;
        this.last = null;
    } else {
        this.first = remove.next;
        remove.next = null;
    }
    this.size--;
    return remove.val;
}

Although a queue might not be a suitable data structure for my project, it is commonly used for many occasions. For instance, when we are printing a document with a printer, and if we continuously add more documents to print out, the printer will process the data which was added first. 

Therefore queues are more suitable for the situation where the order is more important for the whole process.

Conclusion

Stacks and queues are useful for data that you want to keep them ordered in a certain duration of the process, and also no need to keep them when it’s done. As I am in search of data structure that would be suitable for storing data, stacks and queues are not the best choices this time, but I’m certain that I would be using them very often in the future.

Next article, I’m going to write about binary search trees.