Lecture # 11-12

Stack
A stack is a linear list in which insertion and
deletion operations are performed at only one
end of the list.
Thus you are able to insert as well as delete the
element from only one end of the stack.
Since insertion and deletion operations are
performed at same end, the element which is
inserted Last is first to delete.
A deck of cards or a pile of plates
A real-world stack allows operations at one end
only.
 Stack - Examples

For example, we can place or remove a card

or plates on a shelf from the top of the stack
only
At any given time, we can only access the top
element of a stack.
Stack of CD’s
Stack of Books
Stack - Examples
 Stack - LIFO
Consider a card game with a discard pile
√ Discards always placed on the top of the pile
√ Players may retrieve a card only from the top

LIFO stands for Last-In-First-Out. Here, the

element which is placed (inserted or added)
last, is accessed first. In stack terminology,
insertion operation is called PUSH operation
and removal operation is
called POP operation.
Stack Representation
Push – Pop - Top
 Stack - Top
Consider a stack of plates at dinner counter.

The person who comes for dinner takes off

the plate which is at top of the stack.

After washing the plates the waiter places

the washed plates on the top of the stack.

So the plate that is placed last is first take by

person.
 Applications of stack
Stacks are useful data structures for algorithms that
work first with the last saved element of a series.
 computer systems use stack while executing programs,
when a function is called, its return address goes on
a stack.
 Evaluation of arithmetic expressions by compilers [infix
to postfix conversion, infix to prefix conversion,
evaluation of postfix expressions]
Auxiliary data structure for some algorithms.
 Example: Converting a decimal number to another base
Conversion of tail-recursive algorithms to iterative
ones. [Note: Tail recursion will be covered in a later
lesson]
etc
Common Operations Performed on Stack
√ MAKENULL(S): Make Stack S be an empty stack.
√ TOP(S): Return the element at the top of stack S.
√ POP(S): Remove the top element of the stack.
√ PUSH(S): Insert the element x at the top of the
stack.
√ ISEMPTY(S): Return true if S is an empty stack;
return false otherwise.
√ TOP(S)/PEEK(S) − get the top data element of
the stack, without removing it.
√ ISFULL(S) − check if stack is full.
√ ISEMPTY(S) − check if stack is empty.
 Operations Performed on Stack
At all times, we maintain a pointer to the last
PUSHed data on the stack. As this pointer
always represents the top of the stack, hence
named top. The top pointer provides top value
of the stack without actually removing it.
 Algorithm: PEEK()
PEEK (STACK, TOP)
0. Start
1. If (! (TOP < 1)) then // Stack is NOT
Empty
2. Return STACK[TOP]
3. Else
4. Display “Stack is Empty"
5. End if // if index starts
6. End from 0
IF (!(TOP < 0))
…
ELSE
…
End
 Algorithm: ISFULL()
ISFULL (STACK, TOP, SIZE)
0. Start
1. If (TOP == SIZE) then // Stack is Full
2. Return True
3. Else
4. Return False
5. End if
6. End // if index starts
from 0
IF (TOP == SIZE -
1)
…
ELSE
…
 Algorithm: ISEMPTY()
ISEMPTY (STACK, TOP, SIZE)
0. Start
1. If (TOP == 0) then // Stack is EMPTY
2. Return True
3. Else
4. Return False
5. End if
6. End // if index starts
from 0
IF (TOP == -1)
…
ELSE
…
End
Push Operation
 PUSH Operation
The process of inserting an element into stack
is known as PUSH operation.
In order to insert an element into stack first
we have to check weather free space is
available in the stack or not.
If stack is full then we can not insert an
element into stack.
This condition is known as “Overflow”.
If stack is not overflow then we can insert an
element into stack by incrementing the value
of variable TOP by one and then insert an
element at this position into stack.
 Push Operation - Simple Steps
The process of putting a new data element
onto stack is known as a Push Operation.
Push operation involves a series of steps
Step 1 − Checks if the stack is full.
Step 2 − If the stack is full, produces an error
and exit.
Step 3 − If the stack is not full,
increments top to point next empty space.
Step 4 − Adds data element to the stack
location, where top is pointing.
Step 5 − Returns success.
 PUSH Operation - Algorithm
PUSH(STACK, TOP, SIZE, ITEM)
This procedure pushes an ITEMS onto a
stack.
1. [Stack already filled?]
IF (TOP == SIZE) then
Print “OVERFLOW”
Return
ELSE
2. Set TOP: = TOP + 1 [Increase TOP by 1.]

3. Set STACK[TOP] := ITEM. [ Inserts ITEM

in new TOP Position.]

