OBJECTIVES

• Define what a stack is
• Understand use cases for a stack
• Big O of the stack

What is a Stack?
A stack is a linear data structure that follows a particular order for insertion and deletion. The is referred to as LIFO (Last In First Out). The last element added to the stack will be the first element removed from the stack.
How is it used?
Think about a stack of plates, or a stack of markers, or a stack of….anything. As you pile it up, when you want to remove the plate, you start from the top which is the last thing (or the topmost thing) is what gets removed first.
Visualization of a stack
Where are Stacks used?

• Managing function invocations
• Undo / Redo
• Routing (the history object) is treated as a stack!

BigO of stack

• Insertion –   O(1)
• Removal –   O(1)
• Searching –   O(N)
• Access –   O(N)

Recap

• Stacks are a LIFO data structure where the last value is always the first one out.
• Stacks are used to handling function invocations (the call stack), for operations like undo/redo, and for routing (remember pages you have visited and go back/forward) and much more!
• They are not a built-in data structure in JavaScript but are relatively simple to implement
• Insert and remove are both O(1)

Written by Okocha Ebube