Stack and Queue in Javascript: Use Array or LinkedList?

Introduction:

Stack and Queue are collection of datas, similar to arrays or lists, but follow different principles in design. Stack and Queue mainly focus on adding and removing one item at a time to a list. They both are important data structures and have different uses in our applications.

Stack:

Stack - is a concept that creates a collection of data uses
First-in-last-out or last-in-first-out principle. Which means that items that first added to the list will be the last one to be removed.

Let's say I use array.push() 10 times to add 10 items to a new array, when I do array.pop(), the first items to pop is the last item I pushed in. This concept is very useful to implement something like undo/redo functions. when we do an undo, we undo the last action. Website histories is also a good use of a Stack because the last page we visit displays at top of the list.

The most basic Stack should have a method to add and a method to remove items from a list that follows the First-in-last-out principle. In Javascript we can use push to add an item to the end of the list, and pop to remove the item from the end of the list. Another way to do it is to use unshift/shift to add/remove from the beginning of the list.

Keep in mind that when we remove/add anything at the beginning of an array, all elements in it need to re-index. This does not happen when we add/remove items at the end of an array. So push/pop will outperform unshift/shift for Stack implementation. A Stack using array would look like this:

class Stack{
    constructor(){
        stackArray =[]
    }

    push(element){
        this.stackArray.push(element)
    }

    pop(){
        if(this.stackArray.length === 0){
            return "underFlow"
        }
        this.stackArray.pop()
    }
}

In Javascript, as array's length grows, the array doubles its size under hood, automatically and dynamically. This can waste a lot of space in memory for a Stack, because we only add/remove one item at a time with Stack. Due to this, a SinglyLinkedList is more ideal to create a Stack. Optimized for space complexity and Unshift/Shift methods are constant time O(1) (same as push/pop in array) in a SinglyLinkedList.

Queue:

Queue - Unlike Stack, Queue uses a concept of first-in-first-out or last-in-last-out principles. The first item added to a list is the first item to be removed when requests. Similar to how printers work, the first request sent to it is the first page to be printed. Queue is useful for anything like telephone wait line, restaurant wait line etc...

In Javascript, one way to implement a Queue using array is to use push() to add items, and shift() to remove item, as this will satisfy the concept of first-in-first-out principle. However, because shift() remove the first item in an array and all indexes need to shift over, this compromises the time complexity, achieving only O(n) for removing.

Fortunately, we can use a singlyLinkedList again to create a Queue. Both push() and shift() methods are constant time O(1) in singlyLinkedList. This allows our Queue to have a faster performance for adding/removing items, as well as a dynamic length list to save space in memory.