0% found this document useful (0 votes)
49 views34 pagesQueue Adt
The document discusses the concept of a Queue Abstract Data Type (ADT) and its implementation using First In First Out (FIFO) methodology. It covers basic operations such as insertion, deletion, and display of elements in a queue, as well as variations like circular queues and priority queues. Additionally, it provides code snippets for implementing these queue structures in programming languages, highlighting memory management and operational conditions.
Uploaded by
JAYALAKSHMI PCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
49 views34 pagesQueue Adt
The document discusses the concept of a Queue Abstract Data Type (ADT) and its implementation using First In First Out (FIFO) methodology. It covers basic operations such as insertion, deletion, and display of elements in a queue, as well as variations like circular queues and priority queues. Additionally, it provides code snippets for implementing these queue structures in programming languages, highlighting memory management and operational conditions.
Uploaded by
JAYALAKSHMI PCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
/ 34
Queve ALT ®
Que ik a liner data atuttue with Firat To ,
Firat Out manne. (FIFO? , The emer Heine inserted for
is the frat ore Pe be taken outs “The clement in a Queue
an added ut one eect calls the Rese anol removed fom
Yhe othor nd Called jhe FONT:
The baie operabiona CC Enguaue, whith
A Desyvout,
inmorh an Cement at The enol of the dit (v001) on
which deletes he cbment at phe utah of fhe ‘bit Cfoa?
antl (ej cama
eT ee oe fame C2?
tion OF Cveve ADT:
Agsey TMpcemennarion
CE a a a
_ 7 & ce ¥ ime ei
ie Cae as
inserkon
receaer ie eee
ra ere Tm OS ME ARCHIE Sat cnt? eH eee
Anton
allele fe] ye Gere apes de
LEE ae, of an lemect
Fron pel, ord
Enquowe ~ Alp
) Dp vers max! Prune Alp
waite Over How ) of fronts -1 os front > ven
gow pp yt Unde flow
4) $4 fonte- gaol neaye-I e Eslail- Gveul font]
eet fort erent 20 at font = foot!
We oy Teavs seart) ¥ att
END LP
sD set
A) EXIT
Fo aout [reavd= nun pin code:
VAray Lmplementadion
atin clack
f difim, MAX 10
int queue [MACT;
ut fant eo), Pere 1?
void dnqueue (void?
ints dequeue. (void?
int ke ¢ void)?
yorel din play Cveidd;
int main O
ie ‘
tab ophon, Yo;
ae
E pant f (|ndn 44a a Hate Menu Aaa
pont (\nt Eng \n a Degree Ing. Ree Yn Deploy
Hea \e Bet",
prot t ("\n Erb you ephon: "7
sent 07d", & ophor
Switch Cophor)
Ce I
oy
feenk
a:
val = dequeue (2)
ip Gel} = -1D ;
ping (9 pucniferdileted, ta sha val
Bscak j
3
© Nols pare;
1f (vel B 1)
poost CUThe por value th queue o rud", yal
break;
(an
Cou Cane
ahr plog 01,
break;
fi
j while C ephon! in
yehun 9;
Ad ewqpeue
int nem;
pint fla Ents the number eb
sunt ("fa * & num;
if (row == Max-D
pent? l'\n Over flow "7
whe if (front see) O& tear==-D
*foab = reow= »;
ehe
tao +4;
queue [rea] = pum;
J
int dog uene (7
i int val;
if Cfroot > = ~1 I) Bunt >veoud
Ait} CVn Under flow
rehun 17
she
: ved = qe L foot 1s
freot tty
if ( front > reas)
front = rear = ie
4
Away
re ved |
fees int peev
a.
if (front fe-f I fons > veav)
ot
ia Buse empty “2,
j
the
4 vetun queue L prod J;
veil cbivplay
Ink 7
Pook EO Wn");
if (fort == -1 ) front >rean)
bce In Cleue empl “27
(veponts fj < avers ry
poor POV 4d, quence Li)
3 5
Liwkep Luy [npLe Men TATION Or Gveve Apt:
=e ee
Fert mead Ce of Queue.
fee Troubon of 5 44 the [ut clement of Wer
eee ee
lee Pelehen of J on te fur wlemert of cee. the Atcrage requtvemen} $ @
queue with in plemenh bnesel Repreumagon ef 4
A OOD. » OC) od topical f pe
get Se ae er
Ena linked queue, Long cleme hm hoo porb- one
flor stores The dette and another that apres Ha add-e-
Fhe next elomenb a
ATi. LUT pointe xf tox linced )iat in wed! aa FRONT.
4 Hea,we will alro me the another poste 2 ltof REAL
phic will tre Fhe addres of ths love element ia Hae
eee
A All inserBors will be dene at the yout ed ay
all “Be debeborw will be ene ahlliyfe. pote ead
pases
pind PRON T= Rede “NPIL 7 hen iy indicates Hat
the pour b empty.
Trsect CEnynete) Ale
D Allocate memory fo
co pre:
a) Sab prey bata ved
Eg) Lp FRONT > NOLU
see FRONT = BEAR = PTR
FRONTINEXT = beAR 7 NEXT =NuLL
fhe neo node and nawe
Set
elec
Sea REAR 2N EXT 2 FTR
Sb REAR=PTR
Sut REAR=PNEX Tepe
[ena #)
4) ENE Dulshon (Deynan) Ab?
D T Feont =N ble
yn de” Ordeaflow
[Exe 1D
poet pres FRONT
g) Set FRONT epRON TZ NERT
4) Free
5) ENP
Ban Geode:
Ainclede. estdio h7
include < conio- hy
3
pul quer 49)
veld cole ue cohut queue 4;
hut Yor inact Cpt greet cy IVF
ck eee Flee element Catt quene dD?
shut Yur cay et
int pect cs but qed
jt mar?
chery deo
Ge)
d port ("in stay & Mel Menu Ree ND
pont g In te Snsert Vn 2 pele \n2- on tng, Darky
i \p BeBe “% »
sat EC |n Ente gor oper! ap
gant ("fds bephor
sit ch ( opbo)
ae
Cowe
vintt Cn Enis tho no. 7° ingert jig Gneue? 7
seang (" yd") " bval®
45 insert (9, yala
break;
Da ale eamett OP?
break
toe 3:
youl = peck G?
(val = =-)
2 pont $C ln The value of front
queue Sd 7 bor
prox ;
nr A?
qedoplyep)
break;
j
jokl coppon! =5?
Av;
yehune; vi Jd 7
i Crea be — queue Chuctt queue 4g)
Yemen =Nvu;
ce foots Nol;
a gneve % insert (shee quene 47, fi
i
int va
Shuck node +#Ptt
sptr = Cabot pode) malloc (sizest Cshuct nece 5
pr > dota — val?
if (g~7 font = =NULLD
a
12 foot = pj
Y-7 rar = pr;
4-7 pont pret = ya" —znext = NULL;
abe
Qe —rnext 2 pre’
Zarear aft
qareay ay noct =NULL;
4 digs v
Fart quean edoplag (obaet gee P
hace node. & pT
a a7 fronts
coNoU
CP aMARC mn Guess» aempy Ds aa
poort C"\n Dy @
while ( pit! = 4 -7raw
Zeeaeeee see
pinep Crd Wb") prrdoto
five phy nexts
_ pootf Lo rdlt; phr-vdatad;
yetan 4;
4
uch opus aedolets clamor Cohuet queue *)
iz
Bij ctstineda te
pre do pont
if p> fot = = NOL)
party in Onde flaw 72
a
gz font = 47 foot next;
pant C" In The value being didn 7a),
phrr-vdetey
fore p07
etn Fi
Jie poor (shoe gene AD
a Zl Pr font = > NOLL
2 pant f On Aes » empry 2?
gefun -|/
a
j rhe yetun fom ~ydata; :
Types of Clusnes;
). Circular Queue
2) Pegue CPoobile Ends usu)
3). Frionhy Bove
A)» Math phe Gusute-
Circular Cuens
be clone only at
Tn Inxor
Tafel tafe SEPT ES)
Hue FRENT = op , AR =F
Ine ea cpaoazes matt annttene aeeleme I a
the ye completely fel
value tan be inetd.
pot be possible - Je awe
Thu 7 empty espa whee the
Pts Rick ere net ese tae
Comidu a Jaret
delebono ave made The pe will flen be given a
gineen below! *
RIpEREAOS
Les:
Aucue flu poe syteenive
Hue FeenT=0 | EAR =F.
Suppre vit wort fo jane a new elemenk in the.
ees» Bren tbnagh thus Spae vipile ble, the ou flow condition
abil ei became the condiban REAR = MAX ~] 41 holol tme
This hw wager drawkatr % a linea queue. Jo made thir phm, we have @ tolubom: .
) Sift he clemnh fe the Lf ae Hat Tha vatcwst Spaces
tan be veeapyed —ared ubilized MAx-I
a The cireulan qe id implanted in the
as a lin pune implemented,
be only dipfeore ee en Yhad petffoma
inawbon and delesen opus bom
Spy for inanfon, we hue fo check ha @ condidsom:
) oy FRONT=O and REAR= max ter We civ lor
queue » fall.
teh] ] uv fasfel [99 [re] Fall Qu.
comet eee) gp & RENAN,
ineremenkid and
Aame Monner
uy) te pear! = MAXI, phan REAR will be
ya vale will be inguted ao
eae pepe ear
fet ! oan) Ge 6 7 Sine 1
enent , UN
cho rex go thak i+ prich p renee sat
here JIp FRNTI=9 and REAR = MAR), hon it mane thot Pa
Queue hy net fall. So tet RAR =p and ingeut Te new
cnunt thet ar th fig below.
[efele [el [a1 [RPA
g "ppmre® 3 Gane ston ces 1274 e oT
Su REAR 29 and ingut the valu hur.
Abaithm:
9 I} Frowtee aad REAR =MAXH!
we bh “Ove few”
rr skp
END op
4) Tf FRenT =-f and REAR=-/
Su FRONT =RAR=0
Ela Of REAR MAKI and Feet] 20
det kedec0
Fue
get REAR = RRARH
EN DIF
3) ep QUBUET REAR] = VAL
A) fair
Delebra:
To dulete m ebment fiom civeulan gneve , We eee
) gleok at i) below Df FroNT 2-1, fhoa flue are ro
& tee quene. Se, an trderflow condision will
elemen
he vepea tea,
|
a | ae SE oS
eer ha gt and FRoNT= REA,
oo. 4 the rene hb pot emphy
pas lleBing, He element at the front The que Recoraze en
acs yg and g. Front and Keak @®
ee
Ces es ee setae ae 9 = FRONT = REAR
a
pale Hon element ard sep REAR o FRONT =~),
». rf the not 2 PY - and FRoNT=MAX-1,
Fan ap. liebrg the rlemans ot Ke font Feowr b
get foo.
jw | 63 9 je] at) Je]
5 a 8 FRWTE?
6
wv
sedate fn eerste and
Amtibo! Penta
’ tt FRONT =7 "
pisbe ‘Dade flow
gots ohh
Eup of
DP eraaee Queoe (Fron)
» Ty Front = KFA
Ak -)
ga Front OFF
aie a} FRONT 2MAxY
lye
Ble oy PROT > Feit?
eno %
pT Pym bode. !
include @
findude < conio. 7
afedifine MAX Jo
int ques [max] 3
AS ent a ree 7
eae ined Col 2
sae alefe lament ( void),
in £ Cvoj al) ;
void olnphats >
va mau
int opBen, wes
cheacr ly
de
i poort CW atk + Mae Menu gaa4
poontf (In Inout \ne Pele \nt Poor \nu De play
Jaw Bat"?
peat f ("In Ents gow option "77
apie ae aaa
saitch Cophon
: ime +
jae 305
break?»
Cor Ry. delete element 7)
if tvale=D
pone fl» The eles duet i rd)
Paes val);
ime 3!
vals peekl?/
ik (valse-D
poo fC In The free value » 4 valds
break; Ge 4
da ploy 0;
bik 5
feobide( open! =s);
yehun 6;
oid ince? OD
jpt num)
pong ("Wn Frtec the pura ber
eSeanf 0" yd & nun);
if (fort == 0 BE dear= = max-l)
pont Cn pve flow "2;
ebe if-l front ce] kde YATE =—}
Jo be inaukd In The youes
fs
nthe reareo;
queue [rena] = aun;
the if (rere mare! OF from! =o)
i pear=0)
aye L eas] =NUun,
J
whe
I yuard+t,
quem Lyre] enum;
ios veld delet — clement 0
is val;
‘f Cont eon) 4 Yarac-y
: paotfln Under pow"):
ee I?
wel = queue [ font;
ee:
phe
Lif Cont == max~)
font 20;
che
froot +t)
5
rehun yal;
jt peko
1 ph fentoa-1 Be Taree 5)
‘ prof "ls Queue b emyphy 2;
etn =U
dhe pun qn C front ie void doplaye
int 15
pom pC’) a
if C front SES ye weaves~)
paneg ©” [n uae & copy
ebe
if (from
W pede fatal At Ae
Affe inaethon af FF with jononny ay =
oo eT FS TET eT Fg
Ape insiBon af F wh prlerty 2 Cory, no &
Delebon’_ od
Duebon ia ve j 3
fhe Tar will be ee ye ee fet Le 1
procemed first. a Rage
Arayg Im paken af a Prcnity Gheue:
When ormys ore med Yo impdument
then t uy a pron ,
a cape pune fo 80h priority namie oe
& Each of those qwanes will be im plemented win) ;
Civuwlen aera ~ cistulan g
Vameac qese
PEvery indivicud will page h \er8 FRONT
a y
ard REAR pointe ee
a oo- ati na
ao aie ltt
oy Apate.
4
t
2/8 ¢P ie Psodlhy Quene
4 e EF Ma hix
’ GLr Gu
3 and RMREH] contain the fond anol tear
v ap vw x, whe ko the poothe nwn her.
Drwabor:
To inatt = new glomuns with poeonky yada the element
at the rev enol of rw ky ice Gee
w ne a well ae
ony que dboon below:
253) 6 ST
Fry. Posty queue
mahi x @
EF{ insetbon of a ew
ae lem
Delebion:
ae dob an wlement, fiest we find non -em Gye.
and then prow fhe fort serene She frat non-lompy
Yoo cat ansamphin, He for ron eonprrg pent b the
one with prong no 1, A will he claleked anol
proce ed por Toy Code fh
fo need Simp ea
omy lementaben ww cchs fe
Hinludle
Hinlude < Coniohy
Shut nods
Tint datay
‘pp poronty
emack pode anaes
“shut node ps forte NoLLy
Suk node apinaork [shut node A?
Shut node pololebe Leshut node #)
vorol dio play Cot node #3
int — modnl?
i
int ophon j
ebracrey;
: *
: prin $0°\9 pee Met ae a
Ty alte ae ae fra. Aalete \oa- Delay
pont C"\n Exbs your open:
estonf (* dr Gophers
esudich (Ce phond
i
cae Uden = insert (Ata;
praaky
tone Sate delob. ( stat);
bruk;
i dnp) [stant )
lay (stant),
Purl
: aide Copbion | 42°
i
\nbe wi} Shut ain
node vingert (shutt pode 45h
val, pr; at)
Shrub nods ap) +P;
int
Z ie node 4) mallee [sizea (sds ob;
pont Cn Enter the value and ib prion! 2 .
Sonkl' rd rd’, aval, & pr); prerd
pha dota = valy :
pray pronty ap;
if (start = = NOLL Il po stant 9 provi)
pha pext = start)
Stott = po
mele
z
= Shot)
while (pa pot / > pyule LR prrrexd <1psontg Lo fp
Fe pornexts
prez next = ponent:
4 ponent = pre
pehoin jatar >
ght pode 4 dole. (sdudt node psd)
3 sputh node bh
if (sted = = NOLL?
fs
pintt ("\a Und flow 22
4 yerun; ehe
i
pire sont;
pant fl"\n Deleted Item ws Ad prrpdotad;
stant = Shevrt —pnexty
eee
achun Att;
aid dinpleg (amuck rede ame
© wet node 4p?
tee Stotty
if (thant == NbLL)
pf > Brome empty”
we
1 , oD
pone d Con Poorly cea ee
vohile Cpt le NOLL)
: pont (Ne 74 [paonty = HAI’, phrerda ta,
pra proonily %
phe phranexty Deus: ©
A deques tea bt whith She elomenth tan
be inarrfeel ot delebeel at either end. Tt id abve
usw ao head - tail Iineed [rat become the elemenh
wan be addled fo or remo veo fem rite The Pent
Chad) ox Whe bate C#ail) end.
A deque fan the implemen hed ming either & ciruilor
on 8 ciradan cleu He lin 7
LEFT anol
away
F i mae)
ot Tn dosne, tue pointe are maintanes,
Righe , which —peint fo ether a 1 ae
a fen m
The cloner i 4 dayne oct Fo nan]
fo the RIGHT piel ue
4
a fellensd by Dagnune Lol
(TT [|] +
Clan ae Double Endod
Ques Degne)
o Right; @ 3 4 Ss 6 De 9
(® varianh a cle ble — 2nclec! gree
D Tnput reatvictel — dogme:
at one ef the end,
-Inwitom fe. done onl
while delebona can be olone fem both, endo
1) Output rextcted dayne:
~ Dulibor can be clone only at one of the end,
can be cine on oth, ends.
whike jnaetkore Tare code 1 implumant
a mplement i lp andl op rushed cegnaa:
elude <.ttdio. hy
sbinclude < conio.h?
3 max lo
int we [ MAXI;
aes ies,
void s fe tveiedy
yor output void
void inser — Jefpcverdd;
void Insert gps cucid
void ne Jeff he
void right (voids
vee baie void);
ink maint?
i jot aphon
ee is
; we
$l) 1. Input reabsich j
rrp cw 2 a. Oulpe Ute io
pint Cn Ee Chie
soon f le yd” bison
oth C opho
coe
inpote te
eau :
Care
oufpur. degne U
j break ;
@ yeid input dese oe
int ophon;
do
Ln amgl'\n INUT ResrRiCTED DEBE);
eC 1 Int at aight Ed
ntfC ln 2 Doleb fom Att 2
oe fee oe Dolche from per
mt ¢ (Ind Daplag In 8 Quit
ponty ("\n Enler your ophan: 2:
Stoard (Yd “> phen;
switch Co phon)
1
Cee
inaert? Engh!
break;
jue See loft 0;
bowk;
(one Filet sight:
breaks
tet 4 hp levy 0;
brook;
oh ile Copier !=5)4
x
aa output - degare 1?
Hi int phon;
do
Ee ier eee ee Kd
Print Cla I Towrt ob ght. w
nif a 2 Tnwrt at bff)
pont \n 3 Dolute fom Ade)
fini ( “\n # ae Ing. Quid ay
er ("\n foe gow opp on Dy
Stan ("Vt oe &o phon
Switch Cophen)
cue |
inset ALO,
break;
Core 2:
joaert. lefty,
break;
Ce 9"
dolebe — laff 07
break,
dinpleg 0%
break;
amt 4°
habe Copsen! 3);
J
void inoott_ ght O
: at yal
Mets “In Entec The value te be dad: 7
nak yd, & vad;
a =20 bh weight 2 maxed IC Lif == righ)
1 otf 0" ln Diver flo Dy
votun; ®
if Cleft ee) (4 if queue p inibially emphy t/
Aft = right =0 ;
the |
: if (oghb ==max-t) JP mgt th at Aut fel
ight >e
Ch sohb = vighk +13
gt 4
dague [vi ght J- val;
veld inert ff O
ine val > at
pant C'\a Enter the value to be added:
Soong ("td's & vals
a we right - = max~D Il (Lyf == wight 1)
2 ant Cy Overflow ?s
retin ;
‘ pa pe pacer rica emnpg /
+ bff =nghte os
che
A if (Aff == 0
off = MAx~)>
aR Jefe 15
5
lege Cle T= val
j ie deleh_ i
: (eft =
ee In Under flow ;
‘yerwiny
poop l” \n The dolehd slemen’ i: yd 'y Aagpe [ Aeft);
if Clef =) /# Cum fas tolg ane element +/
digt = rgb = 1;
ie
oe unease)
ee oO
; diffe eft +1;
J
yo ra alelte 9 ht
y if (= =-9
Y paar f a Vaolor flow);
ae
sont \n The slemens delta bal” 1 deque L vi ght);
Gicly oe ie Gu har only one element +/
Adt = Baha =
the
i (£00 ght=o)
Coa ub
PS ay - night rb vord din play O
A font> Aft , ears mg ht;
if (feat ==)
i pet Que em ply 2;
poor? C'\ » The element of the git ave 22
if Cfeont 2 = rear)
2 hide (front 2 = reas)
Cpant$l” Yd 4 despa l front
ae +;
5
che
L hide Coat < MAx-))
tpint $C %E™, cyueE fant
fot tn
j
fonts o,
while Chant 2 >veav
€ pnbf- Cs Wid Aegne [front
font I;
j
4 ey
mind Cn?
a f Applicator of Buena:
* Gueves ave widely mel ay weikng hist Pp a Jingle
thaved resource Fie printer , dix, CPU,
ko " wed fp frond data “aay nebren arse Ay Colada
not hearer ile receivel at dame Yate arAent) bh too
presse (50 buffer), eg. Pipes, file £0, socked
aoe " wed a, ba ffer en MPB players and
porte be cD Phyeu, i Pool playbe.
A
wtol in Play bse fe jen to add songs
tb the end, phy fom the a the bos.
kon » med & optrakng serperm A andlin
inte rruph - ek . :
hh When perming a real -dme Ayshem fast tan de
interwphea , fer example , by a meme chee, it
neaary de preter te tntenu ph immediately,
hefere pr ceeding wot The cunent Job. Th the
interne have to fo handled in orden of
arvol, thin a FIFO queue bth apjropnate DS.
# Schealuhng of pre tenes
% dpoolin:
ae of client provwees woibrg fo
Sumi le from fhe sotyer ee wy oe
Rd Vou yone appln Shw ming non-linear i: . er
free or ger requires a quale for roth fit
fravewal,
gece ee. He. Tosep hua Problem; — @
Jn Taplin ph 'n” people cefanol in @ eorele worbag
yo be executed,
The counting shard at fone peint in dhe civele ona
precec ina Speupie divecbon ( clpckwe Jan p~ cle weed
around fhe circle.
4In wth akep , @ Cobain ne of prepa are sipped
and te nxt pevon vb wend,
A The eliminalion af peepee mares Me enrele smaller
and smalles
bAL the last skep, only one petien remo whe br
declawed She winner;
There, if Haw men “number of people carol
am number k’, tohich indicates Hat k-1 people ave Skipped
dhe circle 44 ae Han Sea
& the inlkal civele so that
and kwh penen n
pin 6 f Chore a Fines
the geen pewen pecomes Pha winner,
oo. OQ
Q Aa a
ie oe Be
‘po © Bo 2-2 ae
Fa exoanple , if thee ave £ (nm) reople and Ley
Seeond (ky penon A Ciminateel thon ee the ponen ot
sibon gh eliminated follonad bey [OF pasib'on
fellecee! by pemen at peasikon / sol Pool Ha peven at
posibon 5 uy LMminkd. the poven of aba ‘a yb
The blinnen, Pan, Code
Atinolude <.sfdio-hy
# include malloe Csizeap Cohuee
nodeD;
Mert 1p layetic= 1;
Pro cheat;
folic; pen, IW
z
nuew-node malloc (si2«af.
(thu nok;
phox neh = new node ;
new -necle ~tplye id
