Stacks
Data yang di simpan dan menggunakan sistem Last In First Out (LIFO)
>Stack memiliki 2 variabel :
-TOP dimana address yang menyimpan data paling atas disimpan
-MAX dimana address yang menyimpan maksimal elemen yang bisa ditampung
>jika TOP = NULL, maka elemen tersebut kosong
>jika TOP = MAX - 1, maka elemen yang tersimpan penuh
Stack Application
-Infix evaluation
-Postfix evaluation
-Prefix evaluation
-Infix to Postfix conversion
-Infix to Prefix conversion
-Depth First Search
Linked List
Representation
•
Technique
of creating a stack using array is easier, but the drawback is that the array
must be declared to have some fixed size.
•
In
a linked stack, every node has two parts:
–
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.
Note: top is also known as peek.
Example of
Stack Operations
Stack
Applications
There are
several applications using stack data
structure
that we will discuss:
•
Infix
evaluation
•
Postfix
evaluation
•
Prefix
evaluation
•
Infix
to Postfix conversion
•
Infix
to Prefix conversion
•
Depth
First Search
Infix,
Postfix, and Prefix Notation
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.
Postfix
notation was given by Jan Lukasiewicz who was a Polish
logician,
mathematician, and philosopher. His aim was to develop
a
parenthesis-free prefix notation (also known as Polish notation)
and a
postfix notation which is better known as the Reverse Polish
Notation or
RPN.
Infix,
Postfix, and Prefix Notation
Prefix : operator is written before operands
Infix : operator is written between operands
Postfix : operator is written after operands
Infix,
Postfix, and Prefix Notation
Why do we
need prefix/postfix notation?
•
Prefix
and postfix notations don’t need brackets to prioritize operator precedence.
•
Prefix
and postfix is much easier for computer to evaluate.
Evaluation:
Infix Notation
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
In each
search, we should iterate through the string and we do this
for each
existing operator, so the overall complexity is O(N2) with N
is the
string’s length.
Evaluation:
Postfix Notation
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
Evaluation:
Postfix Notation
Using Stack
Evaluating
a postfix notation can be done in O(N), which is faster
than O(N2)
Algorithm:
Scan the
string from left to right, for each character in the string:
•
If
it is an operand, push it into stack.
•
If
it is an operator, pop twice (store in variable A and B respectively) and
push(B operator A).
Pay attention here! It is (B
operator A), not (A operator B).
The result
will be stored in the only element in stack.
Evaluation:
Postfix Notation
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
Evaluation:
Prefix Notation
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
Evaluation:
Prefix Notation
Using Stack
Evaluating
a prefix notation is similar to postfix notation.
Hint: the
string is scanned from right to left.
You can do
it by yourself.
Conversion:
Infix to Postfix Notation
Manually
Algorithm:
- Search for the operator which has the highest
precedence
- Put that operator behind the operands
- Repeat until finish
Conversion:
Infix to Postfix Notation
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
Conversion:
Infix to Postfix Notation
Using Stack
Given an
infix expression, convert it into postfix notation. It can be
done in
O(N).
Algorithm:
Scan the
string from left to right, for each character in the string:
•
If
it is an operand, add it to the postfix string.
•
If
it is an open bracket, push it into stack.
•
If
it is a close bracket, pop the stack until you found an open bracket. Add each
popped element to the postfix string.
•
If
it is an operator, pop while the stack’s top element has higher or equal
precedence than the scanned character. Add each popped element to the postfix
string. Push the scanned character into stack.
After you
have scanned all character, pop all elements in stack and add
them to
postfix string.
Conversion:
Infix to 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 Notation
Manually
Algorithm:
- Search for the operator which has the highest
precedence
- Put that operator before the operands
- Repeat until finish
Conversion:
Infix to Prefix Notation
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
Conversion:
Infix to Prefix Notation
Using Stack
It is quiet
similar with the conversion from Infix to Postfix.
You can
learn it by yourself
Depth First
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 before
backtracking.
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.
Depth First
Search
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
Depth First
Search
Visit
order: A, C, B, E, D
Other Stack
Applications
Stacks are
widely used to:
•
Reverse
the order of data
•
Convert
infix expression into postfix
•
Convert
postfix expression into infix
•
Backtracking
problem
•
System
stack is used in every recursive function
•
Converting
a decimal number into its binary equivalent
Queue
•
Queue
is an important data structure which stores its elements in an ordered manner
•
Example:
–
People
moving on an escalator. The people who got on the escalator first will be the
first one to step out of it.
–
People
waiting for a bus. The person standing in the line will be the first one to get
into the bus
–
Luggage
kept on conveyor belts
–
Cars
lined for filling petrol
–
Cars
lined at a toll bridge
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.
Array
Representation
•
Queue
has two variables:
–
Front and rear that point to the position where
deletions and insertions can be done respectively
•
For
examples:
Here, front
= 0 and rear = 5.
Linked List
Representation
•
Similar
with stack, technique of creating a queue using array is easy, but its drawback
is that the array must be declared to have some fixed size.
•
In
a linked queue, every element has two parts
–
One
that stores the data
–
Another
that stores the address of the next element
•
The
START pointer of the linked list is used as the FRONT
•
All
insertions will be done at the REAR, and all the deletions are done at the
FRONT end.
•
If
FRONT = REAR = NULL, then it indicates that the queue is empty
Queue
Operations
•
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.
Example of
Queue Operations
Queue
Using the
previous implementation, what will happen if we push MAXN times and pop MAXN
times, and we try to push another data into the queue?
Yes, we can
not do that. The R index will overflow (exceeding MAXN), which means the new
data will be stored outside the array range.
It seems
very inefficient, how to deal with this?
Circular
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.
Circular
Queue
Queue
Applications
There are
several applications using queue data
structure
that we will discuss:
•
Deques
•
Priority
Queues
•
Breadth
First Search
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).
Deques
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
Priority
Queue
Priority
queue after insertion of a new node:
Lower
priority number means higher priority.
Deletion:
Deletion is
a very simple process in this case. The first node of the
list will
be deleted and the data of that node will be processed first
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.
Breadth
First Search
The
difference between DFS and BFS iterative
implementation
is only the data structure being used.
DFS uses
stack while BFS uses queue.
Breadth
First Search
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
Breadth First
Search
Visit
order: A, B, C, D, E
Summary
Stack is an
important data structure which stores its elements in an ordered manner.
Stack is a
linear data structure which can be implemented by either using an array or a
linked list.
The data
are stored in Last In First Out (LIFO) way
Summary
There are
three arithmetic notations: Prefix notation, Infix notation, Postfix notation
Prefix : operator is written before operands
Infix : operator is written between operands
Postfix : operator is written after operands
Depth First
Search (DFS) is an algorithm for traversing or searching in a tree or graph
Summary
Queue is an
important data structure which stores its elements in an ordered manner
Queue can
be implemented by either using arrays or linked lists.
The data
are stored in First In First Out (FIFO) way
Summary
A deque (pronounced as ‘deck’ or ‘dequeue’) is a
list in which elements can be inserted or deleted at either end
A priority
queue is an abstract data type in which the each element is assigned a
priority.
Breadth
First Search (BFS) like DFS is also an algorithm for traversing or searching in
a tree or graph
