Stack's Implementation With Real World Example

Introduction

What comes to your mind when you hear a word stack?

Stack of books? yes, Pringles? yes.

What makes it special is the order in which we eat pringle. We always start with a pringle on the top, and one by one we start consuming more till we reach the last one at the bottom of the box.

This order is called LIFO. Last In First Out.

The question is, where in programming do we follow this order, LIFO. Answer is every damn time.

Every time you code, you are following LIFO to maintain the order of Parentheses. Take this code for example.

class parentheses
{
    constructor(elements = [])
}

Listing 1: Sample code

Following is the same code only with parentheses.

{
  (
    []
  )
}

Listing 2: Parentheses

Look closely, In listing 2, there is a pattern. First opening curly brace "{" is the last to be closed "}". Second round parenthesis "(" only second last to be closed ")" and same goes for square bracket "[ ]".

Another real world application of stack would be Undo and Redo features.

Stack has a list of operations that we need to build.

Push: Adds an element at the top of the stack.
Pop: Removes the element from the top of the stack and returns it.
Peek: Shows the top element from the stack.
Size: Returns the size of the stack.
IsEmpty: Returns true if stack is empty else returns false.
Print stack: Bonus operation.

The Implementation

Stacks can be implemented using Array and LinkedList both,

The elements in an array are stored in a linear fashion next to each other which offers cache locality, due to which it makes them faster while accessing its items. But there is a drawback too, Arrays are going to double their size as soon as it exhausts their assigned limit.
With Linkedlist we can add elements dynamically, and size will increase dynamically while the drawback of using linkedlist is it has items linearly stored yes but nodes are scattered across the memory and they are linked with pointers so it has extra overhead of pointers to carry.

Common Data Structure Operations

Stacks only have one entry point and one exit point. So all that matters is insertion and deletion complexity.

In Array, we need to insert or delete an element at the top of the array which means at the last position, In linkedlist we only have to deal with the head node.

Array Vs LinkedList
Data Structures	Insert element at last index / Head Node	Delete element from the last index / Head Node		Space Complexity
Stack operations	Push/Enqueue	Pop / Dequeue	Peek
Array	O(1)	O(1)	O(1)	O(n)
LinkedList	O(1)	O(1)	O(1)	O(n)

Approach 1: Implement a Stack using LinkList.

First we obviously need a Node class.

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

Listing 3: class Node

Next, we need a stack class and stack has 3 properties.

Top: the top node of a stack
Botton: the bottom or last node of a stack
Length: length of a stack

class Stack{
    constructor(){
        this.top = null,
        this.bottom = null,
        this.length = 0
    }
}

Listing 4: class stack

Push operation

Let's start with the Push method, what we need to do is, we need to add a new head to the linkedlist. If you want to learn how to add a new head in detail then visit this article.

Following are the series of steps we are going to perform in each iteration.

Iteration 1:
Length = 1 
Top = Bottom = 1

Iteration 2:
CurrentTop: 1
NewTop : 2
NewTop.next  : 1
Length = 2
List :  2 -> 1

Iteration 3:
CurrentTop : 2
NewTop : 3
NewTop.next  : 2
Length = 3
List :  3 -> 2 -> 1

Code snippet to insert a new head node,

push(value) {
    var newTopNode = new Node(value);
    if (this.length === 0) {
        this.top = newTopNode;
        this.bottom = newTopNode;
    } else {
        const tempNode = this.top;
        this.top = newTopNode;
        this.top.next = tempNode;
    }
    this.length++;
    return this;
}

Listing 5: Push method

Pop operation

We need to pop the top element from the stack and in this scenario, we need to remove the head element.

Let's remove 3 and 2 from the stack.

Iteration 1: Current List: 3 -> 2 -> 1
CurrentTop : CurrentTop.next
NewTop: 2
Length = 2

Iteration 2: Current List: 2 -> 1
CurrentTop : CurrentTop.next
NewTop: 1
Length = 1

Code snippet to remove a head node.

    pop(){
        if(!this.top){            
            return null;
        }
        if(this.top === this.bottom){
            this.bottom = null;
        }
        this.top = this.top.next;
        this.length--;
        return this;
    }

Listing 6: Pop method

Peek, IsEmpty, Size operations

peek() {
    return this.top;
}
isEmpty() {
    return this.length === 0;
}
size() {
    return this.length;
}

Listing 7: Peek, IsEmpty, Size methods

Bonus method for you guys, Let's print this linkedlist in pretty print.

printList() {
    //Creates an empty array.
    let printArrayList = [];
    //Pointer which points to the head node
    let currentNode = this.top;
    //Start iterating from the first node till you reach the last node
    while (currentNode !== null) {
        //Add every node's value to the array
        printArrayList.push(currentNode.value);
        //Point pointer to the next node
        currentNode = currentNode.next;
    }
    //Return the array
    return printArrayList.join(' -> ');
}

Listing 8: PrintList method

Listing 9 is the entire code snippet for stack.

class Node {
    constructor(value) {
        this.value = value,
            this.next = null
    }
}
class Stack {
    constructor() {
        this.top = null,
            this.bottom = null,
            this.length = 0
    }
    push(value) {
        var newTopNode = new Node(value);
        if (this.length === 0) {
            this.top = newTopNode;
            this.bottom = newTopNode;
        } else {
            const tempNode = this.top;
            this.top = newTopNode;
            this.top.next = tempNode;
        }
        this.length++;
        return this;
    }
    pop() {
        if (!this.top) {
            return null;
        }
        if (this.top === this.bottom) {
            this.bottom = null;
        }
        this.top = this.top.next;
        this.length--;
        return this;
    }
    peek() {
        return this.top;
    }
    isEmpty() {
        return this.length === 0;
    }
    size() {
        return this.length;
    }
    printList() {
        //Creates an empty array.
        let printArrayList = [];
        //Pointer which points to the head node
        let currentNode = this.top;
        //Start iterating from the first node till you reach the last node
        while (currentNode !== null) {
            //Add every node's value to the array
            printArrayList.push(currentNode.value);
            //Point pointer to the next node
            currentNode = currentNode.next;
        }
        //Return the array
        return printArrayList.join(' -> ');
    }
}
var books = new Stack();
books.push(10);
console.log(books.printList());
books.push(20);
console.log(books.printList());
books.push(30);
console.log(books.printList());
books.pop();
console.log(books.printList());
books.pop();
console.log(books.printList());

Listing 9: stack

Run the code and see if all functions are working properly.

Figure 1: Output of listing 9

Approach 2: Implement a Stack using Array.

This code is easy on the eyes because there is hardly anything to code. We are going to leverage most of the functions of array and that's it.

class Stack {
    constructor() {
        this.elements = []
    }
    push(value) {
        this.elements.push(value);
    }
    pop() {
        this.elements.pop();
        return this;
    }
    peek() {
        return this.elements[this.elements.length - 1];
    }
}

Listing 10: Stack with array

Summary

In this article, we learned what stack is, where it's been used, How to implement its various operations with linkedlist and array. In the next article, we will understand how to code to validate parentheses in a program.