4. Return.
Pop Operation
The process of deleting an element from stack is known
as POP operation.
In order to delete an element from stack first we have to
check weather stack is empty or not. If stack is empty
then we can not delete an element from stack. This
condition is known as “Underflow”.
If value of TOP variable is -1 then stack is empty. So we
can not delete an element from stack.
If stack is not underflow then we can delete topmost
element from stack. After deleting topmost element from
stack, we have to decrement the value of TOP by one, so
that it can point to the next topmost element in the
stack.
Pop Operation
Accessing the content while removing it from
the stack, is known as a Pop Operation.
In an array implementation of pop()
operation, the data element is not actually
removed, instead top is decremented to a
lower position in the stack to point to the next
value.
But in linked-list implementation, pop()
actually removes data element and
deallocates memory space.
Pop Operation simple Steps
A Pop operation may involve the following steps −

Step 1 − Checks if the stack is empty.

Step 2 − If the stack is empty, produces an error

and exit.

Step 3 − If the stack is not empty, accesses the data

element at which top is pointing.
Step 4 − Decreases the value of top by 1.

Step 5 − Returns success.

Pop Operation
POP Operation Algorithm
POP(STACK, TOP, ITEM)
This procedure deletes the top elements of STACK and
assigns it to the variable ITEM.
1. [Stack has an items to be removed?]
IF TOP = 0, then:
Write: UNDERFLOW
Return
ENDIF
2. Set ITEM := STACK[TOP]. [Assigns TOP elements
to ITEM.]

3. Set TOP := TOP - 1. [Decreases TOP elements

to ITEM.]

