DEV Community

loading...

Stack and Queues Implementations in JavaScript and Python

edwardcashmere profile image Edwin ・4 min read

What is a stack?

A stack is a linear data structure that follows a particular order in which the operations are performed

An example is the call stack in JavaScript, it is what a program uses to keep track of method calls. It works based on the LIFO principle i.e., last-in-first-out. This means whatever item or function that is called last is executed first. In this article, we will use SLL(singly linked list) to build a call stack. Look up how the call stack handles recursion here.

There two different approaches we can implement the call stack but one is optimized and will take less time. The first approach is adding a node at the end and removing it from the end also. Here we have adhered to the LIFO principle but when removing we have to loop to the 2nd last node before we remove the last node. if we assume our list is big enough this approach is time expensive O(n). A better approach would be to use a doubly-linked list to avoid using the loop or our 2nd approach.

In this 2nd approach, we will be adding at the beginning and removing from the beginning also our time complexity will always be O(1). Hence this is the approach we will use.

What is a Queue?

A queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.
Think about a line at the bank, how you want the system to work is by serving the person who came first always.

Just as the call stack we can implement a queue taking two approaches. Although both approaches will work, only one approach works optimally. That is by adding a node at the end of the list and removing it at the beginning. Try and think about the other approach you can use, and why I have opted not to use it?.

I have implemented both stack and queue using an SLL but you can also use the DLL or even arrays in javascript so long as you adhere to the LIFO and FIFO principles.
Call stack

Stack in JavaScript:

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}
class Stack{
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
 push (val){
        let newNode = new Node(val);
        if(!this.first){
            this.first= newNode;
            this.last = newNode;
        }else{
            newNode.next = this.first;
            this.first = newNode;
        }
        this.size++;
        return this;
    }
    pop(){
        if(!this.first)return undefined;
        let temp = this.first;
        this.first = this.first.next;
        this.size--;
        if(this.size ===0){
            this.last = null;
        }
        return temp;
    }

}

let stack  = new Stack();
stack.push(19);
stack.push(20);
stack.push(21);
stack.push(22);
stack.push(23);
stack.push(24);
stack.push(25);


Enter fullscreen mode Exit fullscreen mode

In python:

class Node:
    def __init__(self,val):
        self.val = val
        self.next = None


class Stack:
    def __init__(self):
        self.first = None
        self.last =None
        self.size =0

    def push(self,val): 
        newNode = Node(val)
        if self.first == None:
            self.first= newNode
            self.last = newNode
        else:
            newNode.next = self.first
            self.first = newNode
        self.size+=1
        return self


    def pop(self):
        if self.first == None: return 
        temp = self.first
        self.first = self.first.next
        self.size-=1
        if(self.size == 0):
            self.last = None
        return temp


Enter fullscreen mode Exit fullscreen mode

Queue in JavaScript:

class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}
// FIFO First in First out
class Queue{
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0
    }
    //  add at the beginning and remove at the beginning
    enqueue(val){
        let newNode = new Node(val);
        if(!this.first){
            this.first= newNode;
            this.last = newNode;
        }else{
            this.last.next = newNode;
            this.last = newNode;
        }
        this.size++
        return this
    }

    dequeue(){
        if(!this.first) return undefined
        let temp = this.first
        this.first = this.first.next
        this.size--
        if(this.size === 0){
            this.last = null
        }
        return temp


    }
}

let queue = new Queue()
queue.enqueue(19)
queue.enqueue(20)
queue.enqueue(21)
queue.enqueue(22)
queue.enqueue(23)
queue.enqueue(24)
queue.enqueue(25)
queue.enqueue(26)
Enter fullscreen mode Exit fullscreen mode

In python:


class Node:
    def __init__(self,val):
        self.val = val
        self.next = None


class Queue:
    def __init__(self):
        self.first = None
        self.last =None
        self.size =0

    def enqueue(self,val):   
        newNode =  Node(val)
        if self.first == None:
            self.first = newNode
            self.last = newNode
            self.size+=1
            return self
        self.last.next= newNode
        self.last = newNode
        self.size+=1
        return self


    def dequeue(self):
        if self.first == None: return 
        temp = self.first
        self.first = self.first.next
        self.size-=1
        if(self.size == 0):
            self.last = None
        return temp


Enter fullscreen mode Exit fullscreen mode

Conclusion
The implementations of Stack and Queue is simple as long as you adhere to its LIFO(Last-In-First-Out) and FIFO(First-In-First-Out) Principles, you can use arrays in JavaScript or Lists in Python, SLL, DLL the main objective however will be keeping the time complexity at O(1) for optimum performance.

Discussion (0)

pic
Editor guide