pertemuan3-Stack-ihsan-2101660790

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 has two variables:

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

•      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

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.

Infix, Postfix, and Prefix Notation

•      Prefix             : operator is written before operand

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

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

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

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.