Data Structures & Algorithms

Lecture # 3
Today Topics
 What are Stacks?

 Representation of Stacks

 Operations on Stacks
 Push
 Pop

 Evaluation of Expressions

 Infix to Postfix Conversion

Stack application
 Function calls
 Reversing Data: We can use stacks to reverse data.
(example: files, strings)
Very useful for finding palindromes.
Consider the following pseudocode:
1) read (data)
2) loop (data not EOF and stack not full)
1) push (data)
2) read (data)
3) Loop (while stack notEmpty)
1) pop (data)
2) print (data)
Stack application
What are Stacks?
 In array insertion and deletion can take place at
both end, i.e. start and end,
 But if insertion and deletion are restricted from one
end, must used STACKS , QUEUES.

Stack can be defined as:

 A stack is a linear data structure which can

be accessed only at one of its ends for
storing and retrieving data. OR
 In which item may b inserted or deleted only at one
end called top of the stack.
 There are two ways of implementing a stack:
 Array (Static)
 Link List (Dynamic)
Example of Stack
 A common model of a
stack is a plate or coin
stacker. Plates are
"pushed “onto to the top
and "popped" off from the
top.

 Stacks form Last-In-First-

Out (LIFO) queues.
 Stack terminology

“Top”: end where insertion and

deletion take place
“Push”: is the term used to insert an
element into an array

“Pop”: is the term used to delete an

element from a stack.
Basic operations of a Stack
New Push

?
Pop Peek

Empty ?
Array implementation of Stacks

 A stack can be implemented with an array

and an integer.

 A pointer variable TOP which contains the

location of the top element of the stack;
 Variable MAXSTK which gives the maximum
number of elements that can be held by the
stack.
 Condition TOP=0, or MAXSTK=NULL
indicate that the stack is empty.
 Stack implemented in an array
 Note that all operations need check array
bounds
 Pushing onto a full stack: Overflow
 When TOP=MAXSTK
 Popping an empty stack: Underflow
 TOP=NULL
Operations on Stack
 A stack is generally implemented with only two
principle operations (apart from a constructor
and destructor methods):

 initializeStack: initializes the stack to an empty state

 destroyStack: Removing all the element 4m the stack
 Is EmpthyStack: check whether stack is empty or
not, and return true or false.
 IsFullStack: returns true if full else false.
 Top: returns the top elements of the stack;
 Push: adds an item to a stack
 Pop: extracts the most recently pushed item from the
stack
How the stack routines work
empty stack; push(a), push(b); pop

a a a

empty stack push(a) push(b) pop()

top = 0 top = 1 top = 2 top = 1
Implementation of the operation
 Initialize Stack:
 Destroy Stack:
 EmpthyStack:
 Full Stack:
 Top: returns the top elements of the stack;
 Push: tow step process, adding and
incrementing the top pointer.
 Pop: extracts the most recently pushed item
from the stack
Algorithms of Push Operation
Push (STACK , TOP, MAXST, ITEM)
Algorithm for push element into the Stack

1. [stack already filled]

If TOP= MAXSTK, then: print: “OVERFLOW”,
and return.
2. [increases TOP by 1] Set TOP:= TOP + 1
3. [insert ITEM in new TOP position ]
Set STACK[TOP]: =ITEM
4. RETRUN
Algorithms of Pop Operation
Pop (STACK, TOP, ITEM)
Algorithm for pop element from the Stack
1. [Stack has an item to be removed]
If TOP= NUL, then
Print: “UNDERFLOW” and return
2. [assign TOP element to ITEM]
Set ITEM := STACK[TOP]
3. [Decrease TOP by 1]
Set TOP:= TOP -1
4. Return
Algorithm for Display Stack
elements
Display_Stack ()
Algorithm for display stack elements
1. Start
2. Repeat step 3 For i = 1 to TOP by 1
3. Print S[i]
4. End
Algorithm for isempty Stack
isempty ()
Algorithm for return the Stack status
1. Start
2. if TOP = 0 then
Return True
else
Return False
3. End
Algorithm for return the top of
stack value
top ()
Algorithm for return the top of Stack
value
1. Start
2. Return TOP
3. End
Evaluation of Expression
 Arithmetic expression is made up
 Operands (Numeric Variables or
Constants)
 Arithmetic Operators (+, -, *, /)
 Power Operator (^)
 Parentheses

 The Expression is always evaluated

