Abstract Data Types (ADTs)

(Stack)
 Abstract Data Types
 A data type can be considered abstract when it is defined
in terms of operations on it, and its implementation is
hidden.

 An Abstract Data Type is some sort of data together with set

of functions (interface) that operate on the data.

The concept of Abstraction means:

1. We know what a data type can do.
2. How it is done is hidden.
 Ex. Stack, Queue, Tree, and Graph.
 Stack ADTs

A stack is a data structure where an element that entered

the first would be the last to come out (Last In First Out
data structure or LIFO). Ex: pile of books.
 Stack Operations
 There are five basic operations, stack, push, pop, top and
empty.

 In stacks, insertion and deletion takes place at the same

place called top.

 Inserting an element into a stack is called push operation.

 Deleting an element from the stack is called pop

operation.
 Stack Primitive Operations
The following operations can be applied to a stack:

Stack(): creates an empty stack.

Push (Element): pushes an Element on the top of stack.

Pop(Stack): removes the top Element from the stack.

Top(Stack): returns the first Element from the stack without

removing it.

Empty(Stack): returns true if stack is empty.

 Implementation of Stacks

 Static Implementation
 Stack is represented as an array

 Dynamic Implementation
 Stack is represented as a linked list
 Push operation
Initially stack is assumed to be empty --- >
top=-1
Now, increment top
Then push the element

4 50
3
40 40
2
1 30 30 30
20 20 20 20
0 10 10 10 10 10
top

Initial value of top=-1 final value of top=4

i.e, top should not exceed max – 1 in array implementation.

 Pop Operation
Pop operation always pops the top most element.
Steps: top
Pick up the topmost element 50
int element; 40
element=stack[top]; before 30
top--; pop 20
return element; 10

Here top=4
stack[top]=50 top 40
Now decrement top by 1 as 30
one value is reduced 20
So, pop function returns the value after 10
pop
 Stacks using arrays – push() and pop()
 int StackArray[5]; // StackArray can contain up to 50 numbers
 int top=-1; // index of the top element of the stack
 // -1 used to indicate an empty stack

 void push(int element)

 {
 top++;
 StackArray[top] = element;
 }

 int pop()
 {
 int element = StackArray[top];
 top--;
 return element;
 }
What will be the contents of the stack after
the following sequence of operations?
push(A)
push(B)
pop
push(C)
push(D)
push(E)
pop
pop stack

pop
pop
 What will be the contents of the stack after the
following sequence of operations?
push(A)
push(B)
pop
push(C)
push(D)
push(E)
A
pop
pop stack

pop
pop
 What will be the contents of the stack after the
following sequence of operations?
push(A)
push(B)
pop
push(C)
push(D)
B
push(E)
A
pop
pop stack

pop
pop
 What will be the contents of the stack after the
following sequence of operations?
push(A)
push(B)
pop
push(C)
push(D)
push(E)
A
pop
pop stack

pop
pop
 What will be the contents of the stack after the
following sequence of operations?
push(A)
push(B)
pop E
push(C) D
push(D)
C
push(E)
A
pop
pop stack

pop
pop
 What will be the contents of the stack after the
following sequence of operations?
push(A)
push(B)
pop
push(C) D
push(D)
C
push(E)
A
pop
pop stack

pop
pop
 What will be the contents of the stack after the
following sequence of operations?
push(A)
push(B)
pop
push(C)
push(D)
C
push(E)
A
pop
pop stack

pop
pop
 What will be the contents of the stack after the
following sequence of operations?
push(A)
push(B)
pop
push(C)
push(D)
push(E)
A
pop
pop stack

pop
pop
 What will be the contents of the stack after the
following sequence of operations?
push(A)
push(B)
pop
push(C)
push(D)
push(E)
pop
pop stack

pop
pop
Applications of Stacks
 Applications of Stacks

Stacks are extensively used in computer

applications-system software like compilers,
operating systems etc.

Used in function calls, parameters are passed

through stacks.

Many compilers store the local variables inside

a function on the stack.
 Applications of stacks contd…

 Conversion of one notation of expression to another.

 Evaluation of expressions.

 Balancing symbols to check for correctness of an

expression.
 Applications of stacks contd…

Convert Infix to Postfix Notation

 Types of Notations
• Infix Notation
– e.g  A+B
– Prefix Notation
• e.g  +AB
– Postfix Notation
• e.g  AB+

When an infix expression is to be converted into

prefix or postfix Precedence rules and
associativity rules follows.
 Advantages of Postfix Notation
• No parenthesis required.
• No need to remember precedence and associativity rules of
various operators.
• When an infix expression is to be converted into prefix
or postfix BODMAS rules and associativity rules follows
(Highest)
• ^ Right associative
• *,/ left associative
• +,- left associative
• (lowest)
 Expressions contd…

For unparenthesized operators of same precedence, the order is

assumed to be left to right except in the case of
exponentiation.

Ex: A + B +C means (A + B) + C
A$B$C means A $(B $ C), where $ stands for exponentiation
 Ex:
