Stack
Stack is an important data structure which stores its elements in an ordered manner
Analogy
You must have seen a stack of book. When you need to remove a bottom book, you first need to remove the topmost book. Thats how stack works.
Stack Concept1. Stack is a linear data structure which can be used by either using array or linked list
2. Element added and removed is called TOP
Array Representation
Stack has two variables
1. TOP is used to store the address of the topmost element of stack
2. MAX which use to store the maximum number that stack can hold
Stack Operations
1. push(x) = add an item x to the top of stack
2. pop() = remove an item from the top of stack
3. top() = reveal/ return the top item from the stack
There are several applications using stack data structure that we will discuss
1. Infix evaluation
2. Postfix evaluation
3. Prefix evaluation
4. Infix to Postfix conversion
5. Infix to Prefix conversion
6. Depth First Search
Prefix : operator is written before operands
Ex: *4 10 // +5 *3 4 // +4/*6 – 5 2 3
Infix : operator is written between operands
Ex: 4 * 10 // 5 + 3 * 4 // 4 + 6 * (5 – 2) / 3
Postfix : operator is written after operands
Ex: 4 10* // 5 3 4* + // 4 6 5 2 – *3/ +1
Depth First Search = A searching method used by data structure to search data start from the bottom, used in stack.
Breadth First Search = A searching method used by data structure to search data start from the side, this operation is used in Queue.