data stuctures

CST35 / Data Structures UNIT - II


UNIT – 2

LINEAR DATA STRUCTURES:

 In linear data structure, elements will have a linear relationship with the adjacent
elements.
 Example: Stack, Queue, Linked list

STACK:

 Stack is an ordered collection of heterogeneous elements, where insertion and deletion
are performed only at one end(top of the stack).
 Insertion of elements in stack is called PUSH
 Deletion of elements in stack is called POP
 Stack follows LIFO(Last In First Out) strategy. (i.e) The element which is pushed last
will be popped out first
 Stack act as a Static Data structure if it is implemented using arrays
 Stack act as a Dynamic Data structure if it is implemented using Linked list
 Initially top = -1, which implies that stack is empty
Stack[4]
Stack[3]
Stack[2]
Stack[1]
Stack[0]
Representation of stack of size 5 as an array
OPERATIONS OF STACK
i) Push operation:

 Push operation is used to insert the element at top of the stack.
 Before performing push operation, it is necessary to check the stackfull condition,
because if a stack is full, push operation cannot be performed.
 If Stack is not full, (i.e) there is some space available in stack, then, top pointer is
incremented by one and then the element will be pushed at the top of the stack.
Algorithm:
Push(element)
if (top = = size – 1)
Write “Stack is full. Can’t perform push”
else
top = top + 1
stack [ top ] = element
end if
 Consider the size of stack is 3. Initially top = -1.

1

,CST35 / Data Structures UNIT - II


 Consider, We need to push the element 10 into the stack
o When we check the stack, we find that stack is not full. So we increment top by 1.
Hence top = 0. We store the element 10 in stack[0]

Stack[2]
Stack[1]
top Stack[0] 10
 We need to push the element 15 into the stack
o When we check the stack, we find that stack is not full. So we increment top by 1.
Hence top = 1. We store the element 15 in stack[1]

Stack[2]
top Stack[1] 15
Stack[0] 10
 We need to push the element 20 into the stack
o When we check the stack, we find that stack is not full. So we increment top by 1.
Hence top = 2. We store the element 20 in stack[2]

top Stack[2] 20
Stack[1] 15
Stack[0] 10
 We need to push the element 25 into the stack. When we check the stack, we find that
stack is full.(i.e) top = = size – 1 becomes true. So we can’t push the element 25 unless
some of the elements from the stack is popped.

POP operation:
 Pop operation deletes the element at top of the stack.
 Before performing pop operation, it is necessary to check the stack empty condition,
because if a stack is empty, pop operation cannot be performed.
 If Stack is not empty, (i.e) there is some values are available in stack, then, element at top
of stack is popped out and top pointer is decremented by 1.

Algorithm:
Pop( )
if (top = = – 1)
Write “Stack is empty. Can’t perform pop”
else
element = stack[top]
top = top -1
return(element)
end if



2

,CST35 / Data Structures UNIT - II


 If pop operation is to be done, element at top of stack 20 is popped and top is
decremented by 1
Stack[2]
top Stack[1] 15
Stack[0] 10
 If pop operation is to be done, element at top of stack 15 is popped and top is
decremented by 1
Stack[2]
Stack[1]
top Stack[0] 10
 If pop operation is to be done, element at top of stack 10 is popped and top is
decremented by 1
Stack[2]
Stack[1]
Stack[0]
top -1
 Since top is -1, stack is empty. Hence further pop operation cannot be done.
Display:
 Display operation displays the element in the stack
 If there is no elements in stack, element can’t be displayed
 If there are elements in stacks, it displays the elements from the top position of the stack
till the zeroth position
display( )
if top = = -1
Write “ stack is empty. No elements to display”
else
for i = top to 0
Write stack [ i ]
end for
end if
APPLICATIONS OF STACK:
 Book in a table
 Shipment in cargo
 Plate on a tray
 Towers of hanoi
 Conversion of infix expression to postfix expression
 Evaluation of arithmetic expression
o An arithmetic expression consists of operands and operators
o Notations: Infix => operand operator operand
o prefix => operator operand operand
o Postfix => operand operand operator

3

, CST35 / Data Structures UNIT - II


CONVERSION OF INFIX EXPRESSION TO POSTFIX EXPRESSION:
Algorithm for converting infix to postfix:
While(tokens are available) // token may be a alphabet or number or operator or ‘(‘ or ‘)’
ch = read(token)
if(ch = = ‘ ( ‘ )
push(ch)
break
end if
if(ch = = ‘ ) ‘ )
pop all operators until ‘(‘ is encountered
break
end if
if ( ch = = operand)
output(ch) (or) Write the operand in postfix expression
else
if ( priority(ch) <= priority( stack[top])
element = pop( )
output(element)
push(ch)
else
push(ch)
end while
write postfix expression
Example 1
Convert the infix expression (a * b) to postfix
Operator stack Input token Postfix expression
Empty
(
(


a a
(




* * a
(




* b ab
(


4