4. Return.
Arithmetic Expressions Notations
The way to write arithmetic expression is known as
a notation – Polish Notations
There are basically three types:
√ Infix: When the operator is written between two
operands then it is known as Infix notation. For
example A+B - Infix Polish Notation
√ Prefix: When the operator is written before their
operands then it is known as Prefix notation. For
example +AB -Polish Notation / Prefix Polish Notation
√ Postfix: When the operator is written after their
operands then it is known as Postfix notation. For
example AB+ - Reverse Polish Notation / Postfix
Polish Notation
Polish Notations
Infix notation
Prefix notation
Postfix notation
Algorithm for converting the Infix
notation into Postfix notation
Algorithm for evaluation of postfix
expression
Polish Notations
Operator Precedence
√ Following are the precedence of each
operator from highest to lowest.
Conversion of Infix Expression into
Postfix Expression
√ Generally we use infix notation in
arithmetic expression.
√ In order to convert an expression from
infix notation to postfix notation follows
some steps
Steps:
Infix Expression into Postfix Expression steps
√ (1) Initialize an empty stack.
√ (2) Scan infix string from left to right.
√ (3) If scanned character is an operand then append it
into postfix string.
√ (4) If scanned character is left parenthesis “(“then
PUSH it into stack.
√ (5) If scanned character is an operator and stack is
either empty or contains “(“at topmost element then
PUSH it into stack.
√ (6) If scanned character is right parenthesis “)” then
POP all the operators from stack until “(“is
encountered in the stack. Do not append parenthesis
into postfix string.
Steps (Contd..)
 Infix Expression into Postfix Expression steps
√ (7) If scanned character is an operator and top of the
stack also contains an operator then we have to
compare the precedence of operators as follow:
√ (a) If precedence of scanned operator is less then or equal to
the precedence of topmost operator in the stack then POP that
operator from stack and append it into postfix string and PUSH
scanned operator into stack.
√ (b) If precedence of scanned operator is greater then the
precedence of topmost operator in the stack then PUSH
scanned operator into stack.
√ (8) Repeat step7 until “(“is encountered into stack or stack
becomes empty.
√ (9) When all the characters are scanned from infix string,
POP remaining characters from stack and append it into
postfix string. (7) If (Incoming-Oprtr > Topmost-Oprtr) REPHRASED
PUSH on to stack
Otherwise POP all oprtrs and append to PostFix expression
which are > Incoming-Oprtr & then PUSH it on stack.
(Simple Steps - Revisited)
Conversion from Infix to Postfix Algorithm
Step1

 Scan the Infix expression from left to right for

tokens (Operators, Operands & Parentheses) and

perform the steps 2 to 5 for each token in the

Expression
Algorithm
Step2

 If token is operand, Append it in postfix expression

Step3

 If token is a left parentheses “(“, push it in stack.

Algorithm
Step4

 If token is an operator,

 Pop all the operators which are of higher or equal

precedence than the incoming token and append

them (in the same order) to the output Expression.

 After popping out all such operators, push the new

token on stack.
Algorithm
Step5

 If “)” right parentheses is found,

 Pop all the operators from the Stack and append

them to Output String, till you encounter the

Opening Parenthesis “(“.

 Pop the left parenthesis but don’t append it to the

output string (Postfix notation does not have

brackets).
Algorithm
Step6

 When all tokens of Infix expression have been

scanned. Pop all the elements from the stack and

append them to the Output String.

 The Output string is the Corresponding Postfix

Notation.
Example
 Let the incoming the Infix expression be:

A * (B + C) – D / E

Stage 1: Stack is empty and we only have the Infix

Expression.
Example
Stage 2

 The first token is Operand A Operands are

Appended to the Output as it is.

Example
Stage 3

 Next token is * Since Stack is empty

(top==NULL) it is pushed into the Stack

Example
Stage 4

 Next token is ( the precedence of open-parenthesis, when it

is to go inside, is maximum.

 But when another operator is to come on the top of ‘(‘ then

its precedence is least.

Example
Stage 5

 Next token, B is an operand which will go to the Output

expression as it is
Example
Stage 6

 Next token, + is operator, We consider the precedence of top

element in the Stack, ‘(‘. The outgoing precedence of open

parenthesis is the least (refer point 4. Above). So + gets pushed into

the Stack

Important
Point
Example
Stage 7

 Next token, C, is appended to the output

Example
Stage 8

 Next token ), means that pop all the elements from Stack

and append them to the output expression till we read an

opening parenthesis.
Example
Stage 9

 Next token, -, is an operator. The precedence of operator on

the top of Stack ‘*‘ is more than that of Minus. So we pop

multiply and append it to output expression. Then push

minus in the Stack.

Example
Stage 10

 Next, Operand ‘D‘ gets appended to the output.

Example
Stage 11

 Next, we will insert the division operator into the Stack

because its precedence is more than that of minus.

Example
Stage 12

 The last token, E, is an operand, so we insert it to the

output Expression as it is.

Example
Stage 13

 The input Expression is complete now. So we pop the

Stack and Append it to the Output Expression as we

pop it.
Algorithmic Steps for Infix to Postfix
1) Examine the next element in the input.
2) If it is operand, output it.
3) If it is opening parenthesis, push it on stack.
4) If it is an operator, then
i) If stack is empty, push operator on stack.
ii) If the top of stack is opening parenthesis, push operator
on stack
iii) If it has higher priority than the top of stack, push
operator on stack.
iv) Else pop the operator from the stack and output it, push
scanned character repeat step 4
5) If it is a closing parenthesis, pop operators from stack and
output them until an opening parenthesis is encountered.
pop and discard the opening parenthesis.
6) If there is more input go to step 1
7) If there is no more input, pop the remaining operators to
output.
Algorithm for Converting Infix Expression into
Postfix Expression
POLISH(Q,P)
Suppose Q is an arithmetic expression written in infix notation. This
algorithm finds the equivalent postfix expression P.
1) Scan Q from left to right and repeat Steps 2 to 5 for each elements
of Q until the STACK is empty:
2) If an operand is encountered, add it to P.
3) If a left parenthesis is encountered. Push it onto STACK.
4) If an operator × is encountered, then:
a) Repeatedly pop from STACK and add to P each operator (on the
top of STACK) which has the same precedence as or higher
precedence than ×.
b) Add × to STACK.
[End of If Structure.]
5) If a right parenthesis is encountered, then:
a) Repeatedly pop from STACK and add to P each operator (on the top of
STACK) until a left parenthesis is encountered:
b) Remove the left parenthesis. [Do not add the left parenthesis to P.]
[End of If Structure.]
[End of Step loop.]
6) Exit.
Evaluation diff: b/w Infix, Prefix n postfix
Infix to Postfix Example
Infix String: (a + b) * (c + d)
Scanned
Content of Stack Postfix String
Character
Empty Empty
( ( Empty
a ( a
+ (+ a
b (+ ab
) Empty ab+
* * ab+
( *( ab+
c *( ab+c
+ *(+ ab+c
d *(+ ab+cd
) * ab+cd+
ab+cd+*
Infix to Postfix Conversion(Examples)
Infix to Postfix Conversion(Examples)
Infix to Postfix Conversion(Examples)
Infix to Postfix Conversion(Examples)
Infix to Postfix Conversion(Examples)
Infix to Postfix
 An Infix to Postfix manual conversion
algorithm is:
1. Completely parenthesize the infix expression according
to order of priority you want.
2. Move each operator to its corresponding right
parenthesis.
3. Remove all parentheses.
Example
 Infix TO Postfix Example
(Without open stack-manual)
 Infix TO Postfix Example
(Without open stack-manual)