Skip to content
Lukas Polak

August 17, 2022

Stack Data Structure

Master the Stack data structure in TypeScript! Implement a type-safe, test-driven stack and uncover its similarities to the Queue.

Introduction

The Stack Data Structure is similar to the Queue. The difference is that Stack obeys the LIFO (Last In First Out) principle, and Queue, on the other hand, obeys the FIFO (First In First Out) principle.

Why is it important to know this? Well, if you know how to implement a Queue, you know how to implement a Stack; You need to change a few methods naming and use different methods on the array, but the rest is mostly the same.

Stack operations

The Stack has a few basic operations that are described below. It does not mean you cannot add any other operation if you need one.

push

Adds an item to the top of the Stack.

pop

Removes the top item (latest) of the Stack.

peek

Returns the top item (latest) of the Stack.

length

Returns the length of the Stack.

isEmpty

Returns true if the Stack is empty, false otherwise.

Implementation

TypeScript definition

index.ts
// as we want to support various item types, we are making our type `CreateStackReturnType` generic by accepting a `T` type variabletype CreateStackReturnType<T> = {  // adds an item to the top of the Stack, do not return anything  push: (item: T) => void  // removes the top item (latest) of the Stack, do not return anything  pop: () => void  // returns the top item (latest) of the Stack  peek: () => T  // returns the length of the Stack  length: number  // returns true if the Stack is empty, false otherwise  isEmpty: () => boolean}

Factory function implementation

index.ts
// `createStack` factory function accepts generic `T` type variable// `T` type variable will be used within `CreateStackReturnType` and inside of factory functionexport function createStack<T>(): CreateStackReturnType<T> {  // the Stack itself will be an array of items  // the type of item is dynamic, controlled by the `T` type variable  const stack: Array<T> = []
  return {    push() {},    pop() {},    peek() {},    // we need to use `get` to access the latest `length` property of the Stack    get length() {},    isEmpty() {},  }}

Adding tests

index.ts
import { createStack } from './stack'
describe('stack', () => {  const stack = createStack<string>()
  it('should be empty initially', () => {    // initially stack is empty    expect(stack.length).toBe(0)    expect(stack.isEmpty()).toBe(true)    expect(stack.peek()).toBeUndefined()  })
  it('should push and pop', () => {    stack.push('First item')    stack.push('Second item')    stack.push('Third item')
    expect(stack.length).toBe(3)    expect(stack.isEmpty()).toBe(false)    expect(stack.peek()).toBe('Third item')
    stack.pop()    expect(stack.length).toBe(2)    expect(stack.isEmpty()).toBe(false)    expect(stack.peek()).toBe('Second item')
    stack.pop()    expect(stack.length).toBe(1)    expect(stack.isEmpty()).toBe(false)    expect(stack.peek()).toBe('First item')
    stack.pop()    expect(stack.length).toBe(0)    expect(stack.isEmpty()).toBe(true)    expect(stack.peek()).toBeUndefined()  })})

Implement push

index.ts
export function createStack<T>(): CreateStackReturnType<T> {  const stack: Array<T> = []
  return {    push(item: T) {      // push method append an item to the top of the stack      stack.push(item)    },    pop() {},    peek() {},    get length() {},    isEmpty() {},  }}

Implement pop

index.ts
export function createStack<T>(): CreateStackReturnType<T> {  const stack: Array<T> = []
  return {    push(item: T) {      // push method append an item to the top of the stack      stack.push(item)    },    pop() {      // pop method removes the last item from the stack      stack.pop()    },    peek() {},    get length() {},    isEmpty() {},  }}

Implement peek

index.ts
export function createStack<T>(): CreateStackReturnType<T> {  const stack: Array<T> = []
  return {    push(item: T) {      // push method append an item to the top of the stack      stack.push(item)    },    pop() {      // pop method removes the last item from the stack      stack.pop()    },    peek() {      // peek method returns the last item from the stack      return stack[Stack.length - 1]    },    get length() {},    isEmpty() {},  }}

Implement length

index.ts
export function createStack<T>(): CreateStackReturnType<T> {  const stack: Array<T> = []
  return {    push(item: T) {      // push method append an item to the top of the stack      stack.push(item)    },    pop() {      // pop method removes the last item from the stack      stack.pop()    },    peek() {      // peek method returns the last item from the stack      return stack[Stack.length - 1]    },    get length() {      // length method returns the length of the stack      return stack.length    },    isEmpty() {},  }}

Implement isEmpty

index.ts
export function createStack<T>(): CreateStackReturnType<T> {  const stack: Array<T> = []
  return {    push(item: T) {      // push method append an item to the top of the stack      stack.push(item)    },    pop() {      // pop method removes the last item from the stack      stack.pop()    },    peek() {      // peek method returns the last item from the stack      return stack[Stack.length - 1]    },    get length() {      // length method returns the length of the stack      return stack.length    },    isEmpty() {      // returns true if the Stack is empty, false otherwise      return Stack.length === 0    },  }}

Complete Implementation

index.ts
type CreateStackReturnType<T> = {  isEmpty: () => boolean  length: number  peek: () => T  pop: () => void  push: (item: T) => void}
export function createStack<T>(): CreateStackReturnType<T> {  const stack: Array<T> = []
  return {    isEmpty() {      return stack.length === 0    },    get length() {      return stack.length    },    peek() {      return stack[stack.length - 1]    },    pop() {      stack.pop()    },    push(item: T) {      stack.push(item)    },  }}

Conclusion

As you may see, the Stack implementation is straightforward and almost the same as the implementation of the Queue.

Have you found any bugs, or do you have any questions? Feel free to reach out on Twitter.

If you do not want to miss the next article, click on the follow button!

Share on X