4. Data Structures - Stacks and Queues.pdf

Stacks and queues in C and C++ for both study and interview curated covers almost most of the topics

1. Data Structures and Algorithms (CS-2001)
KALINGA INSTITUTE OF INDUSTRIAL
TECHNOLOGY
School of Computer Engineering
4 Credit Lecture Note
Strictly for internal circulation (within KIIT) and reference only. Not for outside circulation without permission

2. Chapter Contents
School of Computer Engineering
Sr #Major andDetailed Coverage Area Hrs
3Stacks and Queues 8
Stacks,StacksusingDynamicArraysand
LinkedLists,Queues,QueueusingLinkedList,
CircularQueuesusingDynamicArrays,
EvaluationofExpressions,PriorityQueue,
Dequeue
2

3. Introduction
School of Computer Engineering
Thelinearlistsandlineararraysallowedoneto
insertanddeleteelementsatanyplaceinthelist–at
thebeginning,attheendorinthemiddle.Thereare
certainfrequentsituationswhenonewantsto
restrictinsertionsanddeletionssothattheycantake
placeonlyatthebeginningortheendofthelist,not
inthemiddle.Twoofthedatastructuresthatare
usefulinsuchsituationsarestacksandqueues.
3

4. Stack
School of Computer Engineering
Astackisadatastructurethat
worksontheprincipleofLastIn
FirstOut(LIFO).
Lastitemputonthestackisthe
firstitemthatcanbetakenoff.
Newelementsareaddedtoand
removedfromthetopcalledthe
topofthestack.
Stackoperationsmayinvolveinitializingthestack,usingitandthende-initializingit.
Apartfromthesebasicstuffs,astackisusedforthefollowingtwoprimaryoperations−
push−pushing(storing)anelementonthestack.
pop−removing(deleting)anelementfromthestack.
4

5. Stack Application
School of Computer Engineering
Parsing
RecursiveFunction
FunctionCall
ExpressionEvaluation
ExpressionConversion
InfixtoPostfix
InfixtoPrefix
PostfixtoInfix
PrefixtoInfix
TowersofHanoi
5
Sr#ExpressionMeaning
1 Infix Characterizedbytheplacementofoperators
betweenoperands.E.g.plussignin"2+2"
2 Prefix Characterizedbytheplacementofoperators
beforeoperands.E.g.plussignin“+22"
3 Postfix Characterized by the placement of operators
after operands. E.g. plus sign in “ 2 2 +"
Expression Representation

6. Stack Representation
School of Computer Engineering
Stackcanberepresentedusing−
Arrays−Storingtheitemscontiguously
Fixedsize(CalledasStaticStack)
Dynamicsize(CalledasDynamicStack)
LinkedList−Storingitemsnon-contiguously
Dynamicsize(CalledasDynamicStack)
6

