Data Structures: [2018] 3 - Linked List Implementation - 2101673042

Welcome Back to this Blog!

Now I'd like to use English as this main language for this Blog, but please pardon my mistaken ^_^

In our Third Blog we discuss about

Stack Concept
Stack using Array and Linked List
Infix, Postfix and Prefix Notation
Evaluation
Coversion
Depth First Search
Queue Concept
Queue using Array and Linked List
Priority Queues
Breadth First Search

Let's just start ~

Stack Concept

Stack is an important data structure which stores its elements in an ordered manner
Let we use an analogy to understand what is stack ^_^
Imagine you have pile of plate where you placed one plate on top of the pile of plate.
If you want to take the plate, usually you should pick the topmost plate from the top. In other word you can add and remove an element (in our example the plate) only at or from the one position which is the topmost position

Stack is a linear data structure which can be implemented by either using an array or a linked list. This mean that it has one line of stack
This is a brief example about stack
as you can see, The element 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) or First In Last Out (FILO) way.

Array Representation

Stack has two variables:
1. Top, top is variable that used to store the address of topmost element of the stack
2. Max, max is variable to store the maximum number of element that the stack can hold, in other words max it the number that or array that declared in our code
Example, if you declare int stack[50]; // then you have max = 50;

If the TOP is NULL , it means that the stack you have is empty,
If the TOP = MAX - 1 , then it means the stack is full, do you wondering why
If TOP = MAX - 1 means FULL, not just TOP = MAX then FULL ?

It's because every array has index and it's index is started from zero(0) , and perhaps you already know that the last index in every array is NULL(\0), there for the formula is, FULL = (TOP=MAX-1)

As you can see, the TOP position in index 4(four) and if we set the max of array is 9 then we can add more four data to the stack

Linked List Representation

What is it Linked List ? We have discuss it before please check it , just kidding. Let me explain it again.
With Linked List we can create a stack without using a fixed number or array range number. But the drawback of this Linked List is in small number of data the it may not feel better to use more complicated technique, better we use array but in some advanced programming that require us to store much more data, it's better to use Linked List cause in real life data base imagine you could declare more more more array everyday passed by , is better to use dynamic Linked List that just allocate memory of computer based on the data that comes to input. Do you understood .-. ?

In Linked Stack, every node has two parts:
- One that stores data or it's value
- One that stores the address of the next node

We agreed that the START pointer of the linked list used as the TOP
All insertion and deletions are done at the node pointed by the TOP
If TOP == NULL, once again then it means the stack is empty

We have 7 data and if want to delete or insert data it must be done at the TOP
cause it's stack ! First in Last out || Last in First Out !!

Stack Operations
A linked stack support all three stack operation which is PUSH, POP, and PEEK.

Push Operation
is used to insert an element into the stack. The new element added will be placed at the top most position of the stack.

now please look at this picture bellow (carefully)

If we want to insert an node with value 9 (nine) , we first check if the TOP is NULL. In this case we will allocate memory for a new node, and store it's value to the node data. Because the new node will become the top of the linked list. BUT!, please be minded that if our TOP is NULL then the new node will be the TOP and it's NEXT will be NULL. In our case the updated stack will becomes like this

Pop Operation
The Pop Operation is used to delete the topmost element (node) from a stack. If we want to delete an element, we should check that is (are?) our TOP data is NULL, if that's true, we can not perform such a deletion in the stack because it's empty. Else we can do our deletion. If an attempt is made to delete a value from a stack that is already empty, an UNDERFLOW message is printed.

Let's consider this picture, if we want to pop an element from the TOP node than we should check the node if that NULL or if that empty, cause it's empty then we can perform the deletion on our stack, and our TOP node will assign as the next of the previous TOP node, as this picture

Here is an example of Stack Operations

Let me explain this example ^^
First we have an empty stack. Now our pointer is mark at n which is n = 0
First we'd like to add value 14 as our first stack then we perform push(14)
Then we'd like to add another value which is 25 at our stack thus we perform push(25)
The things is repeated to push(6)
Now we want to remove the last number that we've inputted. Thus we perform pop().
We perform just pop cause in stack the rules is First in Last out.
Top()=25 ? Is perhaps a same function as pop() which is output the last number be have in stack
then we pop() again
and finally we add new value which is 30 then we do push(30).

Stack Applications
There are several applications using stack data structure that we will discuss

Infix evaluation
Postfix evaluation
Prefix evalution
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
- Infrix notation (commonly used)
- Postfix notation, also known as polish notation

You might not understand after all above things, then let's we just talk with an example of it ;)

you might recognize this

4 * 10 ,, this what we called infix notation

if we'd like to make this notation in prefix, according to Ko Sky the formula to make any operand into prefix notation is

operator_left-operand_right-operand

we obtain a prefix of our first infix

* 4 10 ,
* is our operator
4 is our left operand
10 is our right operand

