Pertemuan 3-Linked List: Implementation II-2101640952-Stephanus Nico Budiarso

Stack
Stack concept is Last In, First Out (LIFO).

Stack Using Array and Linked List 

1. Array
Top is the topmost data of the stack. Max is the maximum number of elements that the stack can hold.

If TOP=NULL, then means the stack is empty.
If TOP=MAX-1, then the stack is full.
If TOP=0, then the stack have one data.

2. Linked List
In a linked list stack, every node has two parts:
- one that stores data
- one that stores the address of the next node (pointer to the next node).

If TOP=NULL, then means the stack is empty.

Stack Operation
- push(x) : add x to the top of stack
- pop() : remove the top data of stack
- top() : reveal the top data of stack.

Example:

Prefix, Infix, Postfix
Prefix: Operator is written before operands.
Syntax: operator, left operand, right operand.

Infix: Operator is written between operands.
Syntax: left operand, operator, right operand.

Postfix: Operator is written after operands.
Syntax: left operand, right operand, operator.

Example:

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

Depth First Search

Using the stack concept.

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

Queue

Queue concept is First In, First Out (FIFO).

Queue Operation

- push(x) : add x to the back of queue.

- pop() : remove the front data of queue.

- front() or peek() : reveal the most front data of queue.

Example:

Breadth First Search

Using queue concept.

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