from left to right
Evaluation of Expression
 Order in which the expression is evaluated is:

 If the expression has parenthesis, then they are

evaluated first

 Exponential (^) is given highest priority

 Multiplication (*) and division (/) have the next

highest priority

 Addition (+) and subtraction (-) have the lowest

priority
Evaluation of Expression
 Steps to evaluate the following expression:

 (2^3 + 6) * 2 – 9 / 3

 = (8 + 6) * 2 – 9 / 3

 = 14 * 2 – 9 / 3

 = 28 – 3

 = 25
Infix, Prefix (Polish) and Postfix
(Reverse Polish) Notation
Infix Prefix Postfix
(Polish Notation) (Reverse Polish
Notation)
A+B +AB AB+

A*B *AB AB*

A/B /AB AB/

A-B -AB AB-

Evaluation of Expression
 Computer evaluates an expression given in infix notation by
converting it into postfix notation.

 Stack is used to perform this operation

 Following steps are take to evaluate a postfix expression:

 Expression is scanned from left to right until the end of the expression

 When an operand is encountered, it is pushed into stack

 When an operator is encountered, then

 Top two operands of stack are removed
 Arithmetic operation is performed
 Computed result is pushed back to the stack

 When end of the expression is reached, the top value from the stack is
picked. It is the computed value of the expression
Infix to Postfix Conversion
 Stack is used to convert an infix expression to postfix.

 Stack is used to store operators and operands and then pass to

the postfix expression according to their precedence.

 Infix expression is converted into postfix expression according to

the following rules:

 Infix expression is scanned from left to right until end of the

expression.

 Operands are passed directly to the output.

 Operators are first passed to the stacks.

 Operand is encountered, it is added to the output.

Infix to Postfix Conversion
 Each time an operator is read, the stack is repeatedly
popped and operands are passed to the output, until an
operator is reached that has a lower precedence than the
most recently read operator. The most recently read
operator is then pushed onto the stack.

 When end of the infix expression is reached, all operators

remaining in the stack are popped and passed to the
output in the same sequence.

 Parentheses can be used in the infix expression but these

are not used in the postfix expression.

 During conversion process, parentheses are treated as

operators that have higher precedence than any other
operator.
Infix to Postfix Conversion
 Left parenthesis is pushed into the stack, when
encountered.

 Right parenthesis is never pushed to the stack.

 Left parenthesis is popped only when right

parenthesis is encountered.

 The parentheses are not passed to the output postfix

expressions. They are discarded.

 When end of expression is reached, then all

operators from stack are popped and added to the
output.
Example (Infix to Postfix
Conversion)
Convert infix expression A+B*C+
(D*E+F)*G into postfix

A+B*C+(D*E+F)*G

1. Scanned from left to right. First

operand read is A and passed to
output

Stack

Output: A
Example (Infix to Postfix
Conversion)
A+B*C+(D*E+F)*G

2. Next the ‘+’ operator is read, at

this stage, stack is empty.
Therefore no operators are
popped and ‘+’ is pushed into the
stack. Thus the stack and output
will be:

Stack

Output: A
Example (Infix to Postfix
Conversion)
A+B*C+(D*E+F)*G

3. Next the ‘B’ operand is read and

passed to the output. Thus the
stack and output will be:

Stack

Output: AB
Example (Infix to Postfix
Conversion)
A+B*C+(D*E+F)*G

4. Next the ‘*’ operator is read, The