7. Stack -Static Array Representation
School of Computer Engineering
Static Array Declaration & Definition:
DEFINE N NUM [NUM represents whole number e.g. In C, equivalent statement is #define N 100]
INTEGER STACK[N]
INTEGER TOP = 0
7
1 5 4
1 23 4 5 6 7 8
TOP3
TOP = 0 indicates that the stack is empty and TOP = N indicates that the stack is full
Position
Pictorial Representation

8. Stack Operation using Static Array
School of Computer Engineering
1.Start
2.IFTOP=NTHEN
DISPLAYOverflow
EXIT
ENDIF
3.TOP=TOP+1
4.STACK[TOP]=ITEM[InsertItemintonewTOPPosition]
5.Stop
1.Start
2.IFTOP=0THEN
DISPLAYUnderflow
EXIT
ENDIF
3.SETITEM=STACK[TOP][Callbyreference]
4.TOP=TOP-1
5.Stop
PUSH(STACK, TOP, N, ITEM) POP(STACK, TOP, ITEM)
8
push−pushing(storing)anelementonthe
stack.
pop−removing(deleting)anelementfromthe
stack
Peek-getthetopdataelementofthestack,
withoutremovingit.
1.Start
2.IFTOP=0THEN
DISPLAYUnderflow
EXIT
ENDIF
3.SETITEM=STACK[TOP][Callbyreference]
4.Stop
PEEK(STACK, TOP, ITEM) Operation Description

9. Class Work
School of Computer Engineering
9
1.DesignaPushalgorithmusingdynamicarray
2.DesignaPopalgorithmusingdynamicarray
3.Designanalgorithmtorealizetwostacksinsinglestaticarray
4.Designanrecursivealgorithmtoreversethestack

10. Stack -Linked List Representation
School of Computer Engineering
Sincealltheactionhappensatthetopofthestack,asinglelinkedlistisafinewayto
representthestackwhereintheheader/startalwayspointstothetopofthestack.
CC XAABB
Represents Top
Pushingisinsertinganelementatthefrontofthelist
Poppingisremovinganelementfromthefrontofthelist
Push
CC XAABB
Before Push
CC XAABBDD
After Push
10

11. Stack -Linked List Representation
Pop
CC XAABB
Before Pop
CC XAABBDD
After Pop
School of Computer Engineering
11
Stack Node Representation
structnode
{
intinfo;
structnode*next;
}*top;
N represents NULL

12. Push Function
School of Computer Engineering
12
voidpush()
{
intdata;
scanf(“%d”,&data);
if(top==NULL)
{
top=(structnode*)malloc(*sizeof(structnode));
top->next=NULL;
top->info=data;
}
else
{
structnode*temp=(structnode*)malloc(*sizeof(structnode));
temp->next=top;
temp->info=data;
top=temp;
}
Top
Top
B
XA
B
XA
C
C
PUSH
X represents NULL

13. Pop Function
School of Computer Engineering
13
voidpop()
{
structnode*tempTop=top;
if(tempTop==NULL)
{
printf("\nError");
return;
}
else
tempTop=tempTop->next;
printf("\nPoppedvalue:%d",top->info);
free(top);
top=tempTop;
Top
Top
B
XA
B
XA
C
POP
X represents NULL

14. Arithmetic Expression : Polish Notation
Thewaytowritearithmeticexpressionisknownasanotation.PolishNotation
isawayofexpressingarithmeticexpressionsthatavoidstheuseofbrackets
todefineprioritiesforevaluationofoperators.PolishNotationwasdevisedby
thePolishphilosopherandmathematicianJanŁukasiewicz(1878-1956)foruse
insymboliclogic.
Evaluatethefollowingparenthesis-freearithmeticexpression
2î3+5*2î2–12/6
=8+5*4–12/6=8+20–2=26
Anarithmeticexpressioncanbewritteninthreedifferentbutequivalent
notations,i.e.,withoutchangingtheessenceoroutputofanexpression.These
notationsare−
InfixNotation
PrefixNotation
School of Computer Engineering
14
PostfixNotation

15. Expression Representation
InfixNotation-Wewriteexpressionininfixnotation,e.g.a-b+c,where
operatorsareusedin-betweenoperands.Itiseasyforushumanstoread,
write,andspeakininfixnotationbutthesamedoesnotgowellwith
computingdevices.Analgorithmtoprocessinfixnotationcouldbe
difficultandcostlyintermsoftimeandspaceconsumption.
PrefixNotation-Inthisnotation,operatorisprefixedtooperands,i.e.
operatoriswrittenaheadofoperands.Forexample,+ab.Thisis
equivalenttoitsinfixnotationa+b.Prefixnotationisalsoknownas
PolishNotation.
PostfixNotation-ThisnotationstyleisknownasReversedPolish
Notation.Inthisnotationstyle,theoperatorispostfixedtotheoperands
i.e.,theoperatoriswrittenaftertheoperands.Forexample,ab+.Thisis
equivalenttoitsinfixnotationa+b.
School of Computer Engineering
15

16. Difference in 3 Notation
School of Computer Engineering
16
Sr#Infix Prefix Postfix
1 a + b + a b a b +
2 (a + b) ∗c ∗+ a b c a b + c ∗
3 a ∗(b + c) ∗a + b c a b c + ∗
4 a / b + c / d+ / a b / c da b / c d / +
5 (a + b) ∗(c + d)∗+ a b + c da b + c d + ∗
6 ((a + b) ∗c) -d-∗+ a b c d a b + c ∗d -
Example

17. Parsing Expression
School of Computer Engineering
17
Parsingistheprocessofanalyzingacollectionofsymbols,eitherinnaturallanguageorin
computerlanguages,conformingtotherulesofaformalgrammar.
Itisnotaveryefficientwaytodesignanalgorithmorprogramtoparseinfixnotations.
Instead,theseinfixnotationsarefirstconvertedintoeitherpostfixorprefixnotations
andthencomputed.Toparseanyarithmeticexpression,weneedtotakecareofoperator
precedenceandassociativityalso.
Precedence:-Whenanoperandisinbetweentwodifferentoperators,whichoperator
willtaketheoperandfirst,isdecidedbytheprecedenceofanoperatoroverothers.For
example−a+b*ca+(b*c)
Associativity:-Itdescribestherulewhereoperatorswiththesameprecedenceappear
inanexpression.Forexample,inexpressiona+b−c,both+and–havethesame
precedence,thenwhichpartoftheexpressionwillbeevaluatedfirst,isdeterminedby
associativityofthoseoperators.Here,both+and−areleftassociative,sotheexpression
willbeevaluatedas(a+b)−c.

18. Parsing Expression cont…
School of Computer Engineering
18
Precedenceandassociativitydeterminestheorderofevaluationofanexpression.
Followingisanoperatorprecedenceandassociativitytable(highesttolowest)−
Sr# Operator Precedence Associativity
1 Exponentiation (^ or î) Highest Right Associative
2 Multiplication ( ∗),Division ( / ) and
Modular Division ( % )
Second HighestLeft Associative
3 Addition ( + ) & Subtraction ( −) Lowest Left Associative
Theabovetableshowsthedefaultbehaviorofoperators.Atanypointoftimein
expressionevaluation,theordercanbealteredbyusingparenthesis.
Forexample−Ina+b*c,theexpressionpartb*cwillbeevaluatedfirst,with
multiplicationasprecedenceoveraddition.Wehereuseparenthesisfora+btobe
evaluatedfirst,like(a+b)*c.

19. Arithmetic Expression Conversion
School of Computer Engineering
Infix expression to Prefix notation
(A+B)*C=[+AB]*C=*+ABCwhere[]indicatesapartialtranslation
A+(B*C)=A+[*BC]=+A*BC
(A+B)/(C-D)=[+AB]/[-CD]=/+AB-CD
19
Infix expression to Postfix notation
(A+B)*C=[AB+]*C=AB+C*where[]indicatesapartialtranslation
A+(B*C)=A+[BC*]=ABC*+
(A+B)/(C-D)=[AB+]/[CD-]=AB+CD-/
Orderinwhichtheoperationsaretobeperformediscompletelydeterminedbythe
positionsoftheoperatorsandoperandintheexpression.Accordingly,onenever
needsparenthesiswhenwritingexpressioninPolishnotations
Note

20. Why Postfix and Prefix?
School of Computer Engineering
Postfix:
Computerusuallyevaluatesanarithmeticexpressionwrittenininfixnotationin
twosteps:
1
st
Step-ConvertstheinfixnotationtoPostfixnotation
2
nd
Step-EvaluatesthePostfixexpression.
Ineachstep,stackisthemaintoolusedtoaccomplishthegiventask.
Prefix:
HasseenwideapplicationinLisp(programminglanguage)s-expressions
DataCompressionwithPrefixEncoding
Standardscientificprefixesareusedtodenotepowersof10e.g.kilo=1e
3
mega=1e
6
giga=1e
9
20
tera=1e
12
peta=1e
15
exa=1e
18

21. Evaluation of a Postfix Expression
School of Computer Engineering
1.Start
2.ValidatethePostfixexpressionforcorrectness
a)‘(‘and‘)’areinpairs
b)Operatorisaftertheoperands[Binaryoperatorsareconsideredonly]
3.Addarightparenthesis‘)”attheendofP.[Thisactasdelimiter]
4.ScanPfromlefttorightandrepeatsteps5and6foreachelementofPuntilthe
delimiter“)”isencountered
5.Ifanoperandisencountered,putitonSTACK
6.Ifanoperatorisencountered,then
(a)RemovethetwotopelementsofSTACK,whereAisthetopelementandBisthe
next-to-topelement
(b)EvaluateBA
(c)Placetheresultofstep(b)onSTACK
7.SetvalueofthepostfixexpressionequaltothetopelementofSTACK
8.Stop
21

