Session 3-Linked List Implementation II-2101727190-Fedrick

Subtopic:
- Stack Concept
- Inflix, postfix and prefix notation
- Depth First Search
- Queue Concept
- Breadth First Search

Stack Concept
is an important data structure which stores its elements in an ordered maner.
In stack concept, the data are stored in Last In First Out way.

Stack Operation
- push(x) : add an item x to the top of the stack.
- pop()    : remove an item from the top of the stack.
- top()     : reveal/return the top item from the stack.
//top = peek.

Stack Applications
There are 4 applications of stack we will discuss:
- Infix
- Postfix
- Prefix
- Depth first search

Inflix, Postfix, and Prefix Notation
- Prefix notation = Reverse Polish notation
- Inflix notation (commonly used)
- Postfix notation = Polish notation

Prefix   : operator is written before operands
Infix     : operator is written betwen operands
Postfix : operator is written after operands
//We recommend to use Prefix and Postfix because much easier for computer to evaluate.

Example - Infix.
4 + 8 * (4+1) / 5
4 + 8 * 5 / 5
4 + 40 / 5
4 + 8
12

Example - Postfix
String                   Stack
4 6 5 2 - * 3 / +           
4 6 5 2 - * 3 / +    4            push 4
4 6 5 2 - * 3 / +    4 6         push 6
4 6 5 2 - * 3 / +    4 6 5      push 5
4 6 5 2 - * 3 / +    4 6 5 2   push 2
4 6 5 2 - * 3 / +    4 6 3      pop 2, pop 5, push 5-2
4 6 5 2 - * 3 / +    4 18       pop 3, pop 6, push 6*3
4 6 5 2 - * 3 / +    4 18 3    push 3
4 6 5 2 - * 3 / +    4 6         pop 3, pop 18, push 18/3
4 6 5 2 - * 3 / +    10          pop 6, pop 4, push 10 -> the result

Example - Prefix
+ 7 - x 6 5 ^ 3 2
+ 7 - x 6 5 ^ 3 2
+ 7 - x 6 5 9
+ 7 - x 6 5 9
+ 7 - 30 9
+ 7 - 30 9
+ 7 21
+ 7 21
28

Depth First Search
Depth First Search is an algorithm we can use for traversing or searching in tree or graph.

in this search, data with last index will be poped firstly.

Queue Concepts
is an important data structure which stores its elements in an ordered maner.
In queue concept, the data are stored in First In First Out way.

Same with stack concepts but in queue top = front.
Queue Operation
- push(x) : add an item x to the top of the stack.
- pop()    : remove an item from the top of the stack.
- front()     : reveal/return the top item from the stack.
//front = peek.

now what happen if we push MAXN times and pop MAXN times?

we cant push another data into the queue, so we can use Circular Queue.

Circular Queue

if R reach MAXN then set R as zero, do the same to L.

Queue Applications
There are 3 applications of queue we will discuss:
- Deques
- Priority Queues
- Breadth First Search

Deques
is a list in which elements can be inserted or deleted at either end.

Priority Queue
is an abstract data type in which the each element is assigned a priority.

Breadth First Search
same like DFS is also an algorithm for traversing or searching in a tree or graph but pop data in the smaller index first.

in this search data with front index will be poped firstly.