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.
Top comments (0)