stack has ‘+’ operator which has
lower precedence than the ‘*’
operator. Therefore no operators
are popped and ‘*’ is pushed into
the stack. Thus the stack and
output will be:
*
+

Stack

Output: AB
Example (Infix to Postfix
Conversion)
A+B*C+(D*E+F)*G

5. Next the ‘C’ operand is read and

passed to the output. Thus the
stack and output will be:

*
+

Stack

Output: ABC
Example (Infix to Postfix
Conversion)
A+B*C+(D*E+F)*G

6. Next the ‘+’ operator is read, The

stack has ‘*’ operator which has
higher precedence than the ‘+’
operator. The Stack is popped and
passed to output. Next stack has
‘+’ operator which has same
precedence than the ‘+’ operator.
The Stack is popped and passed to
output. Now stack is empty,
therefore no operators are popped
and ‘+’ is pushed into the stack. +
Thus the stack and output will be:
Stack

Output: ABC*+
Example (Infix to Postfix
Conversion)
A+B*C+(D*E+F)*G

7. Next the left parenthesis ‘(’ is

read, Since all operators have
lower precedence than the left
parenthesis, it is pushed into the
stack. Thus the stack and output
will be:

(
+

Stack

Output: ABC*+
Example (Infix to Postfix
Conversion)
A+B*C+(D*E+F)*G

8. Next the ‘D’ operand is read and

passed to the output. Thus the
stack and output will be:

(
+

Stack

Output: ABC*+D
Example (Infix to Postfix
Conversion)
A+B*C+(D*E+F)*G

9. Next the ‘*’ operator is read.

Now, left parenthesis ‘(‘ has
higher precedence than ‘*’; it can
not be popped from the stack
until a right parenthesis ‘)’ has
been read. Thus the stack is not
popped and ‘*’ is pushed into the *
stack. Thus the stack and output
will be: (
+

Stack

Output: ABC*+D
Example (Infix to Postfix
Conversion)
A+B*C+(D*E+F)*G

10. Next the ‘E’ operand is read and

passed to the output. Thus the
stack and output will be:

*
(
+

Stack

Output: ABC*+DE
Example (Infix to Postfix
Conversion)
A+B*C+(D*E+F)*G

11. Next the ‘+’ operator is read, The

stack has ‘*’ operator which has
higher precedence than the ‘+’
operator. The Stack is popped
and passed to output. Next stack
has left parenthesis ‘(’ which has
not been popped and ‘+’ operator +
is pushed into the stack. Thus the
stack and output will be: (
+

Stack

Output: AB*+DE*
Example (Infix to Postfix
Conversion)
A+B*C+(D*E+F)*G

12. Next the ‘F’ operand is read and

passed to the output. Thus the
stack and output will be:

+
(
+

Stack

Output: ABC*+DE*F
Example (Infix to Postfix
Conversion)
A+B*C+(D*E+F)*G

14. Next the ‘*’ operator is read, The

stack has ‘+’ operator which has
lower precedence than the ‘*’
operator. Therefore no operators
are popped and ‘*’ is pushed into
the stack. Thus the stack and
output will be:
*
+

Stack

Output: ABC*+DE*F+
Example (Infix to Postfix
Conversion)
A+B*C+(D*E+F)*G

15. Next the ‘G’ operand is read and

passed to the output. Thus the
stack and output will be:

*
+

Stack

Output: ABC*+DE*F+G
Example (Infix to Postfix
Conversion)
A+B*C+(D*E+F)*G

16. The end of expression is

encountered. The operators are
popped from the stacked and
passed to the output in the same
sequence in which these are
popped. Thus the stack and
output will be:

Stack

Output: ABC*+DE*F+G*+
Example (Evaluation of Expression)
Postfix Expression

ABC*+DE*F+G*+

A=5, B=6, C=9, D=2, E=4, F=8, G=3

2. Scanned from left to right. In first,

second and third iteration, the value
of A, B and C are pushed into the
stack. Thus the stack will be: 9
6
5

Stack
Example (Evaluation of Expression)
Postfix Expression

ABC*+DE*F+G*+

A=5, B=6, C=9, D=2, E=4, F=8, G=3

2. In fourth iteration, the operator ‘*’ is

read. So the two values ‘9’ and ‘6’
are popped from the stack and
multiplication is perform. i.e 9*6=54.
The computed value pushed back to 54
the stack. Thus the stack will be:
5

Stack
Example (Evaluation of Expression)
Postfix Expression

ABC*+DE*F+G*+

A=5, B=6, C=9, D=2, E=4, F=8, G=3

3. In fifth iteration, the operator ‘+’ is

read. So the two values ‘54’ and ‘5’
are popped from the stack and
addition is perform. i.e 54+5=59.
The computed value pushed back to
the stack. Thus the stack will be:
59

Stack
Example (Evaluation of Expression)
Postfix Expression

ABC*+DE*F+G*+

A=5, B=6, C=9, D=2, E=4, F=8, G=3

4. In sixth and seventh iteration, the

value of D and E are pushed into the
stack. Thus the stack will be:
4
2
59

Stack
Example (Evaluation of Expression)
Postfix Expression

ABC*+DE*F+G*+

A=5, B=6, C=9, D=2, E=4, F=8, G=3

5. In eighth iteration, the operator ‘*’ is

read. So the two values ‘4’ and ‘2’
are popped from the stack and
multiplication is perform. i.e 2*4=8.
The computed value pushed back to 8
the stack. Thus the stack will be:
59

Stack
Example (Evaluation of Expression)
Postfix Expression

ABC*+DE*F+G*+

A=5, B=6, C=9, D=2, E=4, F=8, G=3

6. In ninth iteration, the value of F is

pushed into the stack. Thus the stack
will be:
8
8
59

Stack
Example (Evaluation of Expression)
Postfix Expression

ABC*+DE*F+G*+

A=5, B=6, C=9, D=2, E=4, F=8, G=3

7. In tenth iteration, the operator ‘+’ is

read. So the two values ‘8’ and ‘8’
are popped from the stack and
addition is perform. i.e 8+8=16. The
computed value pushed back to the 16
stack. Thus the stack will be:
59

Stack
Example (Evaluation of Expression)
Postfix Expression

ABC*+DE*F+G*+

A=5, B=6, C=9, D=2, E=4, F=8, G=3

8. In eleventh iteration, the value of G

is pushed into the stack. Thus the
stack will be:
3
16
59

Stack
Example (Evaluation of Expression)
Postfix Expression

ABC*+DE*F+G*+

A=5, B=6, C=9, D=2, E=4, F=8, G=3

9. In twelve iteration, the operator ‘*’ is

read. So the two values ‘3’ and ‘16’
are popped from the stack and
multiplication is perform. i.e
3*16=48. The computed value 48
pushed back to the stack. Thus the
stack will be: 59

Stack
Example (Evaluation of Expression)
Postfix Expression

ABC*+DE*F+G*+

A=5, B=6, C=9, D=2, E=4, F=8, G=3

10. In thirteen iteration, the operator ‘+’

is read. So the two values ‘48’ and
‘59’ are popped from the stack and
addition is perform. i.e 48+59=107.
The computed value pushed back to
the stack. Thus the stack will be:
107

Stack
Example (Evaluation of Expression)

A+B*C+(D*E+F)*G

A=5, B=6, C=9, D=2, E=4, F=8, G=3

= 5 + 6 * 9 + (2 * 4 + 8) * 3

= 5 + 54 + (8 + 8) * 3

= 59 + 16 * 3

= 59 + 48

=107
Next Lecture
 What are Queues?

 Representation of Queues

 Operations on Queues
 QInsert
 QDelete
References

 Structures: A Pseudocode Apporoach with C. Gilberg, Richard

F., Forouzan, Data Behrouz A.. PWS Publishing Company:
1998