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()
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.
What is an example use case of a Stack
Recursion. Each time a function calls itself it is pushed to the stack and then popped when it completes.
Back button in a web browser.
Undo/Redo.
What are the names of the operations for stacks?
The insert operation is usually called “push”
delete is “pop”
retrieve is “peek”
isempty tells us whether the stack is empty
new that creates an empty stack
note: Stacks are inherently tied to the idea of recursion
What is a stack?
A stack is a linear container that allows us to
insert, delete and retrieve only at one end.
There is no general find operation
A stack is LIFO (last in, first out)
List the area of applications where stack data structure can be used?
Expression evaluation
Backtracking
Memory Management
Function calling and return
What is the condition for a stack overflow?
Overflow occurs when top = Maxsize -1
Write the steps involved in the insertion and deletion of an element in the stack.
Push:
–Increment the variable top so that it can refer to the next memory allocation
–Copy the item to the at the array index value equal to the top
Repeat step 1 and 2 until stack overflows
Pop:
–Store the topmost element into the an another variable
–Decrement the value of the top
–Return the topmost element
Depth first search
Uses a stack to progress to the deepest part of a tree or graph before traversing to other nodes.
Can also be done with recursion
