pert 3 - Linked List Implementation II - 2101680123 - MILLIADY KUSNADI THE BU HIAP

Linked List Implementation II

A.      Stack Concept

Stack is an important data structure which stores its elements in an ordered manner

Analogy:

You must have seen a pile of plates where one plate is placed on top of another. When you want to remove a plate, you remove the topmost plate first. Hence, you can add and remove an element (i.e. the plate) only at/from 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.

•         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.

B.       Array Representation

Stack has two variables:

a.     TOP which is used to store the address of the topmost element of the stack

b.     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

C.      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:

a.     One that stores data

b.     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

D.      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.

E.       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

F.        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.

•      Prefix          : operator is written before operands

•      Infix            : operator is written between operands

•      Postfix        : operator is written after operands

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.

G.     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.

H.      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

I.          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.

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

J.        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

K.      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.

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

L.       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

M.    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 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.

N.      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

O.      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.

P.        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.