3 - Linked List Implementation II - 2101702130 - Andrean

Pertemuan ke - 3
13-03-2018

Stack

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

Simplest logic is Last In First Out (LIFO) way. The elements in a stack are added and removed 

only from one end, which is called the top.

In a linked stack, every node has two parts:

– One that stores data

– One that stores the address of the next node

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. //top is also known as peek

Infix, Postfix , and  Prefix Notation

Prefix	Infix	Postfix
* 4 10	4 * 10	4 10 *
+ 5 * 3 4	5 + 3 * 4	5 3 4 * +
+ 4 / * 6 – 5 2 3	4 + 6 * (5 – 2) / 3	4 6 5 2 – * 3 /  +

Prefix: Operator, Left Operand , Right Operand (OLR)
Infix : Left Operand , Operator , Right Operand (LOR)
Postfix : Left Operand , Right Operand ,Operator (LRO)

Evaluation

Infix Notation

To evaluate infix notation, we should search the highest precedence

operator in the string.

4 + 6 * (5 – 2) / 3  it is ( )

4 + 6 * 3 / 3  it is *

4 + 18 / 3   it is  /

4 + 6   it is +

10

Postfix Notation

Manual

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    

Using Stack

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

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

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

Using stack 

Similar with postfix but scanned from right to left.

Infix To Postfix Notation

Manual

1.Search for the operator which has the highest precedence

2.Put that operator behind the operands

Using Stack

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.

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 / +

Infix to Prefix Notation

Manual

1.Search for the operator which has the highest precedence

2.Put that operator before the operands

Using Stack

Similar with Infix to Postfix but start from behind and must reverse the result.

Queue

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

Simplest logic is First In First Out (FIFO) . The element added from rear and removed from front.

In a linked queue, every element has two parts

- One that stores the data

- Another that stores the address of the next element

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.

Priority Queue

•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 

Delete

The peek(front) data will be deleted.

2101702130 - Andrean