- Stack is a linear data structure.
- Stack is an ordered list of similar data type.
- Stack in which elements follow a specific order and operations will be performed.
- Stack follows LIFO(Last In First Out).
- Elements will be added from the end called TOP of stack and removes from the same end.
Stack ADT: Abstract Data Type specifies the operations can be performed on Stack
- Push: Push an element on to the Stack. Returns “Overflow” if stack is full.
- Pop: Deletes an item from Stack. Returns “Underflow” if Stack is empty.
- Peek: Returns top element of stack but not removes.
- isEmpty: Returns true if stack is empty, else false
- isFull: Returns true if stack is full, else false
- A pointer called TOP is used to keep track of the top element in the stack.
- The initial value of TOP is -1 so that the stack is empty if TOP == -1.
- We increase the value of TOP and place the new element in the position pointed to by TOP on PUSH.
- TOP value modified by -1 on POP and returns the item which is deleted.
- Before push, we need to test if the Stack is Full or Not
- Before pop, we need to test if the Stack is Empty or Not
- ‘top’ of stack represents the top element.
- While removing the elements from stack, top value decreases.
Applications of stack:
- Function recursion.
- Finding the Binary value of Decimal value.
- Infix to Post fix or Prefix conversion
- Forward and backward feature in web browsers
- Tower of Hanoi problem
- Tree traversals
- DFS algorithm of Graph
Stack can be implemented in 2 ways:
- Using arrays
- Using linked lists