STACK

Definition
Stack is a collection of homogeneous data items where the insertion and deletion operations
take place at one end called TOP of the stack. Stack works on LIFO (Last In First Out)
Fashion

5 TOP
8
1
Implementation of Stack
There are two ways to implement a stack:
 Static (arrays)
 Dynamic (linked list)

Array representation of Stack

 Stack is represented by a linear array STACK

 A pointer variable TOP, which contains the location of the top element of the stack
 The variable MAXSTK which gives the max number of elements that can be held by
the stack
 The condition TOP=-1 indicates that stack is empty
 The condition TOP = MAXSTK -1 indicates that the stack is full

Linked List representation of Stack

  In linked list implementation of stack, the nodes are maintained non-contiguously in
the memory.
 Each node contains a pointer to its immediate successor node in the stack.
 Stack is said to be overflown if the space left in the memory heap is not enough to
create a node.

 START pointer in the linked list will be the TOP of the stack
 PUSH in the stack , insert a new node in the beginning of the linked list
 POP from the stack, delete a node from the beginning of the linked list
 Display the stack, needs just the traversal of the linked list

StackADT
A set of stack data members and a set of stack operations that perform on stack data. The
stack data members are TOP, MAXSTK.
TOP is a pointer variable which contains the location of the top element. The variable
MAXSTK gives the maximum number of elements that can be held by the stack.
The stack operations such as
1. Createstack()- Create stack with n elements.
2. push()- insert an element on to the TOP of the stack
3. pop()- delete an element from the TOP of the stack.
4. peek() – returns the element at the TOP of the stack
5. isEmpty()- returns true if the stack is empty otherwise false
6. isFull()- returns true if the stack is full otherwise false
7. Traverse()- accessing all the elements in the stack.
8. Count()- count the number of elements in the stack.
PUSH operation
It is used to insert an element on the TOP of the stack. If stack is full, PUSH operation is not
possible.
Algorithm: PUSH(S,TOP, MAXSTK, item)
1. check Stack is overflow
if TOP= = MAXSTK - 1 then
print "Stack Overflow"
return
2. Increment TOP value
TOP=TOP+1
3. Insert the item at the TOP
S[TOP]=item
4. return
Explanation
Consider the following stack contain 3 element and its MAXSTK value is 5

5 TOP
8
1
1. Check stack overflow using TOP= = MAXSTK -1, here it is false
2. Increment TOP value by TOP=TOP+1

TOP
5
8
1
 3. Insert item at the TOP using S[TOP]=item

10 TOP
5
8
1
4. return

POP operation
This operation deletes an element from the stack i.e., it deletes the TOP element from the
stack. If stack is empty the pop operation is not possible.
Algorithm: POP(S,TOP, item)
1. Check underflow
if TOP== -1 then
print "stack underflow"
return
2. Delete the item
item=S[TOP]
3. Decrement TOP value
TOP=TOP-1
4. return
Explanation
Consider a stack contain 3 elements and its MAXSTK value is 5.

5 TOP
8
1
1. Check stack is underflow or not, here TOP=2and MAXSTK=5. Therefore, go to step
2
2. Delete the TOP item

TOP
8
1
3. Decrement TOP value by 1
 8 TOP
1
4. Return

Traverse operation
Accessing all elements in the stack is known as traversal operation.
Algorithm: DISPLAY(S, TOP)
1. Check underflow
if TOP= = -1 then
print "stack underflow"
return
2. Access all elements using loop
for i=TOP to 0
print S[i]
end for
3. return

Explanation
Consider a stack contain 3 elements and its MAXSTK value is 5.

5 TOP
8
1
1. Check stack is underflow or not, here TOP=2and MAXSTK=5. Therefore, go to step
2
2. Access the TOP of the element and print using Loop 5 8 1
3. Return
isEmpty() operation
This operation is used to find whether the stack is empty or not. If the stack is empty then it
returns TRUE, else it returns FALSE. This is used to check stack underflow condition.
Algorithm: boolean isEmpty()
If TOP = = -1
Return true
Else
Return false
isFull() operation
This operation is used to find whether the stack is full or not. If the stack is full then it returns
TRUE, else it returns FALSE. This is used to check stack overflow condition.
Algorithm: boolean isFull()
If TOP = = MAXSTK-1
Return true
Else
Return false
peek() operation
This operation is used to get the top element of the stack and without removing it from the
stack.
Algorithm: int peek()
If TOP = = -1
Display “Stack Underflow”
Else
Return S[TOP];

