Stack
Stack is a data structure which behaves like a stack of some real world objects ( books, plates, etc ) allowing immediate access to top of the stack only at any given time.
Since we have immediate access to top of the stack at any time, this data structure is apt for scenarios where we need the most recent added element or we need to process elements always in such a fashion that we always process the last added element before the first added element. Stack is also called as LIFO ( Last In First Out ) data structure. Recursion stacks are a classical use case of stacks where activation records of functions are pushed and popped
In most of the common implementations of stack, we have the following operations:
pop() - removes the top element of stack if it exists --- O(1)
push() - pushes an element to top of the stack given the stack doesn't overflow --- O(1)
top() - returns the value of element on top of the stack --- O(1)
size() - returns the number of elements present in the stack --- O(n)
empty() - returns true if the stack is empty else returns false --- O(1)