Data Structures

Stack

Stack
A stack is an ordered collection of
items inot which new items may be
added and from which items may be
deleted at one end, called the top of
the stack.

push
pop

Stack operations
push
pop
This stack is called last-in first-out
stack LIFO.
2

Representation of Stack
In 2 ways stack can be represented:
1. Using one-dimensional ARRAY
2. Using single linked list

ARRAY REPRENTATION
3
A[0]

4
A[1]

BASE=0

5
A[2]

6
A[3]

TOP

.
A[max-1]
Upper
limit=
MAX-1

Stack UNDERFLOW: when Top<BASE

Stack OVERFLOW: Top>=MAX-1
Stack Initialization: top= -1

Stack
Representing stacks
s.item[7]

const int SIZE = 8;

struct stack{
int items[SIZE];
int top;
};
s.item[0]
stack s;
s.top = -1; // initialization

s.top
5

Top=1

Top=0

Top=3

1 Stack Over flow

Stack Underflow

Top=-1
6

LINKED LIST
REPRESENTATION OF STACK
push(1) push(3)
1
[213]

push(9)

push(11)

119
3

213
201
9

TOP

119
290
11

201

Stack Operations
1. void Push (S,item)
2. stacktype Pop(S)
3. stacktype Stacktop(S)
4. boolean Isempty(S)
5. boolean Isfull (S)
8

Stack
Push and pop algorithms
Push x
if stack isfull then
stop
else
add x onto a stack
end
Pop
if stack isempty then
stop
else
remove item from a stack
end

Stack
Programming push operation
void push(stack &st, int x)
{
if(st.top == SIZE-1)
{
cout<< Stack overflow;
exit(1);
}
else
st.items[++st.top] = x;
}

7
6
5
4
3
2
1
0
-1

Function call
push(s, 4);
push(s, 33);
10

Stack
Programming pop operation
int pop(stack &st)
{
if(st.top == -1)
{
cout << Stack underflow;
exit(1);
}
else
return st.items[st.top--];
}

12
8
-5
33
4
4

Function call
y = pop(s);
n = pop(s);
11

// stack implementation
#include <iostream.h>
#include <stdlib.h>
#include <ctype.h>
const MAX = 10;

// Length of the stack

struct stack{
int items[MAX];
int top;
};
void push(stack &, int); //prototype for push
int pop(stack &);
//prototype for pop
void main ()
{
stack s;
int item;
char ch;
s.top = -1;
// intializing top to -1
do{
cout<<"select : \n A --- push an item\n B --- pop\n C --- exit\n =>";
cin >> ch; //taking input
ch = toupper(ch);
if (ch=='A') //if PUSH
{
12

cout<<"\n Enter item to push : ";

cin>>item;
push(s, item);
}
if (ch=='B') //if POP
cout << pop(s) <<\n;
}while (ch != C );
}
void push(stack &st, int x)
{
if (st.top == MAX-1)
// if overflow
{
cout<<"\nError : Stack overflow!!\n;"
exit(1)
}
st.top++;
//increment top var
st.items[st.top]=x; //insert the specified value into the stack(array(
}
int pop(stack &st)
{
if (st.top == -1) // if empty
{
cout<<"\nError : Stack empty !!\n;"
exit(1);
}
return st.items[st.top--]; //return the popped value
}

13

Stack Applications
1.

Reversing a line of text

2. Balancing the parentheses

3. Translating an infix expression to postfix
expression
4. Evaluating postfix expression
5. Calling of functions
6. Evaluation Recursion
14

EXAMPLE
R

PUSH one by one

till the end of the
string

POP one by
one till the
stack is empty

I
N
15

Reversing a line of text

Algorithm:

Step1: Read a line of text

Step2: While (character in line ! \0)
push character into the stack
Step3 : While (stack is ! Empty)
pop the character and display
Step 4: Stop

16

PARANTHESIS BALANCING
UNBALANCED EXPRESSION:

