loading...
Cover image for Implement a Stack with TypeScript

Implement a Stack with TypeScript

macmacky profile image Mark A ・4 min read

Hi Guys Good Day!

TypeScript is still booming, take a look at this survey StackOverflow. A lot of people are using it right now and will so for the next couple of years because of the rise of Deno, a secure runtime for JavaScript and TypeScript.

But, first let's make a Stack with TypeScript. Stack is a LIFO (Last In First Out) data structure. Our stack will have two methods push and pop. When we use the push method
that item will be a new item at the top of the stack and when we use the pop method that newly push item in the stack will be removed. We could easily make a Stack with TypeScript by using arrays but we're not gonna do that. I highly recommend using VSCode as your code editor because it has great support for TypeScript out of the box.

First, install Nodejs.

After installing Nodejs install TypeScript and Nodemon using this command.

 npm i -g typescript nodemon

Then, make a folder called typescript_practice

  mkdir typescript_practice && cd typescript_practice

After that, in our main.js inside the typescript_practice folder. I'm gonna explain this code later.

main.js

interface StackNode<T> {
  value: T | null
  next: StackNode<T> | null
}

class StackNode<T> implements StackNode<T> {
  constructor(val: T) {
    this.value = val
    this.next = null
  }
}

interface Stack<T> {
  size: number
  top: StackNode<T> | null
  bottom: StackNode<T> | null
  push(val: T): number
  pop(): StackNode<T> | null
}



class Stack<T = string> implements Stack<T> {
  constructor() {
    this.size = 0
    this.top = null
    this.bottom = null
  }

  push(val: T) {
    const node = new StackNode(val)
    if (this.size === 0) {
      this.top = node
      this.bottom = node
    } else {
      const currentTop = this.top
      this.top = node
      this.top.next = currentTop
    }

    this.size += 1
    return this.size
  }


  pop(): StackNode<T> | null {
    if (this.size > 0) {
      const nodeToBeRemove = this.top as StackNode<T>
      this.top = nodeToBeRemove.next
      this.size -= 1
      nodeToBeRemove.next = null
      return nodeToBeRemove
    }
    return null
  }
}

So, I'm gonna explain this part first and I believe you will understand most of our code eventually.

interface StackNode<T> {
  value: T | null
  next: StackNode<T> | null
}

class StackNode<T> implements StackNode<T> {
  constructor(val: T) {
    this.value = val;
    this.next = null;
  }
}

In this part, obviously we're making an interface and a class. The class implements the interface so our class StackNode must have these two properties value and next. Basically an interface is a contract between the class and the interface saying that our class should have the shape of our interface unless if you make a property optional in the interface using the ? operator. Also, we're using a Generic here <T> to make this class reusable and can work with multiple types. The T holds the type information, not the value but the type of that value we're gonna use in this class.

 const node = new StackNode(1)

For example, in the code above, we're passing a value of 1 when creating an instance of the class. Since 1 is type of number then all of those T above in the interface and class will hold a value of number. What I mean about value here is the type. and lastly in our interface if you're wondering what does this | mean in the T | null.It means a Union Type,so the property value can either have a type of T or it can have a type of null.

Ok, I believe you understand most of our code now, so I'm not gonna explain the class Stack and interface implementation, but I'm gonna explain these two parts.

class Stack<T = string>
const nodeToBeRemove = this.top as StackNode<T>

In the first part, what we are doing is that we're giving a default value for the Generic type and that value is string, We can give a default value for a Generic as long it is valid.

In the second part, what we are doing is Type Assertion. Basically, what Type Assertion is that we're telling the TypeScript compiler that we know the type of this value and we set that value's type to that type. In this example, the this.top property can have two types a null or a StackNode but inside the condition we know that the stack is not empty and the top has still value, so this.top is not null. This is why we use the as operator to tell the TypeScript compiler that the type of this.top is a
StackNode. If you remove this part as StackNode<T> some of you will get this error Object is possibly 'null'.

Add this code below.

const stack = new Stack<string>()

stack.push("a")
stack.push("b")
stack.push("c")

const popData = stack.pop()

console.log(popData)

console.log(stack)

Then, run this command to see the output of the console.log's

nodemon main.ts

You can also add the peek and isEmpty methods in our stack.

Thanks guys for reading this post.

Have a Nice Day and Stay Safe πŸ˜ƒ!.

Posted on by:

macmacky profile

Mark A

@macmacky

a Full-Stack developer who likes reading Tom Clancy's books and loves talking with dogs.

Discussion

pic
Editor guide
 

Hey Mark, very nice article. You demonstrate object hierarchy and genetics nicely. Just one question about the design, Why does the pop method on Stack<T> returns StackNode<T> instead of T. I push: string I should be pop: string. I push number I should pop number. What do you think?

 

Hi Nik, Good question. Yes, that's right you're pushing a value with type string or number but as you can see at right here.

push(val: T) {
    const node = new StackNode(val)
    // logic
}

the variable node holds a value object. If we have an example that looks like this.

const stack = new Stack()
stack.push('1')

that node variable will hold a value

StackNode { value: '1', next: null }

the value you're talking about is inside the object. We're using an object so that we can easily get the next value in the stack. If we use the pop method.

const popData  = stack.pop()

console.log(popData) 
// we will get the object StackNode { value: '1', next: null }.
 

I agree. Let me rephrase. The user of stack should be only aware of stack and the valueType it pushes or pops. It adds no value (in my opinion ) to give back stacknode of popped value.

So, it makes sense to use stacknode internally in stack to keep track of next value but don’t expose stacknode to the user of stack.

Awh ok. Sorry for the late reply. I think I understand what you're talking about. You want just the value correct not the object?. If that's what you want, you need two change two parts.

Stack Interface

interface Stack<T> {
  size: number
  top: StackNode<T> | null
  bottom: StackNode<T> | null
  push(val: T): number
  pop(): T | null
}

Stack pop implementation

pop(): T | null {
    if (this.size > 0) {
      const nodeToBeRemove = this.top as StackNode<T>
      this.top = nodeToBeRemove.next
      this.size -= 1
      nodeToBeRemove.next = null
      return nodeToBeRemove.value
    }
    return null
  }
 

Hello, recently I have published card decks for young people to learn Javascript and Python. Would you be able to share the information? summonthejson.com/products/summon-...