STACK

• A stack is a list with the restriction that inserts

and deletes can be performed in only one position
(called top). The fundamental operations on a
stack are push, which is equivalent to an insert,
and pop, which deletes the most recently inserted
element.
• Stack is also called Last In First Out (LIFO) list.
• Other names are piles and push down list.
STACKS IN REAL LIFE

• stack of books, stack of plates

• Add new items at the top
• Remove an item at the top
• Stack data structure similar to real life: collection of
elements arranged in a linear order.
• Can only access element at the top
STACK OPERATIONS

top 1
top 7 7
top 5 5 5
top 2 2 2 2
push(2) push(5) push(7) push(1)

top 21
top 7 7 top 7
5 5 5 top 5
2 2 2 2 top 2
1 pop() push(21) 21 pop() 7 pop() 5 pop()
STACK IMPLEMENTATION: ARRAY

• Worst case for insertion and deletion from an array when

insert and delete from the beginning: shift elements to
the left.
• Best case for insert and delete is at the end of the array
– no need to shift any elements.
• Implement push() and pop() by inserting and deleting at
the end of an array.
STACK USING AN ARRAY

top 1
2 5 7 1
7
5 0 1 2 3 4
2 top = 3
STACK USING AN ARRAY

• In case of an array, it is possible that the array may “fill-

up” if we push enough elements.
• Have a boolean function IsFull() which returns true is
stack (array) is full, false otherwise.
• We would call this function before calling push(x).
STACK OPERATIONS WITH ARRAY

int pop()
{
return A[current--];
}

void push(int x)
{
A[++current] = x;
}
STACK OPERATIONS WITH ARRAY
int top()
{
return A[current];
}
int IsEmpty()
{
return ( current == -1 );
}
int IsFull()
{
return ( current == size-1);
}
• A quick examination shows that all five operations take
constant time.
PUSH

• PUSH(STACK,TOP,MAXSTK,ITEM)
• This procedure push an ITEM onto a stack
• 1.[Stack already filled?]
• If TOP=MAXSTK then Print Over Flow and Return.
2. Set TOP=TOP+1
3.Set STACK[TOP]=ITEM
4. Return.
POP

