Data Structures: Stacks Flashcards
What are stacks?
A stack consists of a sequence of items, which should be thought of as piled one on top of the other like a physical stack of boxes or cafeteria trays.
The rule: Insertion and deletion only occurs at the top. Only the top item on the stack is accessible at any given time.
Stacks are L.I.F.O structures
What does L.I.F.O stand for?
L.I.F.O
Last in first out.
Stack opperations
Push -adding an element to the stack
Pop -removing an element from the stack
peek -looking at the element at the top of a stack (pointer)
IsEmpty -Checks if stack is empty
Run time analysis
O(1)
Common uses of stacks
Function calls/Recursion
Undo opperations
Balanced parantheses checks
To reverse an order.
Two ways to implement a stack?
Array or linked list
What is the pointer in a stack called?
Top
