Stack and Que
Definition of Stack
A collection of data that operates under LIFO principles.
- LIFO: first in first out
Real World Cases
- managing function invocations
- undo/redo
- routing, history objects in browsers
A stack at it’s core is an abstract concept and there is some fluidity with the properties of the definition. Different languages have varying degrees of rigor and patterns `with how function is implemented.
JavaScript doesn't have a default stack data type but the array object using .push() and .pop() is functionality a stack.
💡 From a performance standpoint a JS array is not the most lean implementations of a stack as functionality associated with index's is not necessary within the rigorous definition of a stack.
Object Definition
class Node {constructor(value) {this.value = valuethis.next = null}}class Stack {constructor() {this.first = nullthis.last = nullthis.size = 0}insert() {let newNode = new Node(val)if (!this.first) {this.first = newNodethis.last = newNode} else {let tmp = this.firstthis.first = newNodethis.first.next = tmp}return ++this.size}remove() {if (!this.first) {return null}let tmp = this.firstif ((this.first = this.last)) {this.last = null}this.first = this.first.nextthis.size--return tmp.value}}
Functional Definition
const node = (value) => {return {Node: value,next: null,}}const stack = (size, insert, remove) => {}
Stack data structure built with linked lists
Queu
- FIFO