• POP(STACK,TOP,ITEM)
• This procedure delete the top element of STACK
and assign it to the variable ITEM.
• 1.[Stack has an item to be removed?]
• If (TOP=0, then print UNDERFLOW and return.
2. Set ITEM=STACK[TOP] [Assign top element to ITEM]
3. Set TOP=TOP-1
4. Return.
USE OF STACK
• Example of use: prefix, infix, postfix expressions.
• Consider the expression A+B: we think of applying the
operator “+” to the operands A and B.
• “+” is termed a binary operator: it takes two operands.
• Writing the sum as A+B is called the infix form of the
expression.
PREFIX, INFIX, POSTFIX

• Two other ways of writing the expression are

+ A B prefix
A B + postfix

• The prefixes “pre” and “post” refer to the position of the

operator with respect to the two operands.
PREFIX, INFIX, POSTFIX

• Consider the infix expression

A+B*C
• We “know” that multiplication is done before addition.
• The expression is interpreted as
A+(B*C)
• Multiplication has precedence over addition.
PREFIX, INFIX, POSTFIX

• Conversion to postfix

A+(B*C) infix form

PREFIX, INFIX, POSTFIX

• Conversion to postfix

A+(B*C) infix form

A+(BC*) convert multiplication
PREFIX, INFIX, POSTFIX

• Conversion to postfix

A+(B*C) infix form

A+(BC*) convert multiplication
A(BC*)+ convert addition
PREFIX, INFIX, POSTFIX

• Conversion to postfix

A+(B*C) infix form

A+(BC*) convert multiplication
A(BC*)+ convert addition
ABC*+ postfix form
PREFIX, INFIX, POSTFIX

• Conversion to postfix

(A + B ) * C infix form
PREFIX, INFIX, POSTFIX

• Conversion to postfix

(A + B ) * C infix form
(AB+)*C convert addition
PREFIX, INFIX, POSTFIX

• Conversion to postfix

(A + B ) * C infix form
(AB+)*C convert addition
(AB+)C* convert multiplication
PREFIX, INFIX, POSTFIX

• Conversion to postfix

(A + B ) * C infix form
(AB+)*C convert addition
(AB+)C* convert multiplication
AB+C* postfix form
PRECEDENCE OF OPERATORS

• The five binary operators are: addition, subtraction,

multiplication, division and exponentiation.
• The order of precedence is (highest to lowest)
• Exponentiation 
• Multiplication/division *, /
• Addition/subtraction +, -
PRECEDENCE OF OPERATORS

• For operators of same precedence, the left-to-right rule

applies:

A+B+C means (A+B)+C.

• For exponentiation, the right-to-left rule applies

A  B  C means A  ( B  C )
INFIX TO POSTFIX

Infix Postfix
A+B AB+
12 + 60 – 23 12 60 + 23 –
(A + B)*(C – D ) AB+CD–*
A  B * C – D + E/F A B  C*D – E F/+
INFIX TO POSTFIX

• Note that the postfix form an expression does not require

parenthesis.
• Consider ‘4+3*5’ and ‘(4+3)*5’. The parenthesis are not
needed in the first but they are necessary in the second.
• The postfix forms are:
4+3*5 435*+
(4+3)*5 43+5*
EVALUATING POSTFIX

• Each operator in a postfix expression refers to the

previous two operands.
• Each time we read an operand, we push it on a stack.
• When we reach an operator, we pop the two operands
from the top of the stack, apply the operator and push
the result back on the stack.
EVALUATING POSTFIX
Stack s;
while( not end of input ) {
e = get next element of input
if( e is an operand )
s.push( e );
else {
op2 = s.pop();
op1 = s.pop();
value = result of applying operator ‘e’ to op1 and op2;
s.push( value );
}
}
finalresult = s.pop();
EVALUATING POSTFIX

Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
EVALUATING POSTFIX

Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
EVALUATING POSTFIX

Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
3 6,2,3
EVALUATING POSTFIX

Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
EVALUATING POSTFIX

Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
EVALUATING POSTFIX

Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
EVALUATING POSTFIX

Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
EVALUATING POSTFIX

Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
EVALUATING POSTFIX

Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
/ 8 2 4 1,3,4
EVALUATING POSTFIX

Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7 1,7
EVALUATING POSTFIX

Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7 1,7
* 1 7 7 7
EVALUATING POSTFIX

Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7 1,7
* 1 7 7 7
2 1 7 7 7,2
EVALUATING POSTFIX
Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7 1,7
* 1 7 7 7
2 1 7 7 7,2
 7 2 49 49
EVALUATING POSTFIX
Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7 1,7
* 1 7 7 7
2 1 7 7 7,2
 7 2 49 49
3 7 2 49 49,3
EVALUATING POSTFIX
Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7 1,7
* 1 7 7 7
2 1 7 7 7,2
 7 2 49 49
3 7 2 49 49,3
+ 49 3 52 52
EVALUATING POSTFIX
Evaluate 6 2 3 + - 3 8 2 / + * 2  3 +
Input op1 op2 value stack
6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7 1,7
* 1 7 7 7
2 1 7 7 7,2
 7 2 49 49
3 7 2 49 49,3
+ 49 3 52 52
CONVERTING INFIX TO POSTFIX

• Consider the infix expressions ‘A+B*C’ and ‘ (A+B)*C’.

• The postfix versions are ‘ABC*+’ and ‘AB+C*’.
• The order of operands in postfix is the same as the infix.
• In scanning from left to right, the operand ‘A’ can be
inserted into postfix expression.
CONVERTING INFIX TO POSTFIX

• The ‘+’ cannot be inserted until its second operand has

been scanned and inserted.
• The ‘+’ has to be stored away until its proper position is
found.
• When ‘B’ is seen, it is immediately inserted into the
postfix expression.
• Can the ‘+’ be inserted now? In the case of ‘A+B*C’
cannot because * has precedence.
CONVERTING INFIX TO POSTFIX

• In case of ‘(A+B)*C’, the closing parenthesis indicates

that ‘+’ must be performed first.
• Assume the existence of a function ‘prcd(op1,op2)’
where op1 and op2 are two operators.
• Prcd(op1,op2) returns TRUE if op1 has precedence over
op2, FASLE otherwise.
CONVERTING INFIX TO POSTFIX

• prcd(‘*’,’+’) is TRUE
• prcd(‘+’,’+’) is TRUE
• prcd(‘+’,’*’) is FALSE
• Here is the algorithm that converts infix expression to its
postfix form.
• The infix expression is without parenthesis.
CONVERTING INFIX TO POSTFIX
1. Stack s;
2. While( not end of input ) {
3. c = next input character;
4. if( c is an operand )
5. add c to postfix string;
6. else {
7. while( !s.empty() && prcd(s.top(),c) ){
8. op = s.pop();
9. add op to the postfix string;
10. }
11. s.push( c );
12. }
13. while( !s.empty() ) {
14. op = s.pop();
15. add op to postfix string;
16. }
CONVERTING INFIX TO POSTFIX
• Example: A + B * C
symb postfix stack
A A
CONVERTING INFIX TO POSTFIX
• Example: A + B * C
symb postfix stack
A A
+ A +
CONVERTING INFIX TO POSTFIX
• Example: A + B * C
symb postfix stack
A A
+ A +
B AB +
CONVERTING INFIX TO POSTFIX
• Example: A + B * C
symb postfix stack
A A
+ A +
B AB +
* AB + *
CONVERTING INFIX TO POSTFIX
• Example: A + B * C
symb postfix stack
A A
+ A +
B AB +
* AB + *
C ABC + *
CONVERTING INFIX TO POSTFIX
• Example: A + B * C
symb postfix stack
A A
+ A +
B AB +
* AB + *
C ABC + *
ABC * +
CONVERTING INFIX TO POSTFIX
• Example: A + B * C
symb postfix stack
A A
+ A +
B AB +
* AB + *
C ABC + *
ABC * +
ABC * +
CONVERTING INFIX TO POSTFIX

• Handling parenthesis
• When an open parenthesis ‘(‘ is read, it must be pushed
on the stack.
• This can be done by setting prcd(op,‘(‘ ) to be FALSE.
• Also, prcd( ‘(‘,op ) == FALSE which ensures that an
operator after ‘(‘ is pushed on the stack.
CONVERTING INFIX TO POSTFIX

• When a ‘)’ is read, all operators up to the first ‘(‘ must be

popped and placed in the postfix string.
• To do this, prcd( op,’)’ ) == TRUE.
• Both the ‘(‘ and the ‘)’ must be discarded: prcd( ‘(‘,’)’ ) ==
FALSE.
• Need to change line 11 of the algorithm.
CONVERTING INFIX TO POSTFIX
if( s.empty() || symb != ‘)’ )
s.push( c );
else
s.pop(); // discard the ‘(‘

prcd( ‘(‘, op ) = FALSE for any operator

prcd( op, ‘(’ ) = FALSE for any operator other than ‘(’
prcd( op, ‘)’ ) = TRUE for any operator other than ‘(‘
prcd( ‘)’, op ) = error for any operator.
prcd( ‘(‘ , ’)’ ) = FALSE
CONVERTING INFIX TO POSTFIX
• Example: (A + B) * C
symb postfix stack
( (
A A (
+ A (+
B AB ( +
) AB +
* AB + *
C AB + C *
AB + C *