Application of stack
• Infix to postfix conversion
• Infix to prefix conversion
• Postfix expression evaluation
• Recursion
• Checking the parenthesis matching ( Balancing of symbols)
• Reversal of a string
• Redo-undo features
• Forward and backward feature in web browsers
• Backtracking
• In Graph Algorithms
• In Memory management

Polish Notation of Arithmetic Expressions

The great Polish Mathematician Jan Lukasiewich introduced a new technique for the
representation of arithmetic expressions. According to him arithmetic expressions are
classified into three categories.
• Infix notation
• Postfix notation
• Prefix Notation
Infix Notation
Operator is placed in between the operands eg: a + b
 Prefix Notation (Polish Notation)
Operator is placed before operands eg : +ab
Postfix Notation (Revers polish notation) or Suffix notation
Operator is placed after operands eg: ab+
To parse any arithmetic expression, we need to take care of
• operator precedence
• associativity

Conversion from infix to postfix expression

Algorithm
1. Push ‘(‘ on the stack and add ‘)’ at the end of the infix expression Q.
2. Read all the symbols one by one from left to right in the given Infix Expression.
3. If the scanned symbol is operand, then print it (Output).
4. If the scanned symbol is left parenthesis '(', then Push it on to the Stack.
5. If the scanned symbol is operator ⊗then
1. Repeatedly pop the operators from stack and print it which has the same
precedence or higher precedence than operator ⊗
2. PUSH ⊗ to STACK
6. If the scanned symbol is right parenthesis ')’, then
1. Repeatedly Pop all the contents of stack and print each poped symbol to the
result.
2. Remove the left parenthesis’ (‘
7. Exit

Example
Consider the following expression Q=A + (B + C)
To covert infix to postfix push a ‘(‘ on to the stack and add a ‘)’ at the end of the infix
expression
Q= A + (B + C))
Line Scanned Stack Postfix Expression
Symbol

