1) STACK CONCEPT
- A stack is a collection data structure which has two fundamental operation: push and pop.
Data are stored in Last In First Out (LIFO) way. In the pushdown stacks only two operations are allowed: Push the item into the stack, and Pop the item out of the stack. A stack is a limited access data structure - elements can be added and removed from the stack only at the top. Push adds an item to the top of the stack, Pop removes the item from the top.
- Top means the most recent data.
2) QUEUE CONCEPT
- Queue is a collection data structure which has two fundamental operation: push and pop (similar to stack). The data are stored in First In First Out (FIFO) way. This linear data structure can only be inserted from the bottom and used from the top.
Data are stored in Last In First Out (LIFO) way. In the pushdown stacks only two operations are allowed: Push the item into the stack, and Pop the item out of the stack. A stack is a limited access data structure - elements can be added and removed from the stack only at the top. Push adds an item to the top of the stack, Pop removes the item from the top.
- Top means the most recent data.
2) QUEUE CONCEPT
- Queue is a collection data structure which has two fundamental operation: push and pop (similar to stack). The data are stored in First In First Out (FIFO) way. This linear data structure can only be inserted from the bottom and used from the top.
3) INFIX, PREFIX, POSTFIX
- Infix = Operators are written in between their operands. (Operands are in the middle)
Example --> A + B
- Prefix = Operators are written after their operands. ( Operands are on the right )
Example --> A B +
- Postfix = Operators are written before their operands. (Operands are on the left)
Example --> + A B
4) Depth-First Search (DFS)
-Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.
DFS has many uses such as :
- Finding articulation point and bridge in a graph.
- Topological sorting.
- Finding connected component.
- Finding the bridges of a graph.
- Planarity Testing.
- etc.
5) Breadth First Search (BFS)
-Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root, and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
- It uses the opposite strategy as Depth-first search (DFS), which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes.
BFS has many uses such as :
- Finding the shortest path between two nodes u and v, with path length measured by number of edges.
- Ford-Fulkerson method for computing the maximum flow in a flow network.
- Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.
-Testing bipartiteness of a graph.
- Infix = Operators are written in between their operands. (Operands are in the middle)
Example --> A + B
- Prefix = Operators are written after their operands. ( Operands are on the right )
Example --> A B +
- Postfix = Operators are written before their operands. (Operands are on the left)
Example --> + A B
4) Depth-First Search (DFS)
-Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.
DFS has many uses such as :
- Finding articulation point and bridge in a graph.
- Topological sorting.
- Finding connected component.
- Finding the bridges of a graph.
- Planarity Testing.
- etc.
5) Breadth First Search (BFS)
-Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root, and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
- It uses the opposite strategy as Depth-first search (DFS), which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes.
BFS has many uses such as :
- Finding the shortest path between two nodes u and v, with path length measured by number of edges.
- Ford-Fulkerson method for computing the maximum flow in a flow network.
- Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.
-Testing bipartiteness of a graph.
No comments:
Post a Comment