Stack and Queues Implementations in JavaScript and Python

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); 

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 

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) 

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 

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.