((A+B)*(C-D
BALANCED EXPRESSION:
((A+B)*(C-D))
17

Balancing the parentheses

Algorithm:

Step1: Read the expression as a line of text

Step2: While (character in line ! =\0)
{ if (character is left parenthesis)
push character into the stack
else if (character is right parenthesis)
{ if the stack is empty Parentheses are not balanced
pop left parenthesis from the stack
}
}
Step3 : if (stack Isempty)
Parentheses are balanced
else
Parentheses are not balanced
Step 4: Stop

18

MECHANICAL EVALUATION OF
INFIX EXPRESSION
1. Infix expression given by the user is
first converted to postfix expression by
the system, then evaluation takes
place.
2. During the conversion of infix
expression to postfix, stack is used
internally by the system.
19

ARITHMETIC EXPRESSION
INFIX

a operator b

POSTFIX

operator a b

PREFIX a b operator
a,b are two operands
20

EXAMPLE
(infix to PREFIX CONVERSION)
A+B*C/D-E is infix arithmetic expression

In Prefix Expression
step 1:A+(*BC)/D-E
step 2:A+(/*BCD)-E
step 3:(+A/*BCD)-E
Finally , -+A/*BCDE
21

EXAMPLE
(infix To POSTFIX CONVERSION
A+B*C/D-E is infix arithmetic expression

In Postfix form it will be

step 1.A+(BC*)/D-E
step 2.A+(BC*D/)-E
step3.(ABC*D/+)-E
finally, ABC*D/+E22

Performing calculations
To evaluate an expression, such as
1+2*3+4, you need two stacks: one for
operands (numbers), the other for
operators: going left to right,

CONTINUED

23

 If you see a number, push it on the number

stack
If you see an operator,
While the top of the operator stack holds an
operator of equal or higher precedence:

pop the old operator

pop the top two values from the number
stack and apply the old operator to them
push the result on the number stack
push the new operator on the operator
stack
At the end, perform any remaining operations
24

Example: 1+2*3+4

1 : push 1 on number stack

+ : push + on op stack
2 : push 2 on number stack
* : because * has higher precedence
than +, push * onto op stack
3 : push 3 onto number stack
compute 2*3=6, and push 6 onto
number stack
push + onto op stack
continued..

25

 + : because + has lower precedence than

+:
pop 6, 1, and +
Perform 6+1 and Push 7 onto the
number stack and + onto the operator
stack
4 : push 4 onto number stack
end : pop 4, 7 and +, compute 7+4=11,
11 (at the top of the stack) is the answer
26

Some things that can go wrong

The expression may be ill-formed:
2+3+
When you go to evaluate the second +, there
wont be two numbers on the stack
12+3
When you are done evaluating the expression,
you have more than one number on the stack
(2 + 3
You have an unmatched ( on the stack
2 + 3)
You cant find a matching ( on the stack
The expression may use a variable that has not been
assigned a value

27

Infix to Postfix Conversion

28

29

Evaluating Postfix Expressions

30

Evaluating Postfix Expressions

31

Evaluating Postfix Expressions

32

What is Recursion?
It is the use of functions that call
themselves. A recursive function
repeatedly calls itself directly or
indirectly until a termination
condition is met.
By calling itself repeatedly a
recursive function achieves
repetition of a code section.
33

 Usually
functions
calls
are
computationally costly; therefore
recursion is recommended only in
naturally recursive cases such as
computing the factorial of a
number.

34

Factorial of a number?
The factorial of
5 = !5
or 5 x 4 x 3 x 2 x 1
10 = !10
or 10 x 9 x 8 x 7 x 6 x 5 x 4
x3x2x1
In the above case 5! Could be expressed
as
5 * (4!)
Or
5 * 4* (3!)
Or 5 * 4 * 3 * (2!)
Or 5 * 4 * 3 * 2 * 1
So you can see that once we know how to
work out the factorial it is just a matter of
calling that process repeatedly.

35

ITERATION VERSION OF A FACTORIAL

void factorial (long number)
{
int fact = 1;
for (int i = 1; i<= number; i++ )
{
fact = fact* i;
printf( \n %d! = %d , i, fact);
}
}
Output
1! = 1
2! = 2
3! = 6
4! = 24

36

RECURSION VERSION OF A
FACTORIAL
Int factorial ( int number)
{
if (number <= 1)
{
printf(\n %d, number);
return 1;
}
else
{
printf(\n %d , number);
return (number * factorial(number 1);
}
}
e.g- 4x3x2x1=24

37

Iteration Vs Recursion
Both involve a termination test
With Iteration until the loop-continuation
condition fails
With Recursion until a value is less than
to equal to 1
Recursion has many negatives it can be
expensive both in processor time and
memory space. Each recursive call causes
another copy of the function variables to be
38
created.

 Iteration normally occurs within a

function so the overhead of repeated
function calls and extra memory is
omitted.

39

Iteration Vs Recursion
So why choose recursion ?

A recursive approach is normally chosen in

preference to an iterative approach when the
recursive approach naturally mirrors the
problem and results in a program that is easier
to understand and debug. Another reason for
choosing recursion is that an iterative solution
may not be apparent.
The important point to remember about
recursion is that it doesnt suit every problem
so normally chosen for problems that are
40
naturally recursive such as Fibonacci.

How Recursion Works

Each call of a method generates an instance of
that method

An instance of a method contains

memory for each parameter
memory for each local variable
memory for the return value
a pointer to the callers next instruction (return
address)

This chunk of memory is also called an

activation record
41

Example: factorial(4)
int factorial (int n)
{
if (n == 1)
return 1;
else
return n *
factorial (n - 1);
}
n
return value

Activation record for factorial(4)

42

int factorial (int n){

if (n == 1)
return 1;
else
return n * factorial (n-1);
}

n
return value

n
return value

Activation record for factorial(3)

Activation record for factorial(4)

43

Number of Activations = # Calls

n
return value

n
return value

n
return value

Activation record for factorial(2)

Activation record for factorial(3)

Activation record for factorial(4)

44

Recursive Process Bottoms out

n
return value

n
return value

n
return value

n
return value

Activation record for factorial(1)

Activation record for factorial(2)

Activation record for factorial(3)

Activation record for factorial(4)

45

Recursive Process Unwinds

n
return value

n
return value

n
return value

n
return value

Activation record for factorial(1)

Activation record for factorial(2)

Activation record for factorial(3)

Activation record for factorial(4)

46

Activations Are Deallocated

n
return value

n
return value

n
return value

Activation record for factorial(2)

Activation record for factorial(3)

Activation record for factorial(4)

47

Activations Are Deallocated

n
return value

n
return value

Activation record for factorial(3)

Activation record for factorial(4)

48

Value Returned
in the First Activation

n
return value

4
24

Activation record for

factorial(4)

49