Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Title: Data Structure and Algorithm
Description: This notes provides an introduction to data structure and algorithms, types of data structures and programming principles. You will learn abstract data type concepts using class and apply ADT concept in the implementation of data structures. Recursive function, algorithm efficiency, order of magnitude analysis and Big O notation will be discussed. You will implement operations that can be applied to data structures using various sorting and searching techniques. Further, you will be exposed to linear data structures such as linked lists, stack and queue. Non-linear data structures such as tree and graphs will also be discussed. At the end of the notes, you should be able to implement and apply the theory and concepts of data structure in the mini project which is conducted in group.
Description: This notes provides an introduction to data structure and algorithms, types of data structures and programming principles. You will learn abstract data type concepts using class and apply ADT concept in the implementation of data structures. Recursive function, algorithm efficiency, order of magnitude analysis and Big O notation will be discussed. You will implement operations that can be applied to data structures using various sorting and searching techniques. Further, you will be exposed to linear data structures such as linked lists, stack and queue. Non-linear data structures such as tree and graphs will also be discussed. At the end of the notes, you should be able to implement and apply the theory and concepts of data structure in the mini project which is conducted in group.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
Stack
by Nor Bahiah Hj Ahmad
Software Engineering Department, FSKSM
bahiah@utm
...
lU d
Understand operations th t can b d
t d
ti
that
be done
on stack
...
2
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
lE
Example: stack of books or
l
k fb k
stack of plates
...
l LAST IN FIRST OUT (LIFO)
data structure
...
my
Example of Stack
p
l Long
g
and narrow driveway
y
– BMW comes in first, Lexus follows, Benz enters in
last
...
l Reverse
a string
Example: TOP , Reverse: POT
E
l
R
l Brackets
balancing in compiler
l Page visited history in a Web browser
Page-visited
l Undo operation in many editor tools
l Check nesting structure
4
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
my
What Is Stack?
l
l
l
l
Stack is an abstract data type
Adding an entry on the top (push)
Deleting an entry from the top (pop)
A stack is open at one end (the top) only
...
6
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
my
Stack implementation
p
l Stack
is an abstract data structure
l Item can be Integer, Double, String, and
also can be any data type such as
type,
Employee, Student…
lH
How t implement a general stack f all
to i l
t
l t k for ll
those types?
l We can implement stack using array or
linked list
...
my
Implementation for Stack
p
Array
l Size of stack is fixed during declaration
l Item can be pushed if there is some space available,
need isFull( ) operations
...
l Stack is empty when the value of Top is –1
...
Linked List
l Size of stack is flexible Item can be pushed and
flexible
...
l Need a pointer, called top to point to top of stack
...
my
Array Implementation of Stack
y p
Stack Operations:
l createStack()
l push(item)
l pop( )
l isEmpty( )
l isFull( )
l stackTop()
top = 2
“Stack can be visualized as
array, BUT the operations
can be done on top stack
only
...
my
Push() and p p() operations
()
pop() p
stack
empty
SCJ 2013/SCK2243
stack
empty
Sept 2009
11
bahiah@utm
...
2
...
Push operations: To insert item into stack
2 statements must be used
top = top + 1;
stack[top] = newitem;
3
...
2 statements should be used
Item = stack[top]; or stackTop();
top = top – 1;
l
Item = stack[top]; statement is needed if we
It
t k[t ]
want to check the value to be popped
...
my
Array Implementation of Stack
y p
Stack declaration:
const int size = 100
100;
class stack
{
p
private : // data declaration
int top ;
char data[size] ;
public : // function declaration
void createStack();
id
t St k()
void push(char) ;
// insert operation
void pop() ;
// delete operation
char stackTop() ; // g
p
get top value
p
bool isFull() ; // check if stack is Full
bool isEmpty(); // check if stack is empty
} ;
13
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
2
...
In this case, stack can
store up to 100 char value
...
my
Array Implementation of Stack
y p
createStack() operation
l Stack
will be created by initializing top to -1
...
15
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
p
p
g
y
l In an array, size of the array is fixed and to create new item in the array
will depend on the space available
...
l bool isFull() implementation
bool stack::isFull()
{
return (top == size-1 );
}
l
Since the size of the array is 100,
bool isFull() will return true, If top is 99 (100 – 1)
...
16
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
l This operation is needed before ANY pop operation can be
done
...
l bool isEmpty() will return true if top –1 and return false
if top is not equal to -1, showing that the stack has element
1,
in it
...
my
Array Implementation of Stack
y p
push(newItem) operation : Insert item onto stack
l push() operation will i
h()
ti
ill insert an it
t
item at th t of stack
...
l I
Insertion operation involve th f ll i steps:
ti
ti i
l the following t
l
Top will be increased by 1
...
my
Array Implementation of Stack
y p
void stack::push(char newitem)
{
if (isFull()) // check whether stack is full
cout << “Sorry,Cannot push item
...
19
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
Function isEmpty() will be called first in order to
ensure that there is item in a stack to be deleted
...
my
Array Implementation of Stack
y p
void stack::pop()
{
char item;
if ( isEmpty() )
cout << “Sorry Cannot pop item
“Sorry,
item
...
my
Array Implementation of Stack
y p
stackTop()operation : to get value at the top
k
()
ti
t
t l
t th t
char stackTop()
{ //function to get top value
if (isEmpty())
cout <<“Sorry, stack is empty!”<< endl;
else
return data[top];
} // end stackTop
22
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
Dynamic memory creation, memory will be assigned to
stack when a new node is pushed into stack, and
memory will be released when an element being
popped from the stack
...
Each node in a stack must contain at least 2 attributes:
i) data – to store information in the stack
...
my
Linked List Implementation of Stack
l
l
l
l
l
l
Basic operations for a stack implemented using linked
list:
li t
createStack() – initialize top
p
push(char) – insert item onto stack
pop() – delete item from stack
isEmpty() – check whether a stack is empty
...
Push and pop operations can only be done at the top
~ similar to add and delete in front of the linked list
list
...
my
Linked List Implementation of Stack:
push() and pop() operations
Create stack
25
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
my
Create Stack and isEmpty()
p y()
l
Creating a stack will initialize top to NULL - showing
g
p
g
that currently, there is no node in the stack
...
bool stack::isEmpty()
{
return (top == NULL);
}
27
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
stack
l Insert item to non empty stack : stack with
value
...
my
push() to empty stack
In this situation the new node being inserted, will become
the first item in stack
...
my
push()to non-empty stack
This operation is similar to inserting element in front of a
linked list
...
STEP 1 : newnode-> next = head;
STEP 2 : head = newnode;
30
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
my
Delete item from stack (pop)
(p p)
l
Pop operation can only be done to non-empty stack
...
If i
in the t k
isEmpty()
()
function return true, pop() operation cannot be done
...
In the figure below, delnode is the pointer variable to point
to the node that is going to be deleted
deleted
...
my
Pop() operation
p() p
void stack::pop()
{ nodeStack *delnode;
if (isEmpty())
cout <<“Sorry, Cannot pop item from
stack
...
my
Check item at top stack
p
int t k
i t stack::stackTop()
t kT ()
{ if (isEmpty())
y,
p y
cout <<“Sorry,Stack is still empty!”
<
return head->data;
} // end check item at top
SCJ 2013/SCK2243
Sept 2009
34
bahiah@utm
...
l Stack is a LIFO data structure
l Can be implemented using array and link list
l Structure of a stack using array and link list
l Basic Operation for a stack
l
l
SCJ 2013/SCK2243
createStack(),Push(),Pop()
stackTop(),isEmpty(),isFull()
Sept 2009
35
bahiah@utm
...
Stack Application
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
l C
Creating simple C l l t
ti
i l Calculator
l Backtracking (example
...
my
Example1: Parantheses Balance
p
l Stack
can be used to recognize a balanced
g
parentheses
...
(a+b), (a/b+c), a/((b-c)*d)
Open and closed parentheses are properly
paired
...
((a+b)*2 and m*(n+(k/2)))
Open and closed parentheses are not
properly paired
...
my
Check for Balanced Parantheses
Algorithm
create (stack);
continue = true;
while ( not end of input string) && continue
{
ch = getch( );
if ch = ‘(’ || ch = ‘)’
{ if ch = ‘(’
h
Push(stack, ‘(’);
else if IsEmpty(stack)
continue = false;
else
Pop(s);
} // end if
} // end while
if ( end of input && isEmpty(stack);
cout << “Balanced
...
” << endl;
39
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
l The open parentheses ‘(’ will be popped from a stack whenever
the closed parentheses ‘)’ is read from string
...
l When reaching the end of the string every “(“ is matched and
string,
(
stack is finally empty
...
l When end of string is reached, there is still ‘(‘ in stack
...
my
Example for Balance Parantheses
Every ( is Insert into stack
Pop ( when found )
3
3
3
3
2
2
2
2
1
1
(
1
1
0
(
0
0
(
Push(()
Push(()
(
Pop()
0
Pop()
Expression a(b(c)) have balance parentheses since when end of
string is found the stack is empty
...
my
Example for ImBalanced Parantheses
Every ( is Insert into stack
Pop ( when found )
3
3
3
3
3
2
2
2
2
2
1
1
(
1
1
1
0
(
0
0
0
0
(
Push(()
Push(()
(
Pop()
Pop()
Pop()->fail
Expression a(b(c))) f does not have balance parentheses => the
>
third ) encountered does not has its match, the stack is empty
...
my
Algebraic expression
g
p
l One
of the compiler’s task is to evaluate
algebraic expression
...
e pression
l 3 algebraic expressions are :
Infix,
I fi prefix and postfix
fi
d
tfi
43
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
g
p
y
The term infix indicates that every binary operators
appears between its operands
...
2
...
Precedence rules
...
P
th
l
44
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
l Example:
l Postfix
: Operator appears after its operand
...
my
Infix, prefix and p
p
postfix
The advantage of using prefix and postfix is that we don’t need
to use precedence rules, associative rules and parentheses
when evaluating an expression
...
my
Converting Infix to Prefix
g
Steps to convert infix expression to prefix:
STEP 1 : Determine the precedence
...
my
Converting Infix to Prefix
g
Another Example:
48
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
my
Converting Infix to Postfix
g
50
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
l Stack operations, such as push(), p p() and
p
,
p
(), pop()
isEmpty() will be used to solve this problem
...
Convert infix to postfix expression
...
Evaluate post
a uate postfix us g stac
using stack
...
my
Converting Infix to Postfix
Algorithm
52
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
...
my
Converting Infix to Postfix :
A * B – ( C + D )+ E
infix
SCJ 2013/SCK2243
stack
Sept 2009
postfix
54
bahiah@utm
...
2
...
4
...
If char read from postfix expression is an operator, pop the first
2 operand in stack and implement the expression using the
following operations:
l pop(opr1) dan pop(opr2)
l result = opr2 operator opr1
p
p
p
Push the result of the evaluation to stack
...
The value is the result of postfix evaluation
...
my
Evaluating Postfix Expression
g
p
SCJ 2013/SCK2243
Sept 2009
56
bahiah@utm
...
my
Evaluating Postfix Expression :
2 7 * 18 - 6 +
postfix
tfi
result
lt
2
SCJ 2013/SCK2243
Sept 2009
stack
t k
2
58
bahiah@utm
...
SCJ 2013/SCK2243
Sept 2009
bahiah@utm
Title: Data Structure and Algorithm
Description: This notes provides an introduction to data structure and algorithms, types of data structures and programming principles. You will learn abstract data type concepts using class and apply ADT concept in the implementation of data structures. Recursive function, algorithm efficiency, order of magnitude analysis and Big O notation will be discussed. You will implement operations that can be applied to data structures using various sorting and searching techniques. Further, you will be exposed to linear data structures such as linked lists, stack and queue. Non-linear data structures such as tree and graphs will also be discussed. At the end of the notes, you should be able to implement and apply the theory and concepts of data structure in the mini project which is conducted in group.
Description: This notes provides an introduction to data structure and algorithms, types of data structures and programming principles. You will learn abstract data type concepts using class and apply ADT concept in the implementation of data structures. Recursive function, algorithm efficiency, order of magnitude analysis and Big O notation will be discussed. You will implement operations that can be applied to data structures using various sorting and searching techniques. Further, you will be exposed to linear data structures such as linked lists, stack and queue. Non-linear data structures such as tree and graphs will also be discussed. At the end of the notes, you should be able to implement and apply the theory and concepts of data structure in the mini project which is conducted in group.