1 A ( A

2 + ( + A

3 ( ( + ( A

4 B ( + ( AB

5 + ( + ( + AB

6 C ( + ( + ABC

7 ) ( + ABC+

8 ) ABC++
Homework
 Write postfix expression for
 A + B*C+(D *E+F)*G
Evaluation of Postfix expression
Algorithm
Step 1: Add “#” at the end of P
Step 2: Repeat scanning P from left to right and repeat step 3 and 4 for each element of P
until “#” is encountered.
Step 3: If an operand is encountered, push it onto STACK
Step 4: If an operator ⊗ is encountered:
1. Remove the two top elements of STACK. If A is the top element, B is the next
top element.
2. Evaluate B⊗ A
3. Push the result of (2) of step 4 back onto STACK
 Step 5: Evaluated value is equal to the top of the STACK
Step 6: Exit
Example
Let P=6, 5, 3, +, *, 12, 3, /, -
Initially add ‘#’ at the end of the given expression P
P=6, 5, 3, +, *, 12, 3, /, -,#
Now we will scan the symbols until ‘#’ is encountered.

Line Scanned Operation Stack

Symbol performed

1 6 Push 6 6

2 5 Push 5 6 5

3 3 Push 3 6 5 3

4 + Pop 3 and 5
5+3=8 6 8
Push 8

5 * Pop 8 and 6
6*8=48 48
Push 48

6 12 Push 12 48 12

7 3 Push 3 48 12 3

8 / Pop 3 and
12
48 4
12/3=4
Push 4

9 - Pop 4 and
48
44
48-4=44
Push 44

Value of postfix expression=Top of stack= 44

Checking the Parenthesis Matching
Stacks are most useful for checking the parenthesis matching in an expression.
Algorithm:
Step1: Scan the symbols of expression from left to right
Step2: If the symbol is a left parenthesis then push it on the stack
Step3: If the symbol is right parenthesis
 if the stack is empty
valid = false
else
pop an element from the stack
if the popped parenthesis does not match the parenthesis being scanned
valid= false
Step4: After scanning all the symbol if stack is not empty then
valid = false
Show that the expression ((1+2)*3) is valid

Scanned Symbol ((1+2)*3) Stack Operation Performed

( ( Push()

( ( ( Push()

1 ( (

+ ( (

2 ( (

) ( Pop()

* (

3 (

) Pop()

RECURSION
It is a process of calling the function repeatedly itself. The repeated calling is terminated by a
specific condition.
Types
 Direct
 Indirect
Direct Recursion
This type calls itself repeatedly until certain condition is satisfied
Example
fact(int n)
{
if(n==0)
return 1;
 else
return (n* fact(n-1));
}
Indirect Recursion
This type calls another function which eventually calls the same function repeatedly
Example
fun1 (int a)
{
fun2( b);
}
fun2 (int c)
{
fun1(x);
}

Advantages of Recursion:
1. Reduces the complexity of the problem
2. It allows user to write simple and elegant program
3. Programs are smaller in length
4. Programs can have any no. of nesting levels
5. Top-Down Programming model

Recursion : Example 1 - Greatest Common Divisor (GCD)

Greatest Common Divisor problem can be solved using recursion
The recursive description can be expressed as:

{ }
GCD ( n ,m ) , if n>m
GCD ( m , n )= m ,if n=0
GCD ( n , MOD ( m , n ) ) , Otherwise

The steps during this process can be represented as follows:

GCD(288, 108)= GCD(108,72)

GCD(108, 72)=GCD(72, 36)
GCD(72, 36)=GCD(36, 0)
GCD(36, 0)= 36
GCD(72, 36)= 36
GCD(108,72)= 36
GCD(288, 108)= 36

The following program find GCD of three numbers

#include<stdio.h>
int gcd(int m, int n)
{
if(n= = 0)
 return m;
else
return (gcd(n, m%n));
}
void main()
{
int k, m, n;
printf("Enter the three numbers: ");
scanf("%d %d %d", &k, &m, &n);
printf("GCD (%d, %d, %d) = %d ", k, m, n, gcd(k, gcd(m, n)));
}
Output
Enter the three numbers: 4 6 8
GCD (4, 6, 8 ) = 2

Recursion : Example 2 - Finding factorial using Recursive method

The factorial is defined as the product of all integers between n and 1.

The recursive description can be expressed as:

FACTORIAL(N) = {N∗FACTORIAL(N −1)if Otherwise }

1 if N=0

Algorithm: FACTORIAL(N)
Step 1: if (N= = 0) then
fact=1
Step 2: else
Fact=N * FACTORIAL (N-1)
End if
Step 3: return(fact)
Step 4: Stop

Consider the following represents 4! Using recursive function

4!=4*3!

3!=3*2!

2!=2*1!

1!=1*0!

1!=1

2!=2
 3!=6

4!=24

The whole process is implemented in the stack as shown below

Recursion : Example 3 - Fibonacci Series

Fibonacci series is a peculiar series of integers where each element in the series is the sum of
the two preceding elements. Eg: 0 1 1 2 3 5 8 13 21 ……………
The general Fibonacci series can be represented as

{ }
0 if N=0∨N =1
Fib(N)= 1 if N=2
fib ( N −1 )+ fib ( N −2 ) if N > 2

Algorithm: fibon(N)
if(N==0) || (N==1) then
fib=0
else if (N==2) then
fib=1
else if (N>2) then
fib=fibon(N-1) +fibon(N-2)
end if
return fib
stop
Algorithm Steps

fibon(6)=fibon(5)+fibon(4)

fibon(5)=fibon(4)+fibon(3)
 fibon(4)=fibon(3)+fibon(2)

fibon(3)=fibon(2)+fibon(1)

fibon(2)=1, fibon(1)=0

fibon(3)=1

fibon(4)=2

fibon(5)=
3

fibon(6)=5

The following represents the Fibonacci recursive call illustration.

Recursion : Example 4 - Tower of Hanoi Problem

Tower of Hanoi problem is a game where a disk is to be moved from one source pillar to a
destination pillar using a temporary pillar. To solve this problem, we have to follow three
conditions. They are:
• Only one disk can be moved at one time, from one pillar to another
• A larger disk cannot be placed on the smaller disk
• Only the top disc on any pillar may be moved to any other pillar
• Algorithm: move(n, S, T, D)
• {
• move(n-1, S, D, T) //move (n-1) disks from S to T
• move(1, S, T, D) //move 1 disk from S to D
• move(n-1, T, S, D) //move (n-1) disks from T to D
• }
• Consider the Tower of Hanoi has three disks (n=3)
 •
• The solution is represented in the following figure:
•

• Hence the sequence for n=3 is

• SD ST DT SD TS TD SD