22. Example
School of Computer Engineering
P=5,6,2,+,*,12,4,/,-[Postfix]
Note–CommasareusedtoseparatetheelementsofPsothat5,6,2isnotinterpretedas562.
P: (after adding a sentinel right parenthesis at the end of P)
5 6 2 + * 12 4 / -)
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10)
Symbol Scanned STACK
(1) 5 5
(2) 6 5 6
(3) 2 5 6 2
(4) + 5 8
(5) * 40
(6) 12 4012
Symbol Scanned STACK
(7) 4 40124
(8) / 403
(9) - 37
(10) )
22
Q=5*(6+2)–12/4istheequivalantInfixexpression

23. Class Work
School of Computer Engineering
23
ConsiderthefollowingarithmeticexpressionP,writteninpostfixnotation:
P=12,7,3,-,/,2,1,5,+,*,+
1.Evaluatetheabovepostfixexpression
2.Byinspection,translatePintoitsequivalentinfixexpression
3.Evaluatetheconvertedinfixexpression
Q=12/(7-3)+2*(1+5)=15

24. Evaluation of a Prefix Expression
School of Computer Engineering
24
1.Start
2.ValidatethePrefixExpressionforcorrectness
a)‘(‘and‘)’areinpairs
b)Operatorisbeforetheoperands[Binaryoperatorsareconsideredonly]
3.ScanPfromrighttoleftandrepeatsteps5and6foreachelementofPuntilitends.
4.Ifanoperandisencountered,putitonSTACK
5.Ifanoperatorisencountered,then
(a)RemovethetwotopelementsofSTACK,whereAisthetopelementandBisthe
next-to-topelement
(b)EvaluateAB
(c)Placetheresultofstep(b)onSTACK
6.SetvalueoftheprefixexpressionequaltothetopelementofSTACK
7.Stop

25. Example
School of Computer Engineering
25
Symbol scanned STACK
(1) 5 5
(2) 2 5 2
(3) 3 5 2 3
(4) 4 5 2 34
(5) + 5 2 7
(6) * 5 14
(7) - 9
P=-,*,+,4,3,2,5[Prefix]
Note–CommasareusedtoseparatetheelementsofP
-* + 4 3 2 5
(7) (6) (5) (4) (3) (2) (1)

26. Infix to Postfix Conversion
School of Computer Engineering
Qisanarithmeticexpressionwrittenininfixnotation.ThisalgorithmInfixToPostfix(Q,P)findstheequivalent
postfixnotationwherePistheequivalentpostfixnotation–
1.Start
2.ValidatetheInfixexpressionforcorrectness
a)‘(‘and‘)’areinpairs
b)Operatorisbetweentheoperands[Binaryoperatorsareconsideredonly]
3.Push“(“ontoSTACKand“)”totheendofQ
4.ScanQfromLefttoRightandRepeatSteps5to8foreachelementofQuntiltheSTACKisempty
5.Ifanoperandisencountered,addittoP
6.Ifaleftparenthesisisencountered,pushitontoSTACK
7.Ifanoperatorisencountered,then:
(a)RepeatedlypopfromSTACKandaddtoPeachoperatorwhichhassameprecedenceorhigherprecedence
than.
(b)AddtoSTACK.
8.Ifarightparenthesisisencountered,then
(a)RepeatedlypopfromtheSTACKandaddtoPeachoperatoruntilaleftparenthesisisencountered.
(b)Removetheleftparenthesis.[DonotaddittoP]
9.Stop
26

