–One
that stores data
–One
that stores the address of the next node
•The START pointer of the linked
list is used as TOP
•All insertions and deletions are
done at the node pointed by the TOP
•If TOP = NULL, then it indicates
that the stack is empty
Stack Operations
•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.
Example :
2. Stack Applications
There
are three arithmetic notations known:
•Prefix
notation, also known as Reverse Polish notation.
•Infix
notation (commonly used)
•Postfix
notation, also known as Polish notation.
Example :
Prefix : * 4 10
Infix : 4 * 10
Postfix: 4 10 *
Infix Evaluation
Evaluate
a given infix expression: 4 + 6 * (5 – 2) / 3
To
evaluate infix notation, we should search the highest precedence
operator
in the string.
4
+ 6 * (5 – 2) / 3 search the highest precedence
operator, it is ( )
4
+ 6 * 3 / 3 search the highest precedence
operator, it is *
4
+ 18 / 3 search
the highest precedence operator, it is /
4
+ 6 search
the highest precedence operator, it is +
10
Postfix Evaluation
Manually
Scan
from left to right
7 6
5 x 3
2 ^ – + , scan until reach the first operator
7 6
5 x
3 2 ^
– + , calculate 6 x 5
7 30
3 2 ^
– + , scan again until reach next operator
7 30
3 2 ^ – + , calculate 32
7 30
9 – + ,
scan again to search next operator
7 30 9 –
+ , calculate 30 – 9
7 21 + , scan again
7
21
+ ,
calculate 7 + 24
28 ,
finish
String
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
Prefix Evaluation
Manually
Scan
from right to left
+ 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
Conversion : Infix to Postfix
•Manually
•A + B
– C x D
^ E / F ,
power has the highest precedence
•A + B
– C x D E ^ / F ,
put ^ behind D and E
•A + B
– C
x D E ^ / F ,
x and / have same level precedence
•A + B
– C D E ^ x / F ,
put x at the end
•A + B
– C
D E ^ x / F ,
continue with the same algorithm till finish
•A + B
– C D E ^ x F /
•A
+ B – C D E ^ x F /
•A B +
– C D E ^ x F /
•A
B + – C D E ^ x F /
•A B +
C D E ^ x F / – ,
this is the Postfix notation
String Stack Postfix String
4 + 6 * (5 – 2) / 3
4 + 6
* (5 – 2) / 3 4
4 + 6 *
(5 – 2) / 3 + 4
4 + 6 * (5
– 2) / 3 + 4 6
4 + 6 * (5 –
2) / 3 + * 4 6
4 + 6 * (5 –
2) / 3 + * ( 4 6
4 + 6 * (5 – 2)
/ 3 + * ( 4
6 5
4 + 6 * (5 – 2) /
3 + * ( – 4 6 5
4 + 6 * (5 – 2) / 3 + * 4 6
5 2
4 + 6 * (5 – 2) / 3 + * / 4
6 5 2 –
4 + 6 * (5 – 2) / 3 + / 4 6
5 2 – *
4 + 6 * (5 – 2) / 3 + / 4 6
5 2 – * 3
4 + 6 * (5 – 2) / 3 4 6 5 2 – * 3 / +
Conversion : Infix to Prefix
Manually
A
+ B – C x D
^ E / F
A
+ B – C x ^ D E / F
A
+ B – C
x ^ D E / F
A
+ B – x C ^ D E / F
A
+ B – x
C ^ D E / F
A
+ B – / x C ^ D E F
A + B – / x C ^ D E F
+
A B – / x C ^ D E F
+ A B – / x C ^ D E F
–
+ A B / x C ^ D E F , this is the Prefix
notation
3. Depth Search
Depth
First Search (DFS)
is an algorithm for traversing or searching in a
tree or graph. We start at the root of the
tree (or some arbitrary node
in graph) and explore as far as possible along each branch beforebacktracking.
DFS
has many applications, such as:
•Finding
articulation point and bridge in a graph
•Finding
connected component
•Topological
sorting
•etc.
DFS
can be implemented by a recursive function or an iterative procedure
using stack, their results may have a
little differences on visiting
order but both are correct.
Algorithm:
Prepare
an empty stack
Push
source/root into stack
Mark
source/root
While
stack is not empty
Pop an item from stack into P
For each node X adjacent with P
If X is not marked
Mark X
Push X into stack
4. Queue
Queue
can be implemented by either using arrays or linked lists. The
elements in a queue
are added at one end called the rear and removed from the other one end
called front. The
data are stored in First
In First Out (FIFO) way,
this is the main difference between stack
and queue
•push(x) : add an item x to the back of the queue.
•pop() : remove an item from the front of the queue.
•front() :
reveal/return the most front item
from the queue.
(front
is also known as peek.)
Cicular Queue
•We
can wrap-around
index L and R.
•If R
reach MAXN then set R as zero, do the same to L.
•It is
also known as circular
queue.
Deques
A deque
(pronounced
as ‘deck’ or ‘dequeue’) is
a list in which elements can be inserted
or deleted
at either end. It is also known as a
head-tail linked list, because elements
can
be added to or removed from the front (head)
or back (tail).
Two variants of a double-ended
queue, include:
•Input
restricted deque
In
this dequeue insertions can be done only at one of the dequeue while deletions
can be done
from both the ends.
•Output
restricted deque
In
this dequeue deletions can be done only at one of the dequeue while insertions
can be done
on both the ends.
Priority Queue
A
priority queue is an abstract data type in which the
each
element
is assigned a priority.
The
general rule of processing elements of a priority queue
can
be given as:
•An
element with higher priority is processes before an element with lower priority
•Two
elements with same priority are processed on a first come first served (FCFS)
basis
5. Breadth First Search
Breadth First Search (BFS) like DFS is also an algorithm
for traversing
or searching in a
tree or graph. We
start at the root of the tree (or some arbitrary node in graph)
and explore
all neighboring nodes level per level until we
find the goal.
BFS
has many applications, such as:
•Finding connected component in a
graph.
•Finding shortest path in an unweighted graph.
•Ford-Fulkerson method for computing
maximum flow.
•etc
The
difference between DFS and BFS iterative implementation
is only the data structure
being used.
DFS
uses stack while BFS uses queue.
Algorithm:
Prepare
an empty queue
Push
source/root into queue
Mark
source/root
While
queue is not empty
Pop an item from queue into P
For each node X adjacent with P
If X is not marked
Mark X
Push X into queue
