Stack Concept
Stack is a linear data structure which can be implemented by either using an array or a linked list.
The elements in a stack are added and removed only from one end, which is called the top.
The data are stored in Last In First Out (LIFO) way.
Array Representation
Stack has two variables:
TOP which is used to store the address of the topmost element of the stack
MAX which is used to store the maximum number of elements that the stack can hold
If TOP = NULL, then indicates that the stack is empty
If TOP = MAX – 1, then the stack is full
0 1 2 3 4 5 6 7 8
TOP=4, insertion and deletion will be done at this position
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.
Stack Applications
There are several applications using stack data struct :
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
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
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
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
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 / +
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 ,
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.
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:
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
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
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
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.
Circular Queue Queue Applications
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
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
Tidak ada komentar:
Posting Komentar