Infix Postfix
A+B AB+
A+B-C AB+C-
(A+B)*(C-D) AB+CD-*
A$B*C-D+E/F/(G+H) AB$C*D-EF/GH+/+
((A+B)*C-(D-E))$(F+G) AB+C*DE- - FG+$
A-B/(C*D$E) ABCDE$*/ -
…………………………………………………………………………………………………….
Infix Prefix
A+B +AB
A+B-C -+ABC
(A+B)*(C-D) *+AB-CD
A$B*C-D+E/F/(G+H) +-*$ABCD//EF+GH
((A+B)*C-(D-E))$(F+G) $-*+ABC-DE+FG
A-B/(C*D$E) -A/B*C$DE
Convert an Infix to Postfix Using Stack:
 When an operand is read, it is immediately placed on
to the output Array.
 Operators are not immediately output, so we save

them somewhere. We place these operators on to a

stack.

 (:
 We need to stack ‘(‘ when they are encountered.
 If we see a ‘)’, then we pop the stack, writing symbols into
output Array until we encounter a corresponding ‘(‘ which is
popped but not output.
 We never remove a ‘(‘ from a stack except when processing
a ‘)’.
 Steps contd…….

 +, - have lowest priority and ( has highest.

 If we see any other symbol, i.e. +, -, *, ( etc then pop

the entries from the stack until we find an entry of

lower priority.
 When popping is done, we push the operator on to

the stack.

 Finally we read the end of the input, we pop the

stack till it is empty, writing symbols onto the
output Array.
Ex: a+b*c+(d*e+f)*g

output stack
Ex: a+b*c+(d*e+f)*g

output stack
Ex: a+b*c+(d*e+f)*g

a
+
output stack
Ex: a+b * c+(d*e+f)*g

a b
+
output stack
Ex: a+b * c+(d*e+f)*g

*
ab +
output stack
Ex: a+b*c+(d*e+f)*g

*
ab c +
output stack
Ex: a+b*c+ (d*e+f)*g

abc **
+
output stack
Ex: a+b*c + (d*e+f)*g

abc ** +
output stack
Ex: a+b*c+(d*e+f)*g

abc ** + +
output stack
Ex: a+b*c+( d*e+f)*g

abc*+ (
+
stack
output
Ex: a+b*c+( d *e+f)*g

abc*+ d (
+
stack
output
Ex: a+b*c+(d * e+f)*g

abc*+d *
(
output +
stack
Ex: a+b*c+(d* e +f)*g

abc*+d e *
(
output +
stack
abc*+de *
(
output +
stack

Ex: a+b*c+(d*e+f)*g
abc*+de * +
(
output +
stack

Ex: a+b*c+(d*e+f)*g
abc*+de * +
(
output +

+
abc*+de* f (
+
output
stack

Ex: a+b*c+(d*e+ f )*g

abc*+de * +
(
output +
stack

abc*+de* f + (
+
output
stack

Ex: a+b*c+(d*e+f ) *g
abc*+de* f +
+
output
stack

Ex: a+b*c+(d*e+f ) *g
abc*+de* f +
+
output
stack

abc*+de*f+ *
+
output
stack

Ex: a+b*c+(d*e+f) * g
abc*+de* f +
+
output
stack

abc*+de*f+ g *
+
output
stack

Ex: a+b*c+(d*e+f)* g
 Ex: a+b*c+(d*e+f)*g

abc*+de*f+g *
+
output
stack

abc*+de*f+g* +
output stack
 Ex: a+b*c+(d*e+f)*g

abc*+de*f+g*+
output stack

Therefore the postfix expression is a b c * + d e * f + g * +

 Another Example: ((A- (B+C))*D)$(E+F)
SYMB POSTFIX STRING (OUTPUT) Stack
( (
( ((
A A ((
- A ((-
( A ((-(
B AB ((-(
+ AB ((-(+
C ABC ((-(+
) ABC+ ((-
) ABC+ - (
* ABC+ - (*
D ABC+ - D (*
) ABC+ - D *
$ ABC+ - D * $
( ABC+ - D * $(
E ABC+ - D * E $(
+ ABC+ -D * E $(+
F ABC+ -D * EF $(+
) ABC+ - D * EF + $

The output is ABC+ - D * EF + $

 Algorithm: Postfix(Q, P)
[Suppose Q is an arithmetic expression written in infix notation. This
algorithm finds the equivalent postfix expression P]

1. Set Q as input Expression, S is stack and P is output array.

2. Scan Q from left to right, repeat step 3 to 6 untill stack S is empty.
3. If operand put it to P (output array)
4. If ‘(‘, push it onto the stack S.
5. If operator then
1. Repeatedly pop from stack S and add to P each operator that has the
same precedence or higher precedence then the operator
encountered.
2. Add operator to stack S
6. If ‘)’ then
(a) Pop from stack S and add to P each operator untill a left opening parenthesis
‘(‘ is encountered.
(b) remove left parenthesis ( and do not add to output array P

7. Exit
(2) Evaluating a postfix expression
Using stack
 (2) Evaluating a postfix expression

Example:

6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

 (2) Evaluating a postfix expression
 Ex: 6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

 If operands, push in the stack.

 If operator , Pop two top operands from Stack and apply
encountered operator on both operands and push result back to
Stack.

6
 (2) Evaluating a postfix expression
 Ex: 6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

6
 (2) Evaluating a postfix expression
 Ex: 6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

3
2

6
 (2) Evaluating a postfix expression
 Ex: 6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

3
5
2
6
6
 (2) Evaluating a postfix expression
 Ex: 6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

5
6 1
 (2) Evaluating a postfix expression
 Ex: 6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

3
1
 (2) Evaluating a postfix expression
 Ex: 6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

8
3
1
 (2) Evaluating a postfix expression
 Ex: 6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

2
8
3
1
 (2) Evaluating a postfix expression
 Ex: 6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

2
4
8
3
3
1 1
 (2) Evaluating a postfix expression
 Ex: 6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

2
4
8
3 7
3
1 1
1
 (2) Evaluating a postfix expression
 Ex: 6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

2
4
8
3 7
3 7
1 1
1
 (2) Evaluating a postfix expression
 Ex: 6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

2
7 49
 (2) Evaluating a postfix expression
 Ex: 6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

2 3
7 49 49
 (2) Evaluating a postfix expression
 Ex: 6 2 3 + - 3 8 2 / + * 2 $ 3 + is the given postfix expression.

2 3
7 49 49 52
Algorithm: Evaluation of Postfix Expression
1. Set P as Expression, S as stack, Final Value.
2. Scan P from left to right and repeat step 3 to 5 till end of
expression.
3. If an operand is encountered, put it on the stack S.
4. If operator is encountered
a) Pop top two elements from the stack as A, and B
b) Evaluate A op B.
c) Push the result of above (b) back on the stack S.
(end of if)
(end of step 3 loop)
5. Set Final Value equal to the top element of the stack S.
6. Exit.
Checking for the Correct Parenthesis of
an Expression Using Stack
 Correctness of an expression
 When the expression involves several sets of multiple
parentheses, we have to ensure that the parentheses are
nested correctly. i.e., we want to check that:
 There are equal number of right and left parentheses.
 Every right parenthesis is preceded by a matching left
parenthesis.

 Ex: ((A+B)
A+B( Are not correct
)A+B(-C
(A+B))-(C+D
(A+B]
Use stacks to check expression correctness
 When ever an opening bracket is encountered, it is pushed on to the
stack.
 When ever a closing bracket is encountered, the stack is examined.

 If the stack is empty, then closing bracket does not have a matching
opening bracket and the expression is therefore invalid.
 If the stack is non empty, we pop the stack and check whether the
popped item corresponds to the closing bracket.

 If a match occurs, we continue otherwise expression is invalid.

 When the end of the string comes, then the stack must be empty.

 Otherwise, one or more bracket have been opened, which have not
been closed and the string is invalid.
 Parenthesis stack at various stages of processing
{ x + (y – [a + b]) * c – [ (d + e) ]}

1
Parenthesis stack at various stages of processing
{ x + (y – [a + b]) * c – [ (d + e) ]}

(
{

2
Parenthesis stack at various stages of processing
{ x + (y – [a + b]) * c – [ (d + e) ]}

[
( (
{ {

2 3
Parenthesis stack at various stages of processing
{ x + (y – [a + b]) * c – [ (d + e) ]}

[
( (
{ {

3 4
Parenthesis stack at various stages of processing
{ x + (y – [a + b]) * c – [ (d + e) ]}

(
{ {

4 5
 Parenthesis stack at various stages of processing
{ x + (y – [a + b]) * c – [ (d + e) ]}

[
{

6
 Parenthesis stack at various stages of processing
{ x + (y – [a + b]) * c – [ (d + e) ]}

(
[ [
{ {

6 7
Parenthesis stack at various stages of processing
{ x + (y – [a + b]) * c – [ (d + e) ]}

(
[ [
{ {
7 8
Parenthesis stack at various stages of processing
{ x + (y – [a + b]) * c – [ (d + e) ]}

(
[ [
{ { {
7 8 9
Parenthesis stack at various stages of processing
{ x + (y – [a + b]) * c – [ (d + e) ]}

(
[ [
{ { {
7 8 9 10
 Algorithm : Parenthesis Check by stack
1. Set P as Expression, S as stack.
2. Scan P from left to right and repeat step 3 to 4 till end of
expression.
3. If an opening bracket is encountered, put it on the stack S.
4. If closing bracket is encountered then check that:
a) If Stack S is empty then expression is INVALID.
b) If top of stack S is not matching opening bracket then
expression is INVALID.
c) If top of S is matching opening bracket then Pop it.

(end of step 3 loop)

5. If stack S is EMPTY then expression is VALID.

6. Exit.