Class notes

data stuctures

0 purchase

Course
U20EST356 (U20EST356)

Institution
Sri Manakula Vinayagar Engineering College

Cover every piece of content that could be asked in an exam Have a solid structure for your notes that makes sense ,Evidence you will need for your exam, Examples that help your understanding of an idea.

[Show more]

Preview 4 out of 44 pages

View example

Uploaded on January 1, 2023
Number of pages 44
Written in 2022/2023
Type Class notes
Professor(s) Bhavani
Contains All classes

data stuctures
stack and queue operations

Institution
Sri Manakula Vinayagar engineering college
Course
U20EST356 (U20EST356)

$8.49

Add to cart

Add to wishlist

100% satisfaction guarantee
Immediately available after payment
Both online and in PDF
No strings attached

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

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.

Quick and easy check-out

You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.

Focus on what matters

Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!

Frequently asked questions

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

Satisfaction guarantee: how does it work?

Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.

Who am I buying these notes from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller pragatimanimarane. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy these notes for $8.49. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

68175 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 15 years now

Start selling