Stack Flashcards
Is an Stack Random or Sequential Access?
Sequential
A stack is a data structure in which we add elements and remove elements according to LIFO or FIFO?
LIFO. Last in, First out.
What is a real world analogy for a Stack?
Washing a stack of dishes. When someone adds a plate to the stack, it will be the first one you grab to wash.
What does BigO scoring not account for with the stack?
It’s useful LIFO ability.
What are the four fairly standard Stack methods?
Push, Pop, Peek and Contains.
How should you implement a Stack in Kotlin?
Use java.util.ArrayDeque.
E.g.
var stack = ArrayDeque()
How should you NOT implement a Stack in Kotlin?
You should NOT use java.util.Stack.
What does the PUSH method do?
It pushes an element onto the top of the Stack.
What does the POP method do?
It removes an element form the top of the stack and return the ‘popped’ element.
What does the PEAK method do?
It allows you to get the value at the top of the list without actually removing it.
What does the CONTAINS method do?
It is used for searching through the Stack. It returns true or false.
What is the BigO of ACCESSING an element in a Stack?
O(n) Worst-case the element we need is at the bottom of the stack and we must pop all other elements on top of it before reaching the bottom element.
What is the BigO of SEARCHING an element in a Stack?
O(n) Linear Search is required.
What is the BigO of INSERTING an element in a Stack?
O(1) Push requires only one operation.
What is the BigO of DELETING an element in a Stack?
O(1) Pop requires only one operation.
