Stack Data Structure
August 17, 2022Introduction
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
1// as we want to support various item types, we are making our type `CreateStackReturnType` generic by accepting a `T` type variable2type CreateStackReturnType<T> = {3 // adds an item to the top of the Stack, do not return anything4 push: (item: T) => void5 // removes the top item (latest) of the Stack, do not return anything6 pop: () => void7 // returns the top item (latest) of the Stack8 peek: () => T9 // returns the length of the Stack10 length: number11 // returns true if the Stack is empty, false otherwise12 isEmpty: () => boolean13}
Factory function implementation
1// `createStack` factory function accepts generic `T` type variable2// `T` type variable will be used within `CreateStackReturnType` and inside of factory function3export function createStack<T>(): CreateStackReturnType<T> {4 // the Stack itself will be an array of items5 // the type of item is dynamic, controlled by the `T` type variable6 const stack: Array<T> = []78 return {9 push() {},10 pop() {},11 peek() {},12 // we need to use `get` to access the latest `length` property of the Stack13 get length() {},14 isEmpty() {},15 }16}
Adding tests
1import { createStack } from './stack'23describe('stack', () => {4 const stack = createStack<string>()56 it('should be empty initially', () => {7 // initially stack is empty8 expect(stack.length).toBe(0)9 expect(stack.isEmpty()).toBe(true)10 expect(stack.peek()).toBeUndefined()11 })1213 it('should push and pop', () => {14 stack.push('First item')15 stack.push('Second item')16 stack.push('Third item')1718 expect(stack.length).toBe(3)19 expect(stack.isEmpty()).toBe(false)20 expect(stack.peek()).toBe('Third item')2122 stack.pop()23 expect(stack.length).toBe(2)24 expect(stack.isEmpty()).toBe(false)25 expect(stack.peek()).toBe('Second item')2627 stack.pop()28 expect(stack.length).toBe(1)29 expect(stack.isEmpty()).toBe(false)30 expect(stack.peek()).toBe('First item')3132 stack.pop()33 expect(stack.length).toBe(0)34 expect(stack.isEmpty()).toBe(true)35 expect(stack.peek()).toBeUndefined()36 })37})
Implement push
1export function createStack<T>(): CreateStackReturnType<T> {2 const stack: Array<T> = []34 return {5 push(item: T) {6 // push method append an item to the top of the stack7 stack.push(item)8 },9 pop() {},10 peek() {},11 get length() {},12 isEmpty() {},13 }14}
Implement pop
1export function createStack<T>(): CreateStackReturnType<T> {2 const stack: Array<T> = []34 return {5 push(item: T) {6 // push method append an item to the top of the stack7 stack.push(item)8 },9 pop() {10 // pop method removes the last item from the stack11 stack.pop()12 },13 peek() {},14 get length() {},15 isEmpty() {},16 }17}
Implement peek
1export function createStack<T>(): CreateStackReturnType<T> {2 const stack: Array<T> = []34 return {5 push(item: T) {6 // push method append an item to the top of the stack7 stack.push(item)8 },9 pop() {10 // pop method removes the last item from the stack11 stack.pop()12 },13 peek() {14 // peek method returns the last item from the stack15 return stack[Stack.length - 1]16 },17 get length() {},18 isEmpty() {},19 }20}
Implement length
1export function createStack<T>(): CreateStackReturnType<T> {2 const stack: Array<T> = []34 return {5 push(item: T) {6 // push method append an item to the top of the stack7 stack.push(item)8 },9 pop() {10 // pop method removes the last item from the stack11 stack.pop()12 },13 peek() {14 // peek method returns the last item from the stack15 return stack[Stack.length - 1]16 },17 get length() {18 // length method returns the length of the stack19 return stack.length20 },21 isEmpty() {},22 }23}
Implement isEmpty
1export function createStack<T>(): CreateStackReturnType<T> {2 const stack: Array<T> = []34 return {5 push(item: T) {6 // push method append an item to the top of the stack7 stack.push(item)8 },9 pop() {10 // pop method removes the last item from the stack11 stack.pop()12 },13 peek() {14 // peek method returns the last item from the stack15 return stack[Stack.length - 1]16 },17 get length() {18 // length method returns the length of the stack19 return stack.length20 },21 isEmpty() {22 // returns true if the Stack is empty, false otherwise23 return Stack.length === 024 },25 }26}
Complete Implementation
1type CreateStackReturnType<T> = {2 isEmpty: () => boolean3 length: number4 peek: () => T5 pop: () => void6 push: (item: T) => void7}89export function createStack<T>(): CreateStackReturnType<T> {10 const stack: Array<T> = []1112 return {13 isEmpty() {14 return stack.length === 015 },16 get length() {17 return stack.length18 },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}
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!