DEV Community

Cover image for Implement a Stack with TypeScript
Mark A
Mark A

Posted on

Implement a Stack with TypeScript

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
Enter fullscreen mode Exit fullscreen mode

Then, make a folder called typescript_practice

  mkdir typescript_practice && cd typescript_practice
Enter fullscreen mode Exit fullscreen mode

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
  }
}
Enter fullscreen mode Exit fullscreen mode

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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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>
Enter fullscreen mode Exit fullscreen mode
const nodeToBeRemove = this.top as StackNode<T>
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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

nodemon main.ts
Enter fullscreen mode Exit fullscreen mode

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 πŸ˜ƒ!.

Discussion (5)

Collapse
yendenikhil profile image
Nik

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?

Collapse
macmacky profile image
Mark A Author

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 }.
Collapse
yendenikhil profile image
Nik • Edited

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.

Thread Thread
macmacky profile image
Mark A Author

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
  }
Collapse
tomaszs2 profile image
Tomasz Smykowski

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-...