Stacks - 401-advanced-javascript-jonnygraybill/data-structures-and-algorithms GitHub Wiki

Stack

• https://www.geeksforgeeks.org/implementation-stack-javascript/

What is it?

• Stack is a very useful data structure and has a wide range of application. Stack is a linear data structure in which addition or removal of element follows a particular order i.e. LIFO(Last in First Out).

Code

• Skeleton

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

// Stack class 
class Stack { 
  
    // Array is used to implement stack 
    constructor() 
    { 
        this.items = []; 
    } 
  
    // Functions to be implemented 
    // push(item) 
    // pop() 
    // peek() 
    // isEmpty() 
    // printStack() 
} 

• Methods

// push function 
push(element) 
{ 
    // push element into the items 
    this.items.push(element); 
} 


pop() 
{ 
    // return top most element in the stack 
    // and removes it from the stack 
    // Underflow if stack is empty 
    if (this.items.length == 0) 
        return "Underflow"; 
    return this.items.pop(); 
} 


peek() 
{ 
    // return the top most element from the stack 
    // but does'nt delete it. 
    return this.items[this.items.length - 1]; 
} 


isEmpty() 
{ 
    // return true if stack is empty 
    return this.items.length == 0; 
} 


// printStack function 
printStack() 
{ 
    var str = ""; 
    for (var i = 0; i < this.items.length; i++) 
        str += this.items[i] + " "; 
    return str; 
}

Example

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

class Stack {
    constructor() {
        this.root = null
        this.size = 0
    }
    
    push(value) {
        let node = new Node(value);
		node.next = this.root;
    	this.root = node;
    }
    
    pop() {
        if (!this.root) {
            return null;
        }
        let popped = this.root.value;
        this.root = this.root.next;
        return popped;
    }
    
    peek() {
        if (!this.root) {
            return null;
        }
        let peeked = this.root.value;
        return peeked;
    }
    
    isEmpty() {
        if (!this.root) {
            return true;
        }
    }
    
    clear() {
        this.root = null;
        this.size = 0;
    }

    // methods to implement:

    // push(value)
    // pop()
    // peek()
    // isEmpty()
    // clear()
    // print()
}