[Powered by Google Translate] [Foleni]
[Chris Gerber, Chuo Kikuu cha Harvard]
Hii ni CS50, CS50.TV]
Moja muhimu data muundo kwa ajili ya kuhifadhi ukusanyaji kuamuru wa mambo ni foleni.
Ni kutumika wakati mambo haja kwa kuondolewa
katika utaratibu huo kama wao walikuwa aliongeza.
Dhana hii inajulikana kama FIFO, ambayo ni kifupi kwa kwanza katika, kwanza nje.
Ili kusaidia taswira hii, inaweza kuwa na manufaa kwa picha
Checkout mstari katika kuhifadhi.
Kama watu kufika, wao kusubiri nyuma ya mstari.
cashier kisha anachukua zamu kuwahudumia wateja mbele,
ambaye kisha exit mstari mmoja kwa wakati.
Katika sayansi ya kompyuta, sisi rejea mbele ya foleni kama kichwa
na nyuma kama mkia.
mfano wa wakati sisi wanaweza kutumia hii katika maombi
ni waitlist kwa uandikishaji darasa.
Kama viti kuwa inapatikana katika darasa,
mtu katika kichwa cha orodha ya kusubiri ni fursa ya kujiandikisha katika darasa.
>> foleni inaweza kuwa yalijengwa kwa kutumia yoyote ukusanyaji
kwamba maduka ya data ili, kama vile safu au orodha zilizounganishwa.
Pamoja na ukusanyaji kuhifadhi vitu katika foleni,
tunahitaji pia njia ya kuongeza vitu mwisho wa foleni,
iitwayo enqueuing,
na mwingine kuondoa bidhaa kutoka kichwa ya foleni,
iitwayo dequeuing.
Ni mara nyingi na manufaa kwa pamoja na mbinu nyingine ya kurudi urefu wa sasa wa foleni
kama vile njia ya kuangalia kama foleni ni tupu.
Hebu tuangalie jinsi sisi tupate kutekeleza na foleni ya integers katika C,
kutumia safu kwa ajili ya ukusanyaji wa vipengele.
Kwanza, sisi kujenga muundo kuitwa foleni kushikilia vigezo wetu.
Tutatumia fasta-size 0 index safu ya integers
kuhifadhi mambo.
Sisi pia ni pamoja na kutofautiana kuitwa kichwa
kwamba maduka index ya kipengele kwamba kwa sasa ni mkuu wa foleni.
variable tatu, iitwayo urefu, zitatumika
kuweka wimbo wa idadi ya vipengele katika safu.
Kama mbadala, unaweza kufikiria kutumia variable kuitwa mkia
kwa uhakika na kipengele mwisho shamba katika safu.
Kabla ya sisi kuandika yoyote zaidi ya kificho,
hebu jaribu nje kubuni yetu.
Hebu kuanza na safu ya tupu urefu 0,
pamoja na kichwa kuweka 0.
Sasa hebu enqueue 4 maadili - 6, 2, 3, na 1.
urefu sasa kuwa 4,
na kichwa kukaa katika 0.
>> Nini kinatokea kama sisi dequeue thamani?
Sisi kupunguza urefu wa 3,
kuweka kichwa kwa 1,
na kurudi thamani 6.
Kificho kwamba ili kuangalia kama hii.
Hapa tuna kazi dequeue,
ambayo inachukua pointer foleni - q - na pointer kipengele,
ambayo ni int aina.
Kwanza sisi kuangalia urefu wa foleni kwa kuhakikisha ni zaidi kuliko 0,
kuhakikisha kuwa kuna kipengele kuwa dequeued.
Kisha sisi kuangalia katika safu vipengele katika kichwa nafasi,
na kuweka thamani ya kipengele kuwa thamani katika nafasi hiyo.
Kisha sisi kubadilisha kichwa kuwa index ijayo
% Uwezo.
Sisi basi kupunguza urefu wa foleni kwa 1.
Hatimaye, sisi kurudi kweli zinaonyesha kwamba dequeue ilikuwa na mafanikio.
Kama sisi dequeue tena, urefu watakuwa 2,
kichwa pia kuwa 2,
na thamani ya kurudi itakuwa 2.
>> Nini kinatokea kama sisi enqueue thamani nyingine kama vile 7?
Kama sisi walikuwa katika mwisho wa foleni,
tutahitaji wrap karibu na kuhifadhi thamani katika kipengele 0 wa safu.
Kihisabati, hii inaweza kuwakilishwa na kuongeza urefu
index ya kichwa
na kutekeleza modulus kutumia uwezo foleni.
Hapa kwamba ni 2 2, ambayo ni 4% 4,
ambayo ni 0.
Kutafsiri wazo hili na Kanuni tuna kazi huu.
Hapa tunaona kazi enqueue,
ambayo inachukua pointer foleni - q -
na inachukua kipengele kuwa enqueued, ambayo ni integer.
Sisi ijayo kuangalia kuhakikisha kwamba uwezo wa foleni
bado ni zaidi ya urefu wa sasa wa foleni.
Next, sisi kuhifadhi kipengele katika safu vipengele
katika index ambayo imedhamiria kwa kichwa + urefu% uwezo wa kupanga foleni.
Sisi basi kuongeza urefu foleni kwa 1,
na kisha kurudi kweli zinaonyesha kwamba kazi enqueue ilikuwa na mafanikio.
>> Mbali na kazi mbili tumekuwa zilizotajwa,
kuna kazi mbili za ziada.
Kwanza ni kazi isempty,
ambayo inachukua pointer foleni
na inathibitisha kwamba urefu ni 0.
pili ni kazi urefu,
ambayo pia inachukua pointer foleni
na anarudi urefu wa sasa kutoka struct.
Hii overview mfupi ameonyesha moja iwezekanavyo utekelezaji wa foleni.
Moja ya mapungufu katika utekelezaji huu
ni kwamba foleni ana fasta upeo wa ukubwa.
Kama sisi kujaribu kuongeza vipengele zaidi ya foleni wanaweza kushikilia,
tunaweza kuhitaji kupuuza ombi na kuacha kipengele,
au sisi wanaweza kupendelea kurudi baadhi ya aina ya makosa.
Kutumia orodha wanaohusishwa badala ya safu
ingekuwa rahisi kufanya ukubwa dynamically foleni.
Hata hivyo, tangu hatuna moja kwa moja kupata mambo ya orodha wanaohusishwa,
kama hatuwezi kuweka wimbo wa mkia,
sisi ingekuwa Scan nzima wanaohusishwa orodha ya kupata mwisho kila wakati.
Tunaweza pia kufikiria kutumia safu ya aina nyingine data,
vile kama structs, ili kujenga foleni ya vipengele ngumu zaidi.
Kufikiri nyuma mfano wetu wa waitlist darasa,
miundo hii inaweza kuwakilisha wanafunzi binafsi.
>> Jina langu ni Chris Gerber, na hii ni CS50.
[CS50.TV]
Na anarudi - >> Moja muda zaidi.
Na kurudi kweli zinaonyesha kwamba - foleni ilikuwa na mafanikio.
-% Uwezo wa foleni -
Ni kwenda kuwa na furaha katika hariri. [Kicheko]