if we'd like to make our infix to postfix, Ko Sky formula is

left-operand_right-operand_operator

then we obtain our postfix as

4 10 * understood? Let's make it more

5 + 3 * 10 , try to make this into prefix and postfix ?
How we do this?
Remember that * has higher precedence then +

start : 5 + 3 * 4
in Prefix
first * 3 4
then + 5 * 3 4
now we have our Prefix notation

in Postfix
first 3 4 *
then 5 3 4 * +
Now we have Postfix

Please remember that every Prefix has operators at the left most
But every Postfix has operators at the right most

Here have a little note given from my source

•Prefix : operator is written before operands

•Infix : operator is written between operands

•Postfix : operator is written after operands

There is a question.
Why do we need prefix / postfix notation?
First both of them doesn't need brackets to priorities operator precedence
and Second both of them is much easier for computer to evaluate

Let say we have expression : 4 + 6 * ( 5 - 2 ) / 3
If we want to evaluate this infix notation, we should search the highest precedence of our operator in the expression

then
4 + 6 * (3) / 3
4 + (18) / 3
4 + (6)
10 , is our result

Now Evaluation : Postfix Notation
Manually scan from left to right
7 6 5 x 3 2 ^ - +    //scan until reach the first operator , remember that postfix operator at the rightmost
7 6 5 x 3 2 ^ - + // calculate 6 x 5 = 30
7 30 3 2 ^ - + // calculate 3^2 = 3x3 = 9
7 30 9 - +    // 30 - 9 = 21
7 21 +    // 7 + 21 = 28
28 , is our result

Let me show you some information, it's not really complete I will describe it below

Evaluation PREFIX NOTATATION
Let say we have this expression
+ 7 - x 6 5 ^ 3 2 // we scan and perform action from right most, then 3^2 = 9
+ 7 - x 6 5 9 // now we have x 6 5 means 6 x 5 = 30
+ 7 - 30 9 // now evaluate calculation 30 - 9 = 21
+ 7 21 // final calculate 7 + 21 = 28
28 // our final result

This below is taken from my source
let me explain this

Conversion: Infix to Prefix Notation

Manually

A + B – C x D ^ E / F , find the highest precedence

A + B – C x ^ D E / F , reevaluate

A + B – C x ^ D E / F , scan another operator,

A + B – x C ^ D E / F , result or re evaluate , then scan

A + B – x C ^ D E / F , re evaluate again

A + B – / x C ^ D E F , it's result, then scan again

A + B – / x C ^ D E F , find another operator

+ A B – / x C ^ D E F , the result, then scan operator again

+ A B – / x C ^ D E F , found and reevaluate again

– + A B / x C ^ D E F , this is the Prefix notation

Depth First Seach
DFS is an algorithm for traversing or searching in a tree or graph. We start at the root of the tree (an node) 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 result may have a little differences on visiting order but both are correct.
via my Source

It has an Algorithm like this

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

Once again this algorithm taken from my Source

It has Visit order : A, C , B , E , D , WHY?
First we have A as our MASTER of TOP tree
as you can see we pop A at picture#2
and we push the node that from the A , push B and push C
now we explore from C and we have C have no root, then we pop the C pop C
now we left have B, now we want to explore B then we pop B pop B
now we examine that are we have root from B , because we have then we push D and push E
after it we want to explore the root, now we pop E first and it has no root then next
we pop D and it has no root too then

our result by the first pop is
A - C - B - E - D

POP , CHECK ROOT , if exist PUSH ? and POP , work from right to left ?
Just like that :D

Other Stack Applications that written in my source
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
----///once again this was taken from my Source//-----

Now we discuss about QUEUE

Queue is an important data structure which store it's elements (Node) in an ordered manner
the manners is FIRST IN FIRST OUT
Example
-People moving on an escalator. People who step in first , step out of it first too
- People waiting for a bus
- Car Lined at a toll bridge
- A real QUEUE , *LOL*

Did you know that Queue can be implemented by array or linked list, their both can adapt queue method mannes.
The elements ub qyeye are added at one end called rear and removed from the other one end called front.
The Mannes as I said FIFO, first in first out. This manner is the main differences in stack and queue :)

Queue in array representation
Queue it self has two variables : front and rear
For Example

In this example, the front index is 0 meanwhile the rear index is 5

Linked List Representation
Similar with stack, but the 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 (value)
- Another parts is that stores the address of the next element
The START pointer of linked list is well known as the FRONT
All insertion will be done at REAR, and all the deletions are done at the front END.

If FRONT = READ = NULL, thet it means our queue is empty

This was taken from my Source

In some variation of code, and matters, you will occurs some problem with queue of an arrray
If you implementing that and it reach the MAXN times array, it will stackoverflow by basicly
and imagine before coder found linked list method, how they deal with this matters
because of this they found Circular Queue