Stack
What is Stack?
Stack is an abstract data type. It’s underlying data structure is an array or linked list. Stack works on the concept of “Last In First Out” or “First In Last Out”. Let’s understand the concept of stack by an example. We have a bookshelf and 10 different books. How do we keep the books on the bookshelf? One book on top of another book. So, This way the last book will always be kept on the top. So If we want to get any book we have to take the top book first. Then, the next book will be taken off. Following this, the last book will be the same book that has been kept at first.
The basic operation of stack are: push(), pop() and peek()
Push operation:
The push operation puts the item to the
top of stack. It’s very simple and
can be
done in O(1).
Pop operation:
The pop operation takes out the top item from the stack. It’s also a simple operation and can be done in O(1).
Peek operation:
The peek operation returns the value of the top element of stack. It does not take out the element from the stack. Stack remains as it is. It’s very simple and can be done in O(1).
Application of Stack:
- In the DFS algorithm, stack works as an underlying data structure.
- Finding strongly connected components in a graph
- Finding Euler-cycles in graphs.