In this post we saw how we can insert an element in an array at an specified index, we saw too how we could remove one or many items from an array from an also specified index.

An interesting thing about that is that we can use arrays, and the functions that we have already saw to quickly implement some of the more used data structures in programming: stacks and queues.

Stack implementation in JavaScript

An Stack is a linear data structure in which elements are added and removed following the LIFO order: last in first out. In other words: the last element added to the  stack will be the first one removed. Imagine for example a set of books on a desktop each piling up on the other: usually if you want to add a book to the existing stack on the desktop you will add it to the top. Also when you want to get a book from the stack you will start from the top working your way down till you reach the book you need.

As you surely remember we can add an element to the end of an array by using the push function, and remove the element at the end of an array by using the pop function. So by using arrays and the pop and push functions we can implement an Stack just like this:

class Stack {
    constructor() {
        this.stack = [];
    }

    push(item) {
        this.stack.push(item);
    }

    pop()
    {
        if (this.stack.length === 0)
        {
            return null;
        }
        return this.stack.pop();
    }

    peek() {
        return this.stack[this.stack.length-1];
    }

    isEmpty() {
        if (this.stack.length === 0){
            return true;
        }
        else {
            return false;
        }
    }

    displayStack() {
        console.log(this.stack.join());
    }
}

The above implementation provides an add and remove functions to add and remove items to the stack, and also functions to check if the stack is empty – isEmpty -, and log to console the current content of the stack.

We could use the above implementation like this:

//create stack
var myStack = new Stack();
console.log(myStack.isEmpty());
// Add to stack: book, notepad, paper
myStack.push("book");
myStack.push("notepad");
myStack.push("paper");
myStack.displayStack();
// Top item in the stack, paper, is removed
console.log(myStack.pop());
myStack.displayStack();
//Once again remove top item
console.log(myStack.pop());
//Look at element on the top of the Stack.
//Stack remains unchanged
myStack.peek();
myStack.displayStack();
//Stack is not empty
console.log(myStack.isEmpty());

As you can see Arrays in JavaScript have already the functions that allow them to work like a Stack, so you could also use them directly without implementing a wrapper Stack class.

Queue implementation in JavaScript

Queues are also linear structures were operations are performed using the FIFO order: First in first out. Queues mimic the behaviour of queues in real life, hence the name. Imagine the usual queue to buy tickets for an event, the first customers to get on the queue will also be the first one to buy their ticket, while the last person to join to a queue has to wait till all the other people before them are done.

Using arrays and the shift and push functions we can implement an Queue:

class Queue {
    constructor() {
        this.queue = [];
    }

    enqueue(item) {
        this.queue.push(item);
    }

    dequeue()
    {
        if (this.queue.length === 0)
        {
            return null;
        }
        return this.queue.shift();
    }

    isEmpty() {
        if (this.queue.length === 0){
            return true;
        }
        else {
            return false;
        }
    }

    displayQueue() {
        console.log(this.queue.join());
    }
}

Usage sample:

//create queue
var myQueue = new Queue();
// check is empty: return true
console.log(myQueue.isEmpty());
// Add Peter,Bob and James in this order to the queue
myQueue.enqueue("Peter");
myQueue.enqueue("Bob");
myQueue.enqueue("James");
//print queue:Peter,Bob,James
myQueue.displayQueue();
//First item in Queue, Peter, dequeued
console.log(myQueue.dequeue());
//Bob is dequeued
console.log(myQueue.dequeue());
//Only James remains in the non-empty queue
myQueue.displayQueue();
console.log(myQueue.isEmpty());

For further reading regarding stack implementations you can check this post about how to implement a stack in C#, and this other about .Net IEnumerables/Enumerators.

Advertisements