27. Example
School of Computer Engineering
Q:A+(B*C–(D/EîF)*G)*H
Sofirst,wepush“(“ontostack,andthenadd“)”totheendoftheQtoobtain:
A+(B*C-(D/EîF)*G)*H)
1234567891011121314151617181920
Symbol Scanned STACK Expression P
1 A ( A
2 + ( + A
3 ( ( + ( A
4 B ( + ( A B
5 * ( + ( * A B
6 C ( + ( * A B C
7 - ( + ( - A B C *
27

28. Example cont…
School of Computer Engineering
Symbol Scanned STACK Expression P
8 ( ( + ( -( A B C *
9 D ( + ( -( A B C * D
10/ ( + ( -( / A B C * D
11E ( + ( -( / A B C * D E
12î ( + ( -( / î A B C * D E
13F ( + ( -( / î A B C * D E F
14) ( + ( - A B C * D E F î /
15* ( + ( -* A B C * D E F î /
16G ( + ( -* A B C * D E F î /G
17) ( + A B C * D E F î / G * -
18* ( + * A B C * D E F î / G * -
19H ( + * A B C * D E F î / G * -H
20) A B C * D E F î / G * -H * +
28
A+(B*C-(D/EîF)*G)*H)
1234567891011121314151617181920

29. Class Work
School of Computer Engineering
29
ConsidertheinfixexpressionQ:((A+B)*D)î(E-F).TranslateQintoitsequivalent
postfixexpressionP
Symbol Scanned STACK Expression P
1 ( ( (
2 ( ( ( (
3 A ( ( ( A
4 + ( ( ( + A
5 B ( ( ( + A B
6 ) ( ( A B +
7 * ( ( * A B +
8 D ( ( * A B + D
9 ) ( A B + D *
10 î ( î A B + D *
11 ( ( î ( A B + D *
12 E ( î ( A B + D * E
13 - ( î ( - A B + D * E F
14 F ( î ( - A B + D * E F
15 ) ( î A B + D * E F –
16 A B + D * E F –î

30. Infix to Prefix Conversion
School of Computer Engineering
Qisanarithmeticexpressionwrittenininfixnotation.ThisalgorithmInfixToPrefix(Q,P)findsthe
equivalentpostfixnotationwherePistheequivalentprefixnotation–
1.Start
2.ValidatetheInfixexpressionforcorrectness
a)‘(‘and‘)’areinpairs
b)Operatorisbetweentheoperands[Binaryoperatorsareconsideredonly]
3.Reversetheexpression
4.CALLInfixToPostfix(Q,P)
5.Reversetheexpression
6.Stop
30
Example:Infixnotation:A+B*C
Step1–Infixexpressioniscorrect
Step2–ReversingtheexpressionresultingtoC*B+A
Step3–Postfixexpressionproducedinstep2isCB*A+
Step4–Reversingtheexpressionproducedinstep3is+A*BC
Result:+A*BC

31. Example cont…
School of Computer Engineering
Q:(A+BîC)*D+EîF
Step1–Infixexpressioniscorrect
Step2–
a)ReversingtheexpressionproduceFîE+D*)CîB+A(
b)Reversethebracket,somakingevery'('as')'andevery')'as'(‘
revisedexpressionisFîE+D*(CîB+A)
Step3–Postfixexpressionofstep2produceFEîDCBîA+*+
Step4–Reversingtheexpressionproducedinstep3becomes
+*+AîBCDîE5
Result:+*+AîBCDîE5
31

32. School of Computer Engineering
32
Home Work
Readthefollowingatyourownpace:
PostfixtoInfixconversion–
http://scanftree.com/Data_Structure/postfix-to-infix
PrefixtoInfixconversion–
http://scanftree.com/Data_Structure/prefix-to-infix
PostfixtoPrefixconversion–
http://see-programming.blogspot.in/2013/05/postfix-to-prefix-conversion.html
PostfixtoPrefixconversion–
http://www.manojagarwal.co.in/conversion-from-prefix-to-postfix/

33. Queue
School of Computer Engineering
Aqueueisadatastructurethatmodels/enforcesthefirst-comefirst-serveorder,or
equivalentlythefirst-infirst-out(FIFO)order.
Theelementthatisinsertedfirstintothequeuewillbetheelementthatwill
deletedfirst,andtheelementthatisinsertedlastisdeletedlast.
Itemsareinsertedoneend(rearend)anddeletedfromtheotherend(frontend).
Queuebasicoperationsare−
enqueue−insertelementatrear
dequeue−Removeelementfromfront
peek−Examinetheelementatfrontwithoutremovingitfromqueue
33

34. Queue Application
School of Computer Engineering
queueofprintjobstosendtotheprinter
queueofprograms/processestoberun
queueofnetworkdatapacketstosend
Operating System
modelingalineofcustomersorclients
storingaqueueofcomputationstobeperformedinorder
Programming
peopleonanescalatororwaitinginaline
carsatagasstation(oronanassemblyline)
Real World
34

35. Queue Representation
School of Computer Engineering
Queuecanberepresentedusing−
StaticArrays−Storingtheitemscontiguously
StaticQueueduetofixedsize
Spaceiswastedifweuselesselements
cannotinsertmoreelementsthanthearraycanhold
DynamicArrays−Storingtheitemscontiguously
DynamicQueue
LinkedList−Storingitemsnon-contiguously
DynamicQueue
35

36. Queue -Static Array Representation
School of Computer Engineering
36
Static Array Declaration & Definition:
DEFINE N NUM [NUM represents whole number e.g. In C, equivalent statement is #define N 100]
INTEGER QUEUE[N]
INTEGER REAR = 0
INTEGER FRONT = 0
4 8 6
1 2 3 4 5 6 7 8Position
Keepstrackofthenumberofitemsinthequeueandthepositionofthefrontelement
(atthefrontofthequeue),therearelement(attherear).Thepositionofthefront
elementisstoredinthefrontmembervariable.Thenextitemisafterthefirstoneand
soonuntiltherearofthequeuethatoccursattheindexstoredinamembervariable
calledrear.
FRONT = 0 and REAR = 0 indicates that the queue is empty and REAR = N indicates that the
queue is full
FRONT1 REAR3Pictorial Representation

37. Enqueue Operation
School of Computer Engineering
Let’sanelemententersthequeue…
1 2 3 4 5 6. . .
FRONT0
REAR0
37
7
1 2 3 4 5 6. . .
FRONT1
REAR1
Afteraseriesofinsertion,thestateofthequeueis
7
1 2 3 4 5 6. . .
FRONT1
REAR4
21012

38. Enqueue Algorithm
School of Computer Engineering
1.Start
2.IF(REAR=N)THEN
DISPLAY“OVERFLOW”
EXIT
ENDIF
3.IF(FRONT=0ANDREAR=0)THEN[Queueinitiallyempty]
FRONT=1
REAR=1
ELSE
REAR=REAR+1
ENDIF
4.QUEUE[REAR]=ITEM[Thisinsertsnewelement]
5.Stop
SQINSERT(QUEUE, N, FRONT, REAR, ITEM)
38

39. Dequeue Operation
School of Computer Engineering
Let’sanelementleavesthequeue
. . .
4 8 6
4 8 6
FRONT1
REAR3
FRONT2
REAR3
39
1 2 3 4 5 6
. . .1 2 3 4 5 6
Afteraseriesofdeletion,thestateofthequeueis
6
FRONT3
REAR3
1 2 3 4 5 6

40. Dequeue Algorithm
School of Computer Engineering
1.Start
2.IFFRONT=0THEN
DISPLAY“UNDERFLOW“
EXIT
ENDIF
3.ITEM=QUEUE[FRONT]
4.IF(FRONT==REAR)THEN[Checkifonlyoneelementisleft]
FRONT=1
REAR=1
ELSE
FRONT=FRONT+1[IncrementFRONTby1]
ENDIF
5.RETURNITEM
6.Stop
ITEM SQDELETE(QUEUE, FRONT, REAR)
40

41. Queue Linked Representation
School of Computer Engineering
Nodesconnectedinachainbylinks
41
Node Representation
structnode
{
charinfo[50];
structnode*next;
}*front,*rear;

42. Enqueue Operation
School of Computer Engineering
Post Insertion
42

43. Enqueue Algorithm
School of Computer Engineering
BEGIN
structlist*node=(structnode*)malloc(sizeof(structnode));
node->info=ITEM;
node->next=NULL;
IF(FRONT==NULL)THEN
FRONT=node
REAR=node
ELSE
REAR->next=node
REAR=node
ENDIF
END
43
LLQINSERT(structnode*FRONT,structnode*REAR,ITEM)

44. Dequeue Operation
School of Computer Engineering
Post Deletion
44

45. Dequeue Algorithm
School of Computer Engineering
BEGIN
IF(FRONT=NULL)THEN
DISPLAY“QueueUnderflow"
EXIT
ENDIF
struct*nodetemp=FRONT
ITEM=temp->info
FRONT=FRONT->next
FREE(temp)
RETURNITEM
END
45
ITEMLLQDELETE(structnode*FRONT)

46. Class Work
School of Computer Engineering
46
1.DesignaDequealgorithmusingdynamicarray
2.DesignanEnqueuealgorithmusingdynamicarray

47. Linear Queue Drawback
School of Computer Engineering
Oncethelinearqueueisfull,eventhoughfewelementsfromthefrontaredeleted&some
occupiedspaceisrelieved,itisnotpossibletoaddanymorenewelements,astherearhas
alreadyreachedthequeue’srearmostposition.
Thissituationalsosaysthatqueueisfullandwecannotinsertthenew
elementbecause,'rear'isstillatlastposition.Inabovesituation,even
thoughwehaveemptypositionsinthequeuewecannotmakeuseofthem
toinsertnewelement.Thisisthemajorprobleminnormalqueuedata
structure.Toovercomethisproblemweusecircularqueuedatastructure.
47
Delete 3 elements

48. Circular Queue
School of Computer Engineering
CircularQueueisalineardatastructureinwhichtheoperationsareperformedbasedon
FIFO(FirstInFirstOut)principleandthelastpositionisconnectedbacktothefirst
positiontomakeacircleandthegraphicalrepresentationofacircularqueueisas
follows...
Incircularqueue,oncetheQueueisfullthe"First"element
oftheQueuebecomesthe"Rear"mostelement,ifandonly
ifthe"Front"hasmovedforward.otherwiseitwillagainbe
a"Queueoverflow"state.
48

49. Circular Queue Enqueue Algorithm
School of Computer Engineering
1.Start
2.IF(FRONT=0ANDREAR=0)THEN
FRONT=1
GOTOSTEP5
ENDIF
3.IF(FRONT=1ANDREAR=N)OR(FRONT=REAR+1)THEN
DISPLAY“CircularQueueOverflow”
EXIT
ENDIF
4.IF(REAR=N)THEN
REAR=1
GOTOSTEP6
ENDIF
5.REAR=REAR+1
6.QUEUE[REAR]=ITEM
7.Stop
49
CQINSERT(QUEUE, N, FRONT, REAR, ITEM)

50. Circular Queue Dequeue Algorithm
School of Computer Engineering
1.Start
2.IF(FRONT=0)THEN
DISPLAY“CircularQueueUnderflow”
EXIT
ENDIF
3.ITEM=QUEUE[FRONT]
4.IFFRONT=NTHEN
FRONT=1
RETRUNITEM
ENDIF
50
ITEM CQDELETE(QUEUE, N, FRONT, REAR)
[Continuationofalgorithm]
5.IF(FRONT=REAR)THEN
FRONT=0
REAR=0
RETURNITEM
ENDIF
6.FRONT=FRONT+1
7.RETURNITEM
8.Stop

51. Circular Queue Example
School of Computer Engineering
1. Initially, Rear = 0, Front = 0.
2. Insert 10, Rear = 1, Front = 1.
Rear
Front
3. Insert 50, Rear = 2, Front = 1.
Rear
Front
4. Insert 20, Rear = 3, Front = 0.
Rear
Front
51

52. Circular Queue Example cont…
School of Computer Engineering
5. Insert 70, Rear = 4, Front = 1.
6. Delete front, Rear = 4, Front = 2.
Rear
Rear
Front
Front
7. Insert 100, Rear = 5, Front = 2.
8. Insert 40, Rear = 1, Front = 2.
Front
Rear
FrontRear
52

53. Class Work -Circular Queue
School of Computer Engineering
53
1.DesignanEnqueuealgorithmusingdynamicarray
2.DesignaDequeuealgorithmusingdynamicarray
3.DesignanEnqueuealgorithmusingLinkedList
4.DesignaDequeuealgorithmusingLinkedList

54. Deques
School of Computer Engineering
Adequeisadouble-endedqueue
Insertionsanddeletionscanoccurateither
end,butnotinthemiddle
Implementationissimilartothatforqueues
Dequesarenotheavilyused
Youshouldknowwhatadequeis,butwe
won’texplorethemmuchfurther
Thereare2typesofdequeasexplainbelow-
Input-restricted Deque
Elementscanbeinsertedonlyatone
end.
Elementscanberemovedfromboth
theends
Output-restricted Deque
Elementscanberemovedonlyatone
end.
Elementscanbeinsertedfromboththe
ends.
54

55. Deques Construction
School of Computer Engineering
TheDequeuecanbeconstructedintwowaysandare:
1)UsingArray2)UsingLinkedList
StaticArrays:FRONTisinitializedto0,REARisinitializedtoNwhereN
representsarraylength
55
ENQUE_FRONT(QUEUE, FRONT, REAR, ITEM)
1.Start
2.IF(FRONT=REAR)[QUEUEisFull]
Display“Overflow”
EXIT
ENDIF
3.FRONT=FRONT+1
4.QUEUE[FRONT]=ITEM
5.Stop
ENQUE_REAR(QUEUE, FRONT, REAR, ITEM)
1.Start
2.IF(REAR=FRONT)[QUEUEisFull]
Display“Overflow”
EXIT
ENDIF
3.QUEUE[REAR]=ITEM
4.REAR=REAR-1
5.Stop

56. Deques Construction cont…
School of Computer Engineering
56
ITEM DEQUE_FRONT(QUEUE, FRONT, REAR)
1.Start
2.IF(FRONT=0)[QUEUEisEmpty]
DISPLAY“Underflow”
EXIT
ENDIF
3.ITEM=QUEUE[FRONT]
4.FRONT=FRONT-1
5.RETURNITEM
6.Stop
ITEMDEQUE_REAR(QUEUE, N, FRONT, REAR)
1.Start
2.IF(REAR=N)[QUEUEisEmpty]
DISPLAY“Underflow”
EXIT
ENDIF
4.ITEM=QUEUE[REAR]
5.REAR=REAR+1
6.RETURNITEM
7.Stop

57. Class Work -Deques
School of Computer Engineering
57
1.DesignanEnqueuealgorithmusingdynamicarray
2.DesignaDequeuealgorithmusingdynamicarray
3.DesignanEnqueuealgorithmforusingLinkedList
4.DesignaDequeuealgorithmusingLinkedList

58. Priority Queues
School of Computer Engineering
Apriorityqueueisacollectionofelementssuchthateachelementhasbeen
assignedapriorityandsuchthattheorderinwhichelementsaredeletedand
processedcomesfromthefollowingrules–
Anelementofhigherpriorityisprocessedbeforeanyelementoflower
priority
Twoelementswiththepriorityareprocessedaccordingtotheorderinwhich
theywereaddedtothequeue.
Maintainingpriorityqueuesare–
One-WayList
Array
58

59. Priority Queue -One-Way List Representation
School of Computer Engineering
Eachnodeinthelistwillcontainthreeitemsofinformation:aninformation
fieldINFO,aprioritynumberPRNandalinknumberLINK.
AnodeXprecedesanodeYinthelistwhen:
XhashigherprioritythanYor
WhenbothhavethesameprioritybutXwasaddedtothelistbeforeY.
1A 2B 2C 3D
Head
59
Systematic diagram

60. Priority Queue -One-Way List Representation
School of Computer Engineering
60
Node Representation
structnode
{
intinfo;
intprn;
structnode*next;
}*top;
Deletion
1.Start
2.Visittothesecondlastnodeinthechain
3.MakethesecondlastnodenextfieldtoNULL
4.Freethelastnode
6.Stop
Insertion with Priority N and ITEM
1.Start
2.TraversethelistuntilfindinganodeXwhoseprioritynumberexceedsthe
priorityN.
3.IfnodefoundthenInsertITEMinfrontofnodeX
4.Ifnosuchnodeisfound,insertITEMasthelastitemofthelist
5.Stop

61. Priority Queue -Array Representation
School of Computer Engineering
Anotherwaytomaintainapriorityqueueinmemoryistouseaseparatequeueforeachpriority
number.
Eachsuchqueuewillappearinitsowncirculararrayandmusthaveitsownpairofpointers,
FRONTandREAR
Ifeachqueueisallocatedthesameamountofspace,atwo–dimensionalarrayQUEUEcanbe
usedinsteadofthelineararray
FRONT[K]andREAR[K]containsthefrontandrearelementsofrowKofqueue,therowthat
maintainsthequeueofelementswithprioritynumberK
61
FRONT REAR
Systematic diagram
1
2
3
4
5
2
1
0
5
4
2
3
0
1
4
Priority
1 2 3 4 5
1 A
2 B C G
3
4 E D
5 F

62. Priority Queue –Array Representation cont…
School of Computer Engineering
62
Deletion
1.Start
2.FindthesmallestKsuchthatFRONT[K]<>NULL
3.DeleteandProcessthefrontelementinrowKofQueue
4.Stop
Insertion
1.Start
2.InsertITEMastherearelementinrowMofqueue
3.Stop

63. Assignments
School of Computer Engineering
Writeanalgorithmtoconvertaninfix
expressionintoitequivalentpostfixexpression.
Explaintheexecutionofalgorithmusingthe
followingexpression.
(A+B)*C–(D*E)î(F+G+(H*M))
Writepseudocodetocheckwhetheragiven
postfixexpressioniscorrectlyparenthesized
Assignment 1 Assignment 2
63
Assignment 3
Evaluatethefollowingpostfixexpression:
532*+79/4*2/-6+2-
WriteCfunctionsforinsertion,deletion,
traversaloperationforcircularqueues
Assignment 4
Writeanalgorithmtocopythedataelementsof
onestacktootherwithoutchangingtheorder
andwithoutusinganyotherdatastructure
Assignment 5
WriteCfunctionsforinsertion,deletion,
traversaloperationforinputrestricteddeques
Assignment 6
WriteCfunctionsforinsertion,deletion,
traversaloperationforpriorityqueues
Assignment 7

64. Assignments
School of Computer Engineering
Writeanalgorithmtocheckforbalanced
parentheses(,),{,},[and]inanexpression
Writepseudocodeforrecursivefunctionto
displaythestringinreverseorder.
Assignment 8 Assignment 9
64
Writeanalgorithmtoconvertpostfixexpression
toinfixexpression.
Writeanalgorithmtoconvertprefixexpression
toinfixexpression.
Assignment 10 Assignment 11
Writeanalgorithmtoconvertpostfixexpression
toprefixexpression.
Writeanalgorithmtoconvertprefixexpression
topostfixexpression.
Assignment 12 Assignment 13
Assignment 14
WriteanalgorithmforTowerofHanoi(iterativelyandrecursively).
Assignment 15
Wearegivenstackdatastructure,thetaskistoimplementqueueusingonlygivenqueue
datastructure.

65. School of Computer Engineering
65

66. Home Work (HW)
1.Youaregiven2queueswhereeachqueuecontainstimestamppairprice.Youhaveto
print<price1price2>forallthosetimestampswhereabs(ts1–ts2)<=1second
wherets1andprice1from1stqueueandts2andprice2from2ndqueue.
2.Givenanarray,printtheNextGreaterElement(NGE)foreveryelement.TheNext
greaterElementforanelementxisthefirstgreaterelementontherightsideofxin
array.Elementsforwhichnogreaterelementexist,considernextgreaterelementas
-1.Examples:
a)Foranyarray,rightmostelementalwayshasnextgreaterelementas-1.
b)Foranarraywhichissortedindecreasingorder,allelementshavenextgreater
elementas-1.
c)Fortheinputarray[4,5,2,25},thenextgreaterelementsforeachelementareas
follows.
ElementNGE
4 5
5 25
2 25
25 -1
66
School of Computer Engineering

67. Home Work (HW)
3.Implementastackusingqueues
4.Implementaqueueusingstacks
5.InapartyofNpeople,onlyonepersonisknowntoeveryone.Suchapersonmaybe
presentintheparty,ifyes,(s)hedoesn’tknowanyoneintheparty.Wecanonlyask
questionslike“doesAknowB?“.Findthestranger(celebrity)inminimumnumber
ofquestions.
6.Findthelargestrectangularareapossibleinagivenhistogramwherethelargest
rectanglecanbemadeofanumberofcontiguousbars.Forsimplicity,assumethatall
barshavesamewidthandthewidthis1unit.Forexample,considerthefollowing
histogramwith7barsofheights{6,2,5,4,5,1,6}.Thelargestpossiblerectangle
possibleis12(seethebelowfigure,themaxarearectangleishighlightedinred)
67
School of Computer Engineering

68. Home Work (HW)
7.Supposethereisacircle.Therearenpetrolpumpsonthatcircle.Youaregiventwo
setsofdata.
1.Theamountofpetrolthateverypetrolpumphas.
2.Distancefromthatpetrolpumptothenextpetrolpump.
Calculatethefirstpointfromwhereatruckwillbeabletocompletethecircle(The
truckwillstopateachpetrolpumpandithasinfinitecapacity).Expectedtime
complexityisO(n).Assumefor1litrepetrol,thetruckcango1unitofdistance.
Forexample,lettherebe4petrolpumpswithamountofpetrolanddistancetonext
petrolpumpvaluepairsas{4,6},{6,5},{7,3}and{4,5}.Thefirstpointfromwhere
truckcanmakeacirculartouris2ndpetrolpump.Outputshouldbe“start=1”
(indexof2ndpetrolpump).
68
School of Computer Engineering

69. Home Work (HW)
8.Givenanarrayofnon-negativeintegers.Findthelargestmultipleof3thatcanbe
formedfromarrayelements.Forexample,iftheinputarrayis{8,1,9},theoutput
shouldbe“981”,andiftheinputarrayis{8,1,7,6,0},outputshouldbe“8760”.
9.Givenanarrayandanintegerk,findthemaximumforeachandeverycontiguous
subarrayofsizek.
Examples:
Input:
arr[]={1,2,3,1,4,5,2,3,6},k=3
Output:
3345556
Input:
arr[]={8,5,10,7,9,4,15,12,90,13},k=4
Output:
10101015159090
69
School of Computer Engineering

70. Home Work (HW)
10.Wearegivenqueuedatastructure,thetaskistoimplementstackusingonlygiven
queuedatastructure.
11.Givenamatrixofdimensionm*nwhereeachcellinthematrixcanhavevalues0,1
or2whichhasthefollowingmeaning:
0:Emptycell,1:Cellshavefreshoranges,2:Cellshaverottenoranges.
Sowehavetodeterminewhatistheminimumtimerequiredsothatalltheoranges
becomerotten.Arottenorangeatindex[i,j]canrototherfreshorangeatindexes[i-
1,j],[i+1,j],[i,j-1],[i,j+1](up,down,leftandright).Ifitisimpossibletorotevery
orangethensimplyreturn-1.
Examples:
Input:arr[][C]={{2,1,0,2,1},
{1,0,1,2,1},
{1,0,0,2,1}};
Output:
Allorangescanbecomerottenin2timeframes.
70
School of Computer Engineering

71. Supplementary Reading
http://www.geeksforgeeks.org/stack-data-structure/
http://www.geeksforgeeks.org/queue-data-structure/
https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm
https://www.tutorialspoint.com/data_structures_algorithms/dsa_queue.htm
http://www.geeksforgeeks.org/implement-stack-using-queue/
http://www.geeksforgeeks.org/queue-using-stacks/
http://nptel.ac.in/courses/106102064/2
http://nptel.ac.in/courses/106102064/3
http://freevideolectures.com/Course/2279/Data-Structures-And-Algorithms/2
http://freevideolectures.com/Course/2279/Data-Structures-And-Algorithms/3
71
School of Computer Engineering

72. FAQ
WhatisStack?
Stacksaredatastructuresthatallowustoinsertandremoveitems.Theoperate
likeastackofpapersorbooksonourdesk-weaddnewthingstothetopofthe
stacktomakethestackbigger,andremoveitemsfromthetopaswelltomake
thestacksmaller.ThismakesstacksaLIFO(LastInFirstOut)datastructure–
thedatawehaveputinlastiswhatwewillgetoutfirst.
Beforeweconsidertheimplementationtoadatastructureitishelpfulto
considertheoperations.Wethenprogramagainstthespecifiedoperations.
Basedonthedescriptionabove,werequirethefollowingfunctions:
boolstack_empty(stackS);/*O(1),checkifstackempty*/
stackstack_new();/*O(1),createnewemptystack*/
voidpush(stackS,eleme);/*O(1),additemontopofstack*/
elempop(stackS) /*O(1),removeitemfromtop*/
72
School of Computer Engineering

73. FAQ cont…
WhatisQueue?
Aqueueisadatastructurewhereweaddelementsatthebackandremove
elementsfromthefront.Inthatwayaqueueislike“waitinginline”:thefirst
onetobeaddedtothequeuewillbethefirstonetoberemovedfromthequeue.
ThisisalsocalledaFIFO(FirstInFirstOut)datastructure.
Beforeweconsidertheimplementationtoadatastructureitishelpfulto
considertheoperations.Wethenprogramagainstthespecifiedoperations.
Basedonthedescriptionabove,werequirethefollowingfunctions:
boolqueue_empty(queueQ);/*O(1),checkifqueueisempty*/
queuequeue_new();/*O(1),createnewemptyqueue*/
voidenq(queueQ,elems);/*O(1),additematback*/
elemdeq(queueQ);/*O(1),removeitemfromfront*/
73
School of Computer Engineering

74. FAQ cont…
ImplementStackusingQueue:Wearegivenastackdatastructurewithpush
andpopoperations,thetaskistoimplementaqueueusinginstancesofstack
datastructureandoperationsonthem.
74
School of Computer Engineering
Solution: http://www.geeksforgeeks.org/queue-using-stacks/

75. FAQ cont…
ImplementQueueusingStack:Wearegivenaqueuedatastructurewith
enqueueanddequeoperations,thetaskistoimplementastackusinginstances
ofqueuedatastructureandoperationsonthem.
75
School of Computer Engineering
Solution: http://www.geeksforgeeks.org/implement-stack-using-queue/