Stacks Flashcards
What is an ADT ( Abstarct Data Type )
ADT is a formal description of the data structure ( what it does and etc).
ADT is not the programming language or the code of the data structure
What is a linear structure ?
Non-indexed container object that can grow and shink one element at a time.
In each order are elements acessed in a stack ?
LIFO: Last in, First out:
i.e. pile of books
How does a stack solves the maze problem
By pushing all possible next steps into the stack, popping and moving to them, when arriving to next one seeing possible next ones.
Problem : we can see the maze
What is the difference between a stack and a queue.
Stack pop and push from the top
queue, enqueue from the end, dequeue from the front
Does it make a difference to have the top of the stack at position 0 or n? If yes, which one is better, and how does the Big O notation change from it
Yes. It is better to have the top at position n so when you push and append you get O(1). instead of O(n).
What is one additional benefit from encapsulation?
Being able to change the location of the top without having to change the whole implementation.
What is a Stackframe?
a stack frame is a memory management technique used in some programming languages for generating and eliminating temporary variables. In other words, it can be considered the collection of all information on the stack pertaining to a subprogram call.
What are operands and operators
operands => numbers
operators => multiplication etc
What is an infix notation
Operator in the middle of operands
Reverse Polish Notation
Postfix ( the operator comes after the operands )
Polish Notation
Infix ( the operator comes before the operands)
What is the Big O notation of reversing a list? If we use a stack to do so what would be the Big O?
O(n), Stack O(1)
