College aantekeningen

data stuctures

0 keer verkocht

Vak
U20EST356 (U20EST356)

Instelling
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.

[Meer zien]

Voorbeeld 4 van de 44 pagina's

Bekijk voorbeeld

Geupload op 1 januari 2023
Aantal pagina's 44
Geschreven in 2022/2023
Type College aantekeningen
Docent(en) Bhavani
Bevat Alle colleges

data stuctures
stack and queue operations

Instelling
Sri Manakula Vinayagar engineering college
Vak
U20EST356 (U20EST356)

$8.49

In winkelwagen

Opslaan

100% tevredenheidsgarantie
Direct beschikbaar na je betaling
Lees online óf als PDF
Geen vaste maandelijkse kosten

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

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!

In een paar klikken geregeld

Geen gedoe — betaal gewoon eenmalig met iDeal, creditcard of je Stuvia-tegoed en je bent klaar. Geen abonnement nodig.

Direct to-the-point

Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.

Van wie koop ik deze samenvatting?

Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper pragatimanimarane. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor $8.49. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 65646 samenvattingen verkocht

Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen

Begin nu gratis

Laatst bekeken door jou

Overig ·

(0)

GDR Full Notes

Essay ·

(0)