Discussing data structures!
Stack
Stack is a linear data structure accessible in single direction having two main operations:
Push: To insert the data Pop: To remove the data
The element which is inserted last is removed first that is why it is called as LIFO(last in first out) or FILO(first in last out).
Applications
Undo/Redo: While writing “My name is…” , pages are stored as shown below in undo stack.
To get to the earlier version, the last page is popped out in the undo stack to restore the previous page. This page will be stored in redo stack. That is how stack works here.
Reversing arrays: As the last element pops out first and first element pops out last, arrays can be restored easily using stacks.
Parenthesis Checking: Parenthesis balancing is checked using stack. First, the left hand parenthesis are inserted in the stack. Whenever a right hand parenthesis is encountered, the outermost left hand parenthesis is popped out to cancel the right hand parenthesis .This is continued till the end. If the stack is empty in the end, the parenthesis is balanced.
Heaps
Heap is a data structure implemented using the concept priority queue. Heaps are of two types max heaps and min heaps. In max heaps priority is given to the largest valued element while in min heaps, the lowest valued element.
Heap can be implemented using various methods including binary heap, binomial heap and fibonacci heap, binary being the most common method. Fibonacci heap and Binomial heap have more complex implementations.
Although in popular programming languages Standard Template Library(STL) can be used to implement heap with the following syntax:
priority_queue<int> nameOfPriorityQueue ;
Let’s see binary heap in more detail for better understanding of heap. Binary heap is in the form of a binary tree.
Example of binary heaps:
