Stack Data Structure

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.

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.

Adds an item to the top of the Stack.

Removes the top item (latest) of the Stack.

Returns the top item (latest) of the Stack.

Returns the length of the Stack.

Returns true if the Stack is empty, false otherwise.

// as we want to support various item types, we are making our type `CreateStackReturnType` generic by accepting a `T` type variable
type 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
}

// `createStack` factory function accepts generic `T` type variable
// `T` type variable will be used within `CreateStackReturnType` and inside of factory function
export 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() {},
  }
}

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()
  })
})

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() {},
  }
}

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() {},
  }
}

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() {},
  }
}

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() {},
  }
}

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
    },
  }
}

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)
    },
  }
}

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 this post on Twitter