Stack data structure

This tutorial is a part of the Data Structures and Algorithms class:

• Stack in real life
• Build Stack data structure
• How to insert/delete/access/search data
• How fast to insert/delete/access/search data

Stack in real life

Stack data structure:

• mimics a physical stack of things in real life. Example: a stack of books.
• data (ex: books) in/out follows the physics: Last-In-First-Out (LIFO).
• is a very popular data structure. Example applications: real life stack modeling (stack of books), function call stack, implement Depth-First-Search algorithm, ...

Build Stack data structure

// build Stack data structure
class Stack {
  constructor() {
    this.stack = []
  }
  
  // add data to stack, O(1)
  push(val) {
    this.stack.push(val)
    return val
  }

  // remove data from stack, O(1)
  pop() {
    return this.stack.pop()
  }

  // see stack size, O(1)
  size() {
    return this.stack.length
  }

  // see element on top of stack, O(1)
  peek() {
    return this.stack[this.stack.length - 1]
  }

  // see all data in stack, O(1)
  print() {
    console.log(this.stack)
  }
}

// create a stack
const stack = new Stack()
stack.print() // []

$ node stack-data-structure.js
[]

How to insert/delete/access/search data

// insert
console.log(stack.push(1)) // 1
console.log(stack.push(2)) // 2
console.log(stack.push(3)) // 3
stack.print() // [ 1, 2, 3 ]

// delete 
console.log(stack.pop()) // 3
stack.print() // [ 1, 2 ]

// peak
console.log(stack.peek()) // 2

// size
console.log(stack.size()) // 2

$ node stack-data-structure.js
1
2
3
[ 1, 2, 3 ]
3
[ 1, 2 ]
2
2

How fast to insert/delete/access/search data

⬆️ Time complexity (worst case) per operation

Real life interview questions

1. What is Stack data structure usually used for? Give 3 different examples.
2. What is the distinct feature of Stack data structure? What's its short 4 characters name?
3. Write your own a Stack data structure with these operations: push, pop, peek, size, print.
4. How do you insert/delete/access/search with Stack data structure?
5. What is the Time Complexity of Stack data structure on insert/delete/access/search operation?
6. Solve Tower of Hanoi coding challenge.