Stack — Typescript

What is it?

A stack is just one of infinitely possible data structures you can make with a programming language. It’s a popular one because it is simple and elegant and it does a couple of things better than most other structures.

In computer programming we have to define everything. In some ways, being a programmer is like re-inventing the wheel a thousand times.

In many languages we even have to tell the computer how to store data, and in doing so we can build infrastructure around the data to make it behave in certain ways.

This is where the initial idea of data structures came to life.

How does it work?

A stack is a data structure that acts like a latex test tube full of Tums. The test tube only takes up as much space as the number of Tums inside of it.

Data can only enter and leave the stack through a singular entry point. the work required to insert an item into the stack or take the most recent item off the top of the stack is minimal and does not depend on how many items are in it.

When would we need it?

Stacks are incredibly useful in engineering and if you start a career as a programmer you will frequently find opportunities to use it.

For example, lets say a hospital has a big database of unorganized patient records, and they want you to categorize patients based on illnesses, but their individual data needs to be stored just in case, because if the category of patients are determined to be at risk for covid-19, everybody in that category will need to be individually inspected.

However, if the category (for example, patients with leukemia) is deemed a low risk category then no further task needs to be done.

This would be a good opportunity to use a bunch of stacks to keep track of each category, since inserting the patient’s record into a categorical stack has a low processing cost. And, if the category is deemed low-risk we can still track basic information like how many patients that category contains with minimal processing power.

So let’s begin.

Here’s a theoretical diagram :

Try to imagine the head as the entry point of the test tube.

In order to make a stack programmatically we just need to make everything in this diagram using whatever language your prefer. I’m using typescript.

This is the entire structure :

class Stack{
head?: StackNode
constructor(){
this.head
}
insert(value:any){
if(this.head){
let newNode = new StackNode(value)
newNode.next = this.head
this.head = newNode
} else {
let newNode = new StackNode(value)
this.head = newNode
}
}
pop(){
if(this.head){
let output = this.head
this.head = this.head.next
return output.value
} else {
console.log("the stack is empty")
}
}
}
class StackNode {
next?:StackNode
value:any
constructor(value:any){
this.value = value
this.next
}
}

As you can see, this can be created with only ~30 lines of code.

Let’s go through these methods to get a thorough grasp of what is going on here. In essence, we’re just defining every little part of our diagram.

class Stack{
head?: StackNode
constructor(){
this.head
}

Here, I am telling the computer there is going to be a stack item in memory, and it’s going to have an item defined as “head” that will always either be undefined or will look like the StackNode item.

The constructor method is just saying, the head’s default value is going to be undefined.

insert(value:any){
if(this.head){
let newNode = new StackNode(value)
newNode.next = this.head
this.head = newNode
} else {
let newNode = new StackNode(value)
this.head = newNode
}
}

This method is defining how an insert will effect our Stack item. First, if the head is undefined then the stack is empty. So I’m saying if the stack is empty, the new insert will become the head.

Otherwise, the new insert will become the head and the new head will reference the old head with its next property.

The Pop method is doing nearly the same thing, except the next StackNode in line becomes the new head and the old head is being removed from reference. (where it will later become garbage collected in most modern languages)

The last part of this puzzle is to define what our StackNodes look like.

class StackNode {
next?:StackNode
value:any
constructor(value:any){
this.value = value
this.next
}
}

In this, I am defining the StackNode as some item in memory that will contain a next property and a value property. The next property references the next StackNode in the Stack item. The value property references whatever important data I want to store in that Node.

The real beauty in working with stacks is that inserting and popping operations are an O(1) time expenditure. If you want to discard the whole stack it’s an O(1) operation and if you want to see everything inside it’s O(n)

I have found them to be very useful on many occasions in my career so far.

That’s all folks.