3- Linked list implementation 2

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(N²) 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 3²

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(N²)

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:

1. Search for the operator which has the highest precedence
2. Put that operator behind the operands
3. 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:

1. Search for the operator which has the highest precedence
2. Put that operator before the operands
3. 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