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.

1// as we want to support various item types, we are making our type `CreateStackReturnType` generic by accepting a `T` type variable
2type CreateStackReturnType<T> = {
3  // adds an item to the top of the Stack, do not return anything
4  push: (item: T) => void
5  // removes the top item (latest) of the Stack, do not return anything
6  pop: () => void
7  // returns the top item (latest) of the Stack
8  peek: () => T
9  // returns the length of the Stack
10  length: number
11  // returns true if the Stack is empty, false otherwise
12  isEmpty: () => boolean
13}

1// `createStack` factory function accepts generic `T` type variable
2// `T` type variable will be used within `CreateStackReturnType` and inside of factory function
3export function createStack<T>(): CreateStackReturnType<T> {
4  // the Stack itself will be an array of items
5  // the type of item is dynamic, controlled by the `T` type variable
6  const stack: Array<T> = []
7
8  return {
9    push() {},
10    pop() {},
11    peek() {},
12    // we need to use `get` to access the latest `length` property of the Stack
13    get length() {},
14    isEmpty() {},
15  }
16}

1import { createStack } from './stack'
2
3describe('stack', () => {
4  const stack = createStack<string>()
5
6  it('should be empty initially', () => {
7    // initially stack is empty
8    expect(stack.length).toBe(0)
9    expect(stack.isEmpty()).toBe(true)
10    expect(stack.peek()).toBeUndefined()
11  })
12
13  it('should push and pop', () => {
14    stack.push('First item')
15    stack.push('Second item')
16    stack.push('Third item')
17
18    expect(stack.length).toBe(3)
19    expect(stack.isEmpty()).toBe(false)
20    expect(stack.peek()).toBe('Third item')
21
22    stack.pop()
23    expect(stack.length).toBe(2)
24    expect(stack.isEmpty()).toBe(false)
25    expect(stack.peek()).toBe('Second item')
26
27    stack.pop()
28    expect(stack.length).toBe(1)
29    expect(stack.isEmpty()).toBe(false)
30    expect(stack.peek()).toBe('First item')
31
32    stack.pop()
33    expect(stack.length).toBe(0)
34    expect(stack.isEmpty()).toBe(true)
35    expect(stack.peek()).toBeUndefined()
36  })
37})

1export function createStack<T>(): CreateStackReturnType<T> {
2  const stack: Array<T> = []
3
4  return {
5    push(item: T) {
6      // push method append an item to the top of the stack
7      stack.push(item)
8    },
9    pop() {},
10    peek() {},
11    get length() {},
12    isEmpty() {},
13  }
14}

1export function createStack<T>(): CreateStackReturnType<T> {
2  const stack: Array<T> = []
3
4  return {
5    push(item: T) {
6      // push method append an item to the top of the stack
7      stack.push(item)
8    },
9    pop() {
10      // pop method removes the last item from the stack
11      stack.pop()
12    },
13    peek() {},
14    get length() {},
15    isEmpty() {},
16  }
17}

1export function createStack<T>(): CreateStackReturnType<T> {
2  const stack: Array<T> = []
3
4  return {
5    push(item: T) {
6      // push method append an item to the top of the stack
7      stack.push(item)
8    },
9    pop() {
10      // pop method removes the last item from the stack
11      stack.pop()
12    },
13    peek() {
14      // peek method returns the last item from the stack
15      return stack[Stack.length - 1]
16    },
17    get length() {},
18    isEmpty() {},
19  }
20}

1export function createStack<T>(): CreateStackReturnType<T> {
2  const stack: Array<T> = []
3
4  return {
5    push(item: T) {
6      // push method append an item to the top of the stack
7      stack.push(item)
8    },
9    pop() {
10      // pop method removes the last item from the stack
11      stack.pop()
12    },
13    peek() {
14      // peek method returns the last item from the stack
15      return stack[Stack.length - 1]
16    },
17    get length() {
18      // length method returns the length of the stack
19      return stack.length
20    },
21    isEmpty() {},
22  }
23}

1export function createStack<T>(): CreateStackReturnType<T> {
2  const stack: Array<T> = []
3
4  return {
5    push(item: T) {
6      // push method append an item to the top of the stack
7      stack.push(item)
8    },
9    pop() {
10      // pop method removes the last item from the stack
11      stack.pop()
12    },
13    peek() {
14      // peek method returns the last item from the stack
15      return stack[Stack.length - 1]
16    },
17    get length() {
18      // length method returns the length of the stack
19      return stack.length
20    },
21    isEmpty() {
22      // returns true if the Stack is empty, false otherwise
23      return Stack.length === 0
24    },
25  }
26}

1type CreateStackReturnType<T> = {
2  isEmpty: () => boolean
3  length: number
4  peek: () => T
5  pop: () => void
6  push: (item: T) => void
7}
8
9export function createStack<T>(): CreateStackReturnType<T> {
10  const stack: Array<T> = []
11
12  return {
13    isEmpty() {
14      return stack.length === 0
15    },
16    get length() {
17      return stack.length
18    },
19    peek() {
20      return stack[stack.length - 1]
21    },
22    pop() {
23      stack.pop()
24    },
25    push(item: T) {
26      stack.push(item)
27    },
28  }
29}

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