Ne përdorim gjithnjë e më shumë gjuhë programimi të avancuara që na lejojnë të shkruajmë më pak kod dhe të marrim rezultate të shkëlqyera. Ju duhet të paguani për këtë. Ndërsa ne bëjmë gjithnjë e më pak gjëra të nivelit të ulët, bëhet normale që shumë prej nesh nuk e kuptojnë plotësisht se çfarë janë grumbulli dhe grumbulli, si ndodh në të vërtetë përpilimi, cili është ndryshimi midis shtypjes statike dhe dinamike, etj. Nuk po them që të gjithë programuesit nuk i dinë këto koncepte - thjesht mendoj se ndonjëherë ia vlen t'u kthehemi gjërave të tilla të shkollës së vjetër.
Sot do të flasim vetëm për një temë: pirg dhe grumbull. Si pirgu ashtu edhe grumbulli i referohen vendndodhjeve të ndryshme ku ndodh menaxhimi i kujtesës, por strategjia për këtë menaxhim është në mënyrë dramatike e ndryshme.
Rafte
Stack është një zonë e RAM-it që krijohet për çdo thread. Ajo funksionon në rendin LIFO (Last In, First Out), domethënë, pjesa e fundit e memories e shtuar në pirg do të jetë e para në radhë për dalje nga pirg. Sa herë që një funksion deklaron një variabël të ri, ai shtyhet në pirg, dhe kur ajo variabël del jashtë fushëveprimit (për shembull, kur funksioni përfundon), ai del automatikisht nga pirgu. Kur lirohet një variabël i stivës, kjo zonë e memories bëhet e disponueshme për variablat e tjerë të pirgut.
Kjo natyrë e stackit e bën menaxhimin e memories shumë logjike dhe të thjeshtë për t'u ekzekutuar në CPU; kjo çon në shpejtësi të lartë, veçanërisht sepse koha e ciklit për përditësimin e bajtit të stivit është shumë e shkurtër, d.m.th. ky bajt ka shumë të ngjarë të lidhet me cache-in e procesorit. Megjithatë, ka të meta për këtë formë strikte të qeverisjes. Madhësia e stivës është një vlerë fikse dhe tejkalimi i memories së caktuar në pirg do të rezultojë në një tejmbushje të pirgut. Madhësia vendoset kur krijohet transmetimi dhe secila variabël ka një madhësi maksimale në varësi të llojit të të dhënave. Kjo ju lejon të kufizoni madhësinë e disa variablave (për shembull, numrat e plotë) dhe ju detyron të deklaroni paraprakisht madhësinë e llojeve më komplekse të të dhënave (për shembull, vargjeve), pasi pirgu nuk do t'i lejojë ata ta ndryshojnë atë. Përveç kësaj, variablat e vendosura në rafte janë gjithmonë lokale.
Si rezultat, stack ju lejon të menaxhoni kujtesën në mënyrën më efikase - por nëse keni nevojë të përdorni struktura dinamike të të dhënave ose variabla globale, atëherë duhet t'i kushtoni vëmendje grumbullit.
Grumbull
Grumbulli është ruajtja e memories, e vendosur gjithashtu në RAM, që lejon shpërndarjen dinamike të memories dhe nuk funksionon si një pirg: është thjesht një depo për variablat tuaja. Kur ndani një pjesë të memories në grumbull për të ruajtur një variabël, ju mund ta përdorni atë jo vetëm në thread, por në të gjithë aplikacionin. Kështu përcaktohen variablat globale. Kur aplikacioni përfundon, të gjitha zonat e alokuara të memories çlirohen. Madhësia e grumbullit caktohet kur fillon aplikacioni, por, ndryshe nga rafti, është vetëm fizikisht i kufizuar dhe kjo ju lejon të krijoni variabla dinamike.
Ju ndërveproni me grumbullin përmes referencave, të quajtura zakonisht tregues - variabla vlerat e të cilave janë adresa të variablave të tjerë. Duke krijuar një tregues, ju po tregoni një vendndodhje memorie në grumbull, e cila cakton vlerën fillestare për variablin dhe i tregon programit se ku duhet të aksesojë atë vlerë. Për shkak të natyrës dinamike të grumbullit, CPU nuk merr pjesë në kontrollimin e tij; në gjuhët pa një grumbullues mbeturinash (C, C ++), zhvilluesi duhet të lëshojë manualisht pjesët e memories që nuk nevojiten më. Dështimi për ta bërë këtë mund të çojë në rrjedhje të kujtesës dhe fragmentim, gjë që do të ngadalësojë ndjeshëm grumbullin.
Krahasuar me pirgun, grumbulli është më i ngadalshëm sepse variablat janë të shpërndara në memorie në vend që të qëndrojnë në krye të pirgut. Menaxhimi i gabuar i kujtesës në grumbull ngadalëson punën e tij; megjithatë, kjo nuk e zvogëlon rëndësinë e saj - nëse keni nevojë të punoni me ndryshore dinamike ose globale, përdorni grumbullin.
IBM bëri gabimin dramatik duke mos ofruar një implementim të harduerit për stack. Kjo seri përmbante shumë zgjidhje të tjera të pasuksesshme, por, për fat të keq, u kopjua në Bashkimin Sovjetik me emrin ES EVM (Seria e Bashkuar), dhe të gjitha zhvillimet e saj u pezulluan. Kjo e ktheu industrinë sovjetike shumë vite prapa në fushën e zhvillimit të kompjuterave.Radhe
Radha si strukturë e të dhënave është e kuptueshme edhe për njerëzit që nuk janë të njohur me programimin. Radha përmban elementë, sikur të rreshtuar njëri pas tjetrit në një zinxhir. Radha ka një fillim dhe një fund. Mund të shtoni artikuj të rinj vetëm në fund të radhës; artikujt mund t'i merrni vetëm nga fillimi. Ndryshe nga një radhë e zakonshme, të cilën mund ta lini gjithmonë nëse dëshironi, nuk mund të hiqni artikujt nga mesi i radhës së programuesit.
Radha mund të konsiderohet si një tub. Topat mund të shtohen në njërën skaj të tubit - elementët e radhës, nga skaji tjetër ato hiqen. Artikujt në mes të radhës, d.m.th. topat brenda tubit nuk janë të disponueshëm. Fundi i tubit të cilit i shtohen topat korrespondon me fundin e radhës, fundi nga i cili merren në fillim të radhës. Kështu, skajet e tubit nuk janë simetrike, topat brenda tubit lëvizin vetëm në një drejtim.
Në parim, do të ishte e mundur të lejohej që artikujt të shtoheshin në të dy skajet e radhës dhe të mblidheshin gjithashtu nga të dy skajet. Një strukturë e tillë e të dhënave ekziston edhe në programim, emri i saj është "dec", nga anglishtja. Radhë me fund të dyfishtë, d.m.th. radhë me dy skaje. Dhjetor përdoret shumë më rrallë se në radhë.
Përdorimi i radhës në programim është pothuajse i njëjtë me rolin e tij në jetën e përditshme. Radha shoqërohet pothuajse gjithmonë me shërbimin e kërkesave, në rastet kur ato nuk mund të ekzekutohen në çast. Radha gjithashtu ruan rendin në të cilin kryhen kërkesat. Merrni, për shembull, çfarë ndodh kur një person shtyp një buton në një tastierë kompjuteri. Kështu, personi i kërkon kompjuterit të kryejë disa veprime. Për shembull, nëse ai thjesht printon tekst, atëherë veprimi duhet të përbëhet nga shtimi i një karakteri në tekst dhe mund të shoqërohet me rivizatimin e zonës së ekranit, lëvizjen e dritares, riformatimin e një paragrafi, etj.
Çdo sistem operativ, madje edhe më i thjeshtë, është gjithmonë duke kryer shumë detyra në një shkallë ose në një tjetër. Kjo do të thotë që në momentin që shtypet një tast, sistemi operativ mund të jetë i zënë me ndonjë punë tjetër. Sidoqoftë, sistemi operativ nuk ka të drejtë të injorojë goditjen e tastit në asnjë situatë. Prandaj, kompjuteri ndërpritet, kujton gjendjen e tij dhe kalon në përpunimin e goditjes së tastit. Ky përpunim duhet të jetë shumë i shkurtër në mënyrë që të mos prishë detyra të tjera. Komanda e lëshuar duke shtypur një çelës thjesht shtohet në fund të radhës së kërkesës në pritje. Pas kësaj, ndërprerja përfundon, kompjuteri rikthen gjendjen e tij dhe vazhdon punën e ndërprerë duke shtypur tastin. Kërkesa në radhë nuk do të ekzekutohet menjëherë, por vetëm kur t'i vijë radha.
Në Windows, aplikacionet me dritare mbështeten në mesazhet që u dërgohen atyre aplikacioneve. Për shembull, ka mesazhe për shtypjen e butonit të miut, për mbylljen e një dritareje, për nevojën për të rivizatuar zonën e dritares, për zgjedhjen e një artikulli të menysë, etj. Çdo program ka radha e kërkesës... Kur programi merr pjesën e tij të kohës së ekzekutimit, ai zgjedh kërkesën tjetër nga kreu i radhës dhe e ekzekuton atë. Kështu, puna e një aplikacioni me dritare konsiston, në terma të thjeshtë, në ekzekutimin sekuencial të kërkesave nga radha e tij. Radha mbahet nga sistemi operativ.
Një qasje ndaj programimit, e cila nuk konsiston në një thirrje të drejtpërdrejtë të procedurave, por në dërgimin e mesazheve që futen në radha e kërkesës, ka shumë përparësi dhe është një nga veçoritë e programimit të orientuar drejt objekteve. Kështu, për shembull, nëse një program dritare duhet të përfundojë për ndonjë arsye, është më mirë të mos telefononi menjëherë komandën e daljes, e cila është e rrezikshme sepse shkel logjikën e punës dhe mund të çojë në humbje të të dhënave. Në vend të kësaj, programi i dërgon vetes një mesazh mbylljeje, i cili do t'i dërgohet radha e kërkesës dhe ekzekutohet pas kërkesave të mëparshme.
Zbatimi i radhës së vargjeve
Siç u përmend tashmë, grupi i jepet programuesit nga lart, të gjitha strukturat e tjera të të dhënave duhet të zbatohen në bazë të tij. Sigurisht, një zbatim i tillë mund të jetë me shumë faza, dhe grupi nuk vepron gjithmonë si një bazë e menjëhershme e zbatimit. Në rastin e një radhe, dy implementimet më të njohura janë zbatimi i vazhdueshëm i bazuar në grup, i quajtur gjithashtu zbatimi rrethor i buferit, dhe zbatimi i referencës, ose një zbatim të bazuar në listë. Zbatimet e referencës do të diskutohet më poshtë.
Me zbatimin e vazhdueshëm të një radhe, një grup me gjatësi fikse N vepron si bazë, kështu që radha është e kufizuar dhe nuk mund të përmbajë më shumë se N elementë. Indekset e elementeve të grupit variojnë nga 0 në N - 1. Përveç një grupi, zbatimi i radhës ruan tre variabla të thjeshtë: indeksin e fillimit të radhës, indeksin e fundit të radhës dhe numrin e elementeve në radhë. Elementet e radhës përmbahen në segmentin e grupit nga indeksi i fillimit deri në indeksin e fundit.
Kur shtohet një element i ri në fund të radhës, indeksi i fundit së pari rritet me një, pastaj elementi i ri shkruhet në qelizën e grupit me këtë indeks. Në mënyrë të ngjashme, kur merret një element nga kreu i radhës, përmbajtja e qelizës së grupit me indeksin e kokës së radhës ruhet si rezultat i operacionit, atëherë indeksi i kokës së radhës rritet me një . Si indeksi i fillimit ashtu edhe ai i fundit lëvizin nga e majta në të djathtë gjatë funksionimit. Çfarë ndodh kur indeksi i fundit i linjës arrin në fund të grupit, d.m.th. N - 1?
Ideja kryesore pas zbatimit të një radhe është që grupi të jetë i lidhur mendërisht në një unazë. Konsiderohet se elementi i fundit i grupit pasohet nga elementi i parë i tij (kujtojmë se elementi i fundit ka indeksin N - 1, dhe i pari ka indeksin 0). Gjatë zhvendosjes së indeksit të fundit të radhës djathtas, në rastin kur ai tregon elementin e fundit të grupit, ai shkon në elementin e parë. Kështu, një segment i vazhdueshëm i grupit i zënë nga elementët e radhës mund të kalojë nga fundi i grupit deri në fillimin e tij.
Rafte
Stack-i është struktura më e popullarizuar dhe ndoshta më e rëndësishme e të dhënave në programim. Një pirg është një pajisje ruajtëse nga e cila artikujt shfaqen në rendin e kundërt të shtimit të tyre. Është si një radhë e gabuar, në të cilën i pari që shërben është ai që ka hyrë i fundit. Në literaturën e programimit, shkurtesat që tregojnë disiplinën e radhës dhe stek janë përgjithësisht të pranuara. Disiplina e radhës është caktuar FIFO, që do të thotë i pari në të parën jashtë. Disiplina e stivës tregohet nga LIFO, e fundit në daljen e parë.
Një pirg mund të mendohet si një tub vertikal me një fund të ngarkuar me susta. Fundi i sipërm i tubit është i hapur, mund të shtoni, ose, siç thonë ata, të shtyni elementë në të. Termat e zakonshëm në anglisht në këtë drejtim janë shumë të gjallë, operacioni i shtimit të një elementi në pirg shënohet shtytje, që do të thotë "shty, shtyj". Artikulli i sapo shtuar i shtyn artikujt e shtyrë në pirg më parë një pozicion poshtë. Kur elementet dalin nga pirgja, ato duken sikur shtyhen lart, në anglisht pop ("shoot").
Një shembull i një pirg është një pirg bari, një pirg letrash në një tavolinë, një pirg me pjata dhe të ngjashme. Nga këtu vjen emri i stakut, që në anglisht do të thotë stack. Pllakat hiqen nga pirgja në rendin e kundërt të shtimit. Ekziston vetëm pllaka e sipërme, d.m.th. pjatë në krye të pirgut... Një shembull i mirë do të ishte gjithashtu një qorrsokak hekurudhor, në të cilin mund të montohen vagonët.
Përdorimi i stakut në programim
Rafti përdoret mjaft shpesh, dhe në një sërë situatash. Qëllimi i mëposhtëm i bashkon ata: ju duhet të ruani disa punë që nuk janë përfunduar ende deri në fund, nëse duhet të kaloni në një detyrë tjetër. Stacki përdoret për të ruajtur përkohësisht gjendjen e një pune të papërfunduar deri në fund. Pas ruajtjes së gjendjes, kompjuteri kalon në një detyrë tjetër. Në fund të ekzekutimit të tij, gjendja e punës në pritje rikthehet nga grumbulli dhe kompjuteri rifillon punën e ndërprerë.
Pse përdoret pirgu për të ruajtur gjendjen e punës së ndërprerë? Supozoni se kompjuteri po kryen detyrën A. Në procesin e ekzekutimit të tij, bëhet e nevojshme të kryhet detyra B. Gjendja e detyrës A mbahet mend dhe kompjuteri vazhdon të kryejë detyrën B. Por në fund të fundit, kur kryeni detyrën B, kompjuteri mund të kalojë në një detyrë tjetër C dhe do të jetë e nevojshme të ruani gjendjen e detyrës B përpara se të kaloni në C. Më vonë, në fund të C, së pari do të rikthehet gjendja e detyrës B, më pas, në fund të B, gjendja e detyrës A do të rikthehet. Kështu, rikuperimi ndodh në rendin e kundërt të kursimit, i cili është në përputhje me disiplinën e pirgut.
Stack ju lejon të organizoni rekursion, d.m.th. thirrja e nënprogramit në vetvete, qoftë drejtpërdrejt ose nëpërmjet një zinxhiri thirrjesh të tjera. Për shembull, supozoni se nënprogrami A ekzekuton një algoritëm që varet nga parametri hyrës X dhe, ndoshta, nga gjendja e të dhënave globale. Për vlerat më të thjeshta të X, algoritmi zbatohet drejtpërdrejt. Për vlera më komplekse X, algoritmi zbatohet si reduktim i aplikimit të të njëjtit algoritëm për vlerat më të thjeshta X. Në këtë rast, nënprogrami A i referohet vetvetes, duke kaluar një vlerë më të thjeshtë X si parametër. Në një thirrje të tillë, vlera e mëparshme e parametrit X, si dhe të gjitha variablat lokale të nënprogramit A, ruhen në pirg. Më pas, krijohet një grup i ri variablash lokale dhe një variabël që përmban një vlerë të re (më të thjeshtë) të parametrit X. Nënprogrami i thirrur A vepron në një grup të ri variablash pa e shkatërruar grupin e mëparshëm. Në fund të thirrjes, grupi i vjetër i ndryshoreve lokale dhe gjendja e vjetër e parametrit të hyrjes X rikthehen nga pirgu dhe nënprogrami vazhdon nga pika ku u ndërpre.
Në fakt, as nuk duhet të ruani vlerat e variablave lokale të nënrutinës në pirg në një mënyrë të veçantë. Fakti është se variablat lokale të një nënprogrami (d.m.th., e brendshme e saj, variablat e punës, të cilat krijohen në fillim të ekzekutimit të tij dhe shkatërrohen në fund) vendosen në një stack të implementuar në harduer të bazuar në memorien e zakonshme të aksesit të rastësishëm. Në fillim të punës së saj, nënprogrami rrëmben një vend në pirg për variablat e tij lokalë, kjo pjesë e memories në pirgun e harduerit zakonisht quhet bllok lokal të ndryshueshëm ose në anglisht kornizë("kornizë"). Në fund të punës së saj, nënprogrami çliron memorien duke hequr një bllok të ndryshoreve të saj lokale nga pirgja.
Përveç variablave lokale, rafti i harduerit ruan adresat e kthimit për thirrjet nënrutinë. Le të thirret një nënprogram në një moment në programin A B... Përpara se të thirret nënprogrami B, adresa e instruksionit që ndjek udhëzimin që thërret B ruhet në rafte. Ky është i ashtuquajturi adresa e kthimit në programin A. Në fund të punës së saj, nënprogrami B nxjerr adresën e kthimit në programin A nga steka dhe kthen kontrollin në këtë adresë. Kështu, kompjuteri vazhdon të ekzekutojë programin A nga instruksioni pas instruksionit thirrës. Shumica e përpunuesve kanë udhëzime speciale që mbështesin thirrjen e një nënprogrami duke e shtyrë fillimisht adresën e kthimit në stek dhe duke u kthyer nga nënprogrami në adresën e shfaqur nga pirgu. Zakonisht komanda e thirrjes quhet thirrje, komanda e kthimit quhet kthim.
Parametrat e një nënprogrami ose funksioni gjithashtu shtyhen në pirg përpara se ta thërrasin atë. Rendi në të cilin ato shtyhen në pirg varet nga konventat e gjuhëve të nivelit të lartë. Pra, në C ose C ++, argumenti i parë i një funksioni është në krye të pirgut, i dyti është poshtë tij, e kështu me radhë. Në Pascal, e kundërta është e vërtetë, në krye të pirgut është argumenti i fundit i funksionit. (Prandaj, meqë ra fjala, funksionet me një numër të ndryshueshëm argumentesh, si printf, janë të mundshme në C, por jo në Pascal.)
Në Fortran-4, një nga gjuhët më të vjetra dhe më të suksesshme të programimit, argumentet kalohen përmes një zone të veçantë memorie, e cila mund të mos jetë e vendosur në pirg, pasi kompjuterë si kompjuterët IBM 360 ose ES pa implementim të harduerit ende ekzistonin. deri në fund të viteve 70 të shekullit XX. rafte. Adresat e kthimit gjithashtu u ruajtën jo në rafte, por në vendndodhje të memories të fiksuara për secilën nënprogram. Programuesit e quajnë memorie të tillë statike në kuptimin që variablat statike zënë gjithmonë të njëjtin vend në memorie në çdo kohë që programi është duke u ekzekutuar. Kur përdorni vetëm memorie statike, rekursioni nuk është i mundur, pasi kur bëhet një thirrje e re, vlerat e mëparshme të ndryshoreve lokale shkatërrohen. Në referencën Fortran-4, u përdorën vetëm variabla statike dhe rekursioni ishte i ndaluar. Deri më tani, gjuha Fortran përdoret gjerësisht në llogaritjet shkencore dhe inxhinierike, megjithatë, standardi modern Fortran-90 tashmë prezanton memorien e grumbullit, duke eliminuar të metat e versioneve të mëparshme të gjuhës.
Implementimi i stivit të bazuar në grup
Zbatimi i stivit të bazuar në grup është një klasik programimi. Ndonjëherë edhe vetë koncepti i një pirg nuk identifikohet mjaft saktë me këtë zbatim.
Baza e zbatimit është një grup me madhësi N, kështu që zbatohet një pirg me madhësi të kufizuar, thellësia maksimale e së cilës nuk mund të kalojë N. Indekset e qelizave të grupit variojnë nga 0 në N - 1. Elementet e stivit ruhen në një grup si më poshtë: elementi në fund të pirgut ndodhet në fillim të grupit, d.m.th. në indeksin 0, artikulli mbi elementin më të poshtëm të pirgut ruhet në indeksin 1, e kështu me radhë. Pjesa e sipërme e pirgut ruhet diku në mes të grupit. Indeksi i artikullit në krye të pirgut ruhet në një variabël të veçantë të quajtur zakonisht treguesi N - 1. Elementet e stivës zënë një segment të njëpasnjëshëm të grupit, duke filluar me qelizën, indeksi i së cilës ruhet në treguesin e stivit dhe duke përfunduar me qelizën e fundit në grup. Në këtë variant, pirgja rritet në drejtim të uljes së indekseve. Nëse steka është bosh, atëherë treguesi i stivës përmban vlerën N (e cila është një më shumë se indeksi i qelizës së fundit në grup).
Përshëndetje, unë jam student i vitit të dytë në një universitet teknik. Pasi kalova disa palë programe për arsye shëndetësore, hasa në një keqkuptim të temave si "Stack" dhe "Queue". Nëpërmjet provave dhe gabimeve, pas disa ditësh, më në fund më kuptoi se çfarë ishte dhe me çfarë hahej. Në mënyrë që të kuptuarit tuaj të mos marrë aq shumë kohë, në këtë artikull do t'ju tregoj se çfarë është "Stack", si dhe me çfarë shembujsh kuptova se çfarë është. Nëse ju pëlqen, do të shkruaj pjesën e dytë, e cila do të prekë një koncept të tillë si "Radha"
Teoria
Në Wikipedia, përkufizimi i një pirg është:
Stack (anglisht stack - një pirg; rafte lexohet) është një lloj abstrakt i të dhënave që është një listë e elementeve të organizuar sipas parimit LIFO (anglisht fundit në - first out, "last in - first out").
Ky është një përkufizim mjaft i plotë, por mund të jetë pak i vështirë për fillestarët për t'u kuptuar.
Prandaj, gjëja e parë në të cilën do të doja të fokusohesha është prezantimi i pirgut në formën e gjërave nga jeta. Gjëja e parë që më erdhi në mendje ishte interpretimi në formën e një pirg librash, ku libri më i lartë është maja.
Në fakt, një pirg mund të përfaqësohet si një pirg i çdo objekti, qofshin një pirg fletësh, fletore, këmisha e të ngjashme, por shembulli me libra, mendoj se do të jetë më optimali.
Pra, nga çfarë përbëhet pirgu?
Stacki përbëhet nga qeliza (në shembull, këto janë libra), të cilat paraqiten në formën e një strukture që përmban disa të dhëna dhe një tregues për llojin e kësaj strukture në elementin tjetër.
E vështirë? Nuk ka rëndësi, le ta kuptojmë.
Kjo foto tregon një pirg skematik. Blloku "Të dhënat / * tjetër" është qeliza jonë. * next, siç mund ta shohim, tregon për elementin tjetër, me fjalë të tjera, treguesi * Next ruan adresën e qelizës tjetër. Treguesi * TOP tregon në krye të pirgut, domethënë ruan adresën e tij.
Me përfundimin e teorisë, le të kalojmë në praktikë.
Praktikoni
Së pari, ne duhet të krijojmë një strukturë që do të jetë "qeliza" jonë
Kodi C ++
struct comp (// Një strukturë e quajtur comp (nga fjala komponent) int Data; // Disa të dhëna (mund të jenë çdo, për shembull, mund të shkruani çelësin int; char Data; mund të shtoni edhe disa të dhëna të tjera) comp * tjetër ; // Një tregues i tipit comp në elementin tjetër);
Për fillestarët, mund të mos jetë e qartë pse treguesi ynë është i llojit comp, ose më mirë, treguesi i llojit të strukturës comp. Më lejoni të shpjegoj se në mënyrë që treguesi i ardhshëm * të ruajë strukturën comp, duhet të tregojë llojin e kësaj strukture. Me fjalë të tjera, specifikoni se çfarë do të ruajë treguesi.
Pasi të kemi vendosur "Qelizën", le të kalojmë në krijimin e funksioneve.
Funksione
Funksioni i krijimit të një "Stack" / shtimi i një artikulli në "Stack"
Kur shtojmë një element, do të kemi dy situata:
- Rafti është bosh dhe duhet të krijohet
- Stacki tashmë ekziston dhe ju vetëm duhet të shtoni një element të ri në të
Kodi C ++
void s_push (comp ** top, int D) (// funksioni i tipit void (nuk kthen asgjë) i cili merr një tregues në krye të stivit dhe një variabël që do të shkruhet në qelizën comp * q; // Krijo një treguesi i ri q i llojit të strukturës comp. në fakt, ky është elementi ynë i ri q = new comp (); // caktoni memorie për elementin e ri q-> Data = D; // Shkruani numrin e kërkuar në elementin Data nëse (lart == NULL) (// Nëse nuk ka kulm, domethënë, pirgu është bosh * krye = q; // maja e pirgut do të jetë një element i ri) tjetër // nëse pirgu nuk është bosh ( q-> tjetër = * lart; // Ne lidhim nga elementi i ri në krye. Kjo do të thotë, e vendosim librin në krye të stivit. * krye = q; // Tregojmë që pjesa e sipërme tani është një e re element))
Le të marrim pak më shumë detaje.
Së pari, pse funksioni merr ** krye, domethënë një tregues në një tregues, për hir të qartësisë, do ta lë këtë pyetje për më vonë. Së dyti, le të flasim më në detaje rreth q-> tjetër = * krye dhe çfarë do të thotë ->
.
-> do të thotë që, përafërsisht, ne hyjmë në strukturën tonë dhe marrim një element të kësaj strukture prej andej. Ne rresht q-> tjetër = * krye ne marrim nga qeliza jonë një tregues për elementin tjetër * tjetër dhe e zëvendësojmë atë me një tregues që tregon në krye të stivit * të sipërm. Me fjalë të tjera, ne jemi duke komunikuar, nga elementi i ri në krye të stivit. Asgjë e komplikuar këtu, ashtu si me librat. Librin e ri e vendosim pikërisht në krye të pirgut, pra bëjmë një lidhje nga libri i ri në krye të pirgut të librave. Pas kësaj, libri i ri bëhet automatikisht në krye, meqenëse pirg nuk është një pirg librash, duhet të tregojmë se elementi i ri është një majë, për këtë shkruajmë: * krye = q;.
Funksioni i heqjes së një elementi nga "Stack" sipas të dhënave
Ky funksion do të heqë një element nga pirgu nëse numri i të dhënave të qelizës (q-> Data) është i barabartë me numrin që ne vetë do të caktojmë.
Mund të ketë opsione të tilla:
- Qeliza që duhet të fshijmë është pjesa e sipërme e pirgut
- Qeliza që duhet të fshijmë është në fund, ose midis dy qelizave
Kodi C ++
void s_delete_key (comp ** top, int N) (// funksioni që merr krye dhe numrin që do të fshihet comp * q = * top; // krijoni një tregues të tipit comp dhe barazoni (vendosni) në krye të stack comp * prev = NULL; // krijoni një tregues në elementin e mëparshëm, që nga fillimi do të jetë bosh ndërsa (q! = NULL) (// për sa kohë që treguesi q nuk është bosh, ne do ta ekzekutojmë kodin në një lak, nëse ende përfundon në një cikli bosh nëse (q-> Të dhënat == N) (// nëse të dhënat e elementit janë të barabarta me numrin që duhet të fshijmë nëse (q == * lart) (/ / nëse një tregues i tillë është i barabartë me pjesën e sipërme, domethënë, elementi që duhet të fshijmë është pjesa e sipërme * krye = q- > tjetër; // zhvendoseni majën në elementin tjetër të lirë (q); // pastroni qeliza q-> Të dhënat = NULL; // Më pas, për të shmangur gabimet, ne zero variablat në qelizën e fshirë, pasi në disa përpilues qeliza e fshirë ka vlera të ndryshoreve jo NULL, por fjalë për fjalë "Leximi i kujtesës është i pamundur" ose numra " -2738568384" ose të tjera, në varësi të përpiluesit. q-> tjetër = NULL;) tjetër // nëse elementi n i fundit ose midis dy elementeve të tjerë (prev-> next = q-> next; // Lidhja nga elementi i mëparshëm me elementin tjetër të lirë (q); // pastroni qelizën q-> Të dhënat = NULL; // zero variablat q -> tjetër = NULL; )) // nëse të dhënat e elementit NUK janë të barabartë me numrin që duhet të heqim prev = q; // mbani mend qelizën aktuale si të mëparshmen q = q-> tjetër; // zhvendosni treguesin q në elementin tjetër))
Në këtë rast, treguesi q luan të njëjtin rol si treguesi në fletore, kalon mbi të gjithë pirgun derisa të bëhet NULL ( ndërsa (q! = NULL)), me fjalë të tjera, derisa të përfundojë pirgu.
Për një kuptim më të mirë të fshirjes së një elementi, le të bëjmë një analogji me pirgun tashmë të njohur të librave. Nëse duhet ta heqim librin nga lart, e heqim atë dhe libri poshtë tij bëhet krye. Këtu është e njëjta gjë, vetëm në fillim duhet të përcaktojmë që elementi tjetër do të bëhet maja. * krye = q-> tjetër; dhe vetëm atëherë hiqni elementin pa pagesë (q);
Nëse libri që do të hiqet është midis dy librave ose midis një libri dhe një tavoline, libri i mëparshëm do të shtrihet në tjetrin ose në tryezë. Siç e kemi kuptuar tashmë, libri ynë është një qelizë, dhe tabela është NULL, domethënë nuk ka asnjë element tjetër. Rezulton në të njëjtën mënyrë si me librat, ne tregojmë se qeliza e mëparshme do të lidhet me tjetrën prev-> tjetër = q-> tjetër;, vlen të theksohet se para-> tjetër mund të jetë e barabartë me një qelizë dhe zero, nëse q-> tjetër = NULL, domethënë nuk ka qelizë (libri do të shtrihet në tryezë), pas kësaj e pastrojmë qelizën falas (q).
Vlen gjithashtu të theksohet se nëse nuk e bëni këtë lidhje, pjesa e qelizave që shtrihet pas qelizës së fshirë do të bëhet e paarritshme, pasi vetë lidhja që lidh një qelizë me tjetrën do të humbasë dhe ky seksion thjesht do të humbasë në kujtesë.
Funksioni i shfaqjes së të dhënave të stivës
Funksioni më i thjeshtë:
Kodi C ++
void s_print (comp * top) (// merr një tregues në krye të stek comp * q = lartë; // vendos q në krye ndërsa (q) (// ndërsa q nuk është bosh (ndërsa (q) është ekuivalente me while (q! = NULL )) printf_s ("% i", q-> Të dhëna); // shfaqni të dhënat e qelizës së stivit q = q-> më pas; // pasi të kemi shfaqur, zhvendoseni q në elementi tjetër (qeliza)))
Këtu mendoj se gjithçka është e qartë, thjesht dua të them që q duhet të perceptohet si një rrëshqitës, ai kalon nëpër të gjitha qelizat nga lart, ku e instaluam në fillim: * q = krye;, deri në artikullin e fundit.
Funksioni kryesor
Epo, ne kemi shkruar funksionet kryesore për të punuar me pirgun, ne i quajmë ato.
Le të shohim kodin:
Kodi C ++
void main () (comp * top = NULL; // në fillim të programit nuk kemi radhë, pra nuk ka kulm, i japim një vlerë NULL // Pastaj fillojmë të mbledhim numrat nga 1 në 5 në stack tonë s_push (& top, 1); s_push (& top, 2); s_push (& top, 3); s_push (& top, 4); s_push (& top, 5); // pas ekzekutimit të funksioneve në pirg , do të kemi 54321 s_print (lart); // printim s_delete_key (& top, 4); // Më pas fshijmë 4, pirgu merr 5321 printf_s ("\ n"); // transferimi në një rresht të ri s_print (lart ); // sistemi i printimit ("pauzë"); // pauzë)
Le të kthehemi te arsyeja pse i kaluam një tregues në një tregues kulmi në funksion. Fakti është se nëse do të futnim vetëm një tregues në kulm në funksion, atëherë "Stack" do të krijohej dhe ndryshohej vetëm brenda funksionit, në funksionin kryesor kulmi do të ishte gjithashtu NULL. Duke kaluar një tregues në një tregues, ne ndryshojmë pjesën e sipërme * të sipërme në funksionin kryesor. Rezulton se nëse funksioni ndryshon pirgun, ju duhet të transferoni kulmin në të si një tregues në një tregues, siç kishim në funksionin s_push, s_delete_key. Në funksionin s_print, "stack" nuk duhet të ndryshojë, kështu që ne thjesht kalojmë një tregues në krye.
Në vend të shifrave 1,2,3,4,5, mund të përdorni edhe variabla të tipit int.
konkluzioni
Kodi i plotë i programit:
Kodi C ++
#përfshi
Rezultati i ekzekutimit
Meqenëse artikujt shtyhen vazhdimisht në krye të pirgut, artikujt do të shfaqen në rend të kundërt
Si përfundim, do të doja t'ju falënderoja për kohën kushtuar artikullit tim, me të vërtetë shpresoj se ky material ka ndihmuar disa programues fillestarë të kuptojnë se çfarë është "Stack", si ta përdorin atë dhe në të ardhmen ata nuk do të kenë ndonjë problem më. Shkruani në komente mendimin tuaj, si dhe si mund t'i përmirësoj artikujt e mi në të ardhmen. Faleminderit per vemendjen.
Etiketa: Stack, C stack, implementim stack, stack on array, stack në rritje dinamike, rafte në një disk të lidhur vetëm
Rafte
C tech është ndoshta struktura më e thjeshtë e të dhënave që do të mësojmë dhe që do ta përdorim vazhdimisht. Një pirg është një strukturë të dhënash në të cilën elementët mbështesin parimin LIFO ("I fundit në - i pari jashtë"): i fundit brenda, i pari jashtë. Ose i pari që hyri - i fundit që doli.
Stack ju lejon të ruani artikujt dhe zakonisht mbështet dy operacione bazë:
- SHTYTJE- e vendos artikullin në krye të pirgut
- POP- nxjerr një element nga maja e pirgut, duke lëvizur pjesën e sipërme te elementi tjetër
Është gjithashtu e zakonshme që një operacion PEEK të marrë një artikull në krye të pirgut, por jo ta nxjerrë atë nga atje.
Stack-i është një nga strukturat bazë të të dhënave dhe përdoret jo vetëm në programim, por edhe në qark, dhe thjesht në prodhim, për zbatimin e proceseve teknologjike etj.; stack përdoret si një strukturë ndihmëse e të dhënave në shumë algoritme dhe struktura të tjera më komplekse.
Për shembull, le të themi se kemi një grumbull numrash. Le të ekzekutojmë disa komanda. Fillimisht, pirgu është bosh. Pjesa e sipërme e pirgut është një tregues për elementin e parë, nuk tregon askund. Në rastin e c, mund të jetë NULL.
Stafi tani përbëhet nga një element, numri 3. Pjesa e sipërme e pirgut tregon numrin 3.
Rafti përbëhet nga dy elementë, 5 dhe 3, me pjesën e sipërme të pirgut të treguar në 5.
Rafti përbëhet nga tre elementë, pjesa e sipërme e pirgut tregon në 7.
Do të kthejë vlerën 7, 5 dhe 3 do të mbeten në pirg. Kulmi do të tregojë në elementin tjetër - 5.
Do të kthehet 5, do të mbetet vetëm një element në pirg, 3, i cili do të tregohet nga maja e pirgut.
Do të kthehet 3, pirgu do të jetë bosh.
Një pirg shpesh krahasohet me një pirg pllakash. Për të marrë pjatën tjetër, duhet të hiqni ato të mëparshme. Pjesa e sipërme e pirgut është maja e pirgut të pjatave.
Kur punojmë me pirgun, dy gabime kryesore dhe të zakonshme janë të mundshme:
- 1. Stack Underflow: Përpjekja për të nxjerrë një artikull nga një pirg bosh
- 2. Stack Overflow: Përpjekja për të vendosur një artikull të ri në një pirg që nuk mund të rritet më (për shembull, RAM jo e mjaftueshme)
Implementimi i softuerit
Konsideroni tre zbatime të thjeshta të stivës:
Stack me madhësi fikse të ndërtuar mbi një grup
Një tipar dallues është thjeshtësia e zbatimit dhe shpejtësia maksimale e ekzekutimit. Një pirg i tillë mund të përdoret kur madhësia maksimale e tij dihet paraprakisht ose dihet se është e vogël.
Së pari, ne përcaktojmë madhësinë maksimale të grupit dhe llojin e të dhënave që do të ruhen në të:
#define STACK_MAX_SIZE 20 typedef int T;
Tani vetë struktura
Struktura Typedef Stack_tag (T të dhëna; madhësia_t;) Stack_t;
Këtu madhësia e ndryshueshme është numri i elementeve, dhe në të njëjtën kohë treguesi në krye të pirgut. Kulmi do të tregojë në elementin tjetër të grupit, në të cilin do të futet vlera.
Ne vendosim një artikull të ri në pirg.
Pushim i pavlefshëm (Stack_t * stack, konst T vlera) (stack-> të dhëna = vlera; stek-> madhësia ++;)
Problemi i vetëm është se mund të dilni jashtë grupit. Prandaj, duhet të kontrolloni gjithmonë që të mos ketë gabim të tejmbushjes së Stack:
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 void push (Stack_t * stack, const vlera T) (if (stack-> size> = STACK_MAX_SIZE) (dalje (STACK_OVERFLOW);) stack-> data = value; stack-> ++ ;)
Në mënyrë të ngjashme, ne përcaktojmë një operacion Pop që kthen një element nga lart dhe vazhdon në tjetrin
T pop (Stack_t * stack) (nëse (stack-> madhësia == 0) (dalja (STACK_UNDERFLOW);) stack-> size--; kthimi stack-> të dhënat;)
Dhe një funksion shikimi që kthen artikullin aktual nga lart
T peek (konst Stack_t * stack) (if (stack-> size<= 0) { exit(STACK_UNDERFLOW); } return stack->të dhëna; )
Një tjetër shënim i rëndësishëm - ne nuk kemi një funksion për krijimin e një pirg, kështu që ju duhet të rivendosni manualisht vlerën e madhësisë
Funksionet ndihmëse për printimin e artikujve të stivës
Void printStackValue (konst T vlera) (printf ("% d", vlera);) void printStack (const Stack_t * stack, void (* printStackValue) (const T)) (int i; int len = stack-> size - 1 ; printf ("stack% d>", stack-> size); for (i = 0; i< len; i++) { printStackValue(stack->të dhënat [i]); printf ("|"); ) if (stack-> madhësia! = 0) (printStackValue (stack-> të dhënat [i]);) printf ("\ n"); )
Vini re se ne po përdorim int në funksionin e printimit, jo size_t, sepse len mund të bëhet negativ. Funksioni printon së pari madhësinë e pirgut, dhe më pas përmbajtjen e tij, duke i ndarë elementet me |
Ekzaminimi
Stack_t stack; stack.madhësia = 0; shtytje (& rafte, 3); printStack (& stack, printStackValue); shtytje (& rafte, 5); printStack (& stack, printStackValue); shtytje (& rafte, 7); printStack (& stack, printStackValue); printf ("% d \ n", pop (& stack)); printStack (& stack, printStackValue); printf ("% d \ n", pop (& stack)); printStack (& stack, printStackValue); printf ("% d \ n", pop (& stack)); printStack (& stack, printStackValue); _getch ();
Konsideroni gjithashtu situata ku ka gabime në përdorim. Rrjedha e nëndheshme
Kryesor i pavlefshëm () (stack_t stack; stack.size = 0; push (& stack, 3); pop (& stack); pop (& stack); _getch ();)
Kryesor i pavlefshëm () (stack_t stack; size_t i; stack.size = 0; për (i = 0; i< 100; i++) { push(&stack, i); } _getch(); }
Rafte në rritje dinamike në grup
Stack në rritje dinamike përdoret kur numri i elementeve mund të jetë i rëndësishëm dhe nuk dihet në momentin e zgjidhjes së problemit. Madhësia maksimale e stivës mund të kufizohet nga një numër ose nga madhësia e RAM-it.
Stack do të përbëhet nga një tregues për të dhënat, madhësia e grupit (maksimumi) dhe numri i elementeve në grup. Ky numër do të tregojë gjithashtu majën.
Typedef struct Stack_tag (T * të dhëna; madhësia_t; madhësia_t sipër;) Stack_t;
Për të filluar, ju duhet një madhësi fillestare e grupit, le të jetë e barabartë me 10
#define INIT_SIZE 10
Algoritmi i punës është si më poshtë: kontrollojmë nëse vlera e majës e ka tejkaluar vlerën e madhësisë. Nëse vlera tejkalohet, atëherë ne rrisim madhësinë e grupit. Ka disa opsione se si të rritet grupi. Mund të shtoni një numër, mund ta shumëzoni me ndonjë vlerë. Cila nga opsionet është më e mirë varet nga specifikat e detyrës. Në rastin tonë, ne do ta shumëzojmë madhësinë me numrin MULTIPLIER
#define SHUMËZUESI 2
Ne nuk do të vendosim madhësinë maksimale. Programi do të dështojë gjatë tejmbushjes së pirgut ose nën rrjedhjes së pirgut. Ne do të zbatojmë të njëjtën ndërfaqe (pop, push, peek). Për më tepër, meqenëse grupi është dinamik, ne do të bëjmë disa funksione ndihmëse për të krijuar pirgun, për ta hequr dhe pastruar.
Së pari, funksionet për krijimin dhe heqjen e pirgut dhe disa gabime
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 Stack_t * createStack () (Stack_t * jashtë = NULL; jashtë = malloc (madhësia e (Stack_t)); nëse (jashtë =OF_MEMORY) jashtë-> madhësia = INIT_SIZE; jashtë-> të dhënat = malloc (jashtë-> madhësia * madhësia e (T)); nëse (jashtë-> të dhënat == NULL) (falas (jashtë); dalja (OUT_OF_MEMORY);) jashtë- > krye = 0; kthehu jashtë;) void deleteStack (Stack_t ** stack) (falas ((* rafte) -> të dhëna); falas (* rafte); * rafte = NULL;)
Gjithçka është jashtëzakonisht e thjeshtë dhe e drejtpërdrejtë, nuk ka truke të pista. Ne krijojmë një pirg me një gjatësi fillestare dhe zero vlerat.
Tani le të shkruajmë një funksion ndihmës për ndryshimin e madhësisë.
Ndryshimi i madhësisë së pavlefshme (Stack_t * stack) (stack-> madhësia * = MULTIPLIER; stack-> data = realloc (stack-> data, stack-> size * sizeof (T)); if (stack-> data == NULL) ( dalje (STACK_OVERFLOW);))
Këtu, vini re, në rast se memoria e mjaftueshme nuk mund të ndahet, ajo do të dalë me STACK_OVERFLOW.
Funksioni push kontrollon nëse jemi jashtë kufijve të grupit. Nëse po, atëherë rrisni madhësinë e saj.
Pushim i pavlefshëm (Stack_t * stack, vlera T) (nëse (stack-> lartë> = stack-> madhësia) (ndryshoni madhësinë (stack);) stack-> data = value; stack-> top ++;)
Funksionet pop dhe peek janë të ngjashme me ato të përdorura për një grup me madhësi fikse.
T pop (Stack_t * stack) (if (stack-> top == 0) (dil (STACK_UNDERFLOW);) stack-> top--; return stack-> data;) T peek (const Stack_t * stack) (nëse ( rafte-> krye<= 0) { exit(STACK_UNDERFLOW); } return stack->të dhëna; )
Kontrollo
Kryesor i pavlefshëm () (int i; Stack_t * s = createStack (); për (i = 0; i< 300; i++) { push(s, i); } for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); } deleteStack(&s); _getch(); }
Le të shkruajmë një funksion tjetër, implode, që zvogëlon grupin në një madhësi të barabartë me numrin e elementeve në grup. Mund të përdoret kur dihet tashmë se nuk do të futen më elementë dhe kujtesa mund të lirohet pjesërisht.
Shpërthimi i zbrazët (Stack_t * rafte) (stack-> madhësia = stack-> lart; stack-> data = realloc (stack-> të dhëna, stek-> madhësia * sizeof (T));)
Ne mund të përdorim në rastin tonë
Për (i = 0; i< 300; i++) { push(s, i); } implode(s); for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); }
Ky implementim me një fije të vetme të stackit përdor pak akses në memorie, është mjaft i thjeshtë dhe i gjithanshëm, funksionon shpejt dhe mund të zbatohet, nëse është e nevojshme, në pak minuta. Përdoret gjithmonë në vijim, përveç nëse tregohet ndryshe.
Ka një pengesë në lidhje me metodën e rritjes së kujtesës së konsumuar. Kur shumëzohet me 2 (në rastin tonë), kërkohen pak aksese në memorie, por çdo rritje pasuese mund të çojë në një gabim, veçanërisht me një sasi të vogël memorie në sistem. Nëse përdorni një mënyrë më të butë për ndarjen e memories (për shembull, shtoni 10 çdo herë), atëherë numri i thirrjeve do të rritet dhe shpejtësia do të bjerë. Sot, zakonisht nuk ka probleme me madhësinë e kujtesës, dhe menaxherët e kujtesës dhe mbledhësit e mbeturinave (të cilët nuk janë në C) janë të shpejtë, kështu që mbizotëron ndryshimi agresiv (për shembull, për shembull, zbatimi i të gjithë bibliotekës standarde Java).
Zbatimi i një pirg në një listë të lidhur vetëm
Çfarë është një listë e lidhur vetëm,. Shkurtimisht: një listë e lidhur vetëm përbëhet nga nyje, secila prej të cilave përmban informacion të dobishëm dhe një lidhje me nyjen tjetër. Nyja e fundit i referohet NULL.
Nuk do të kemi asnjë madhësi maksimale dhe minimale (edhe pse në rastin e përgjithshëm mund të jetë). Çdo element i ri krijohet përsëri. Së pari, le të përcaktojmë strukturën e nyjës
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 typedef int T; typedef struct Node_tag (vlera T; struct Node_tag * next;) Node_t;
Funksioni për futjen e elementit të parë është i thjeshtë: krijojmë një nyje të re. Ne hedhim treguesin tjetër në nyjen e vjetër. Më pas, treguesi në krye të pirgut transferohet në nyjen e krijuar rishtazi. Pjesa e sipërme e pirgut tani po tregon nyjen e re.
Pushimi i pavlefshëm (Node_t ** koka, vlera T) (Nyja_t * tmp = malloc (madhësia e (Node_t)); nëse (tmp == NULL) (dalja (STACK_OVERFLOW);) tmp-> tjetër = * kokë; tmp-> vlera = vlera; * kokë = tmp;)
Funksioni pop merr elementin e parë (ai i treguar nga lart), e kalon treguesin te elementi tjetër dhe kthen të parin. Këtu ka dy opsione - mund të ktheni një nyje ose një vlerë. Nëse e kthejmë vlerën, atëherë do të duhet të fshijmë nyjen brenda funksionit
Node_t * pop1 (Node_t ** head) (Node_t * out; if ((* head) == NULL) (dalje (STACK_UNDERFLOW);) out = * head; * head = (* head) -> next; kthehu jashtë; )
T pop2 (Node_t ** kokë) (Nyja_t * jashtë; vlera T; nëse (* kokë == NULL) (dalje (STACK_UNDERFLOW);) jashtë = * kokë; * kokë = (* kokë) -> tjetër; vlera = jashtë -> vlera; falas (jashtë); vlera e kthimit;)
Tani, në vend që të kontrollohet për gjatësinë e një grupi, kontrolli NULL i majës së pirgut përdoret kudo.
Funksion i thjeshtë shikimi
T përgjimi (konst Node_t * kokë) (nëse (koka == NULL) (dalja (STACK_UNDERFLOW);) kthe kokën-> vlerën;)
Përsëritja është mjaft interesante. Thjesht lëvizim nga një nyje në tjetrën derisa të arrijmë në fund.
PrintStack i pavlefshëm (const Node_t * head) (printf ("stack>"); ndërsa (head) (printf ("% d", head-> vlera); head = head-> next;))
Dhe një problem tjetër - tani nuk mund të shikoni vetëm madhësinë e pirgut. Ju duhet të shkoni nga fillimi në fund dhe të numëroni të gjithë elementët. Për shembull, kështu
Size_t getSize (konst Node_t * kokë) (madhësia_t = 0; ndërsa (koka) (madhësia ++; koka = koka-> tjetër;) kthen madhësinë;)
Natyrisht, madhësinë mund ta ruani veçmas, mund ta mbështillni pirgun me të gjitha të dhënat në një strukturë më shumë, etj. Le t'i shqyrtojmë të gjitha këto kur i shqyrtojmë listat në mënyrë më të detajuar.
i fundit në - i pari jashtë, "i fundit në - i pari jashtë").Më shpesh, parimi i funksionimit të një pirg krahasohet me një pirg pllakash: për të marrë të dytin nga lart, duhet të hiqni pjesën e sipërme.
Në disa gjuhë (p.sh. Lisp, Python) çdo listë mund të quhet pirg, pasi operacionet pop dhe push janë të disponueshme për to. Në C ++, biblioteka standarde ka një klasë me një strukturë dhe metoda të implementuara. etj.
YouTube kolegjial
1 / 3
Informatikë. Strukturat e të dhënave: Stack. Qendra e Mësimit Online Foxford
#9. Stack / 1. Assembler dhe procedura / Programimi nga e para
Bazat e rrjeteve të transmetimit të të dhënave. Modeli OSI dhe grumbulli i protokollit IP TCP. Bazat Ethernet.
Titra
Stack softuerësh
Organizimi në kujtesë
Shpesh pirgu zbatohet si një listë me një drejtim (çdo artikull në listë përmban, përveç informacionit të ruajtur në pirg, një tregues për artikullin tjetër në pirg).
Por gjithashtu shpesh pirgu ndodhet në një grup njëdimensional me adresa të renditura. Një organizim i tillë i pirgut është i përshtatshëm nëse një artikull informacioni zë një numër fiks fjalësh në memorie, për shembull, 1 fjalë. Kjo eliminon nevojën për të ruajtur një tregues të qartë në elementin tjetër të pirgut në elementin e pirgut, i cili kursen kujtesën. Në këtë rast, treguesi i stivës ( Stack Pointer, - PS) është zakonisht një regjistër procesor dhe tregon adresën e kreut të stackit.
Supozoni, për shembull, që kreu i stivit ndodhet në një adresë më të ulët, elementët e mëposhtëm janë të vendosur në adresat në rritje. Sa herë që një fjalë shtyhet në pirg, SP fillimisht zvogëlohet me 1 dhe më pas bëhet një shkrim në kujtesë në adresën nga SP. Sa herë që një fjalë del nga grumbulli (shfaqet), ajo fillimisht lexon adresën aktuale nga SP dhe më pas rrit përmbajtjen e SP me 1.
Kur organizoni një pirg në formën e një liste njëdrejtimëshe, vlera e variablit stack është një tregues në krye të saj - adresa e majës. Nëse pirgu është bosh, atëherë vlera e treguesit është NULL.
Një shembull i zbatimit të stackit në C:
struct stack (char * të dhëna; struct stack * next;);
Operacionet e stivës
Janë të mundshme tre operacione të stivës: shtimi i një artikulli (përndryshe shtytja), heqja e një artikulli (pop) dhe leximi i artikullit kryesor (shikimi).
Një shtytje shton një element të ri që tregon elementin që më parë ishte koka. Elementi i ri tani bëhet ai kryesor.
Kur një element fshihet (pop), i pari hiqet dhe koka bëhet ajo në të cilën ky objekt kishte një tregues (elementi tjetër). Në këtë rast, vlera e elementit të hequr kthehet.
shtytje e zbrazët (STACK * ps, int x) // Shtoni një artikull të ri në pirg(nëse (ps -> madhësia == STACKSIZE) // A është tejmbushur pirgu?(fputs ("Gabim: tejmbushja e stivës \ n", stderr); ndërprerje ();) tjetër (ps -> artikuj [ps -> madhësia ++] = x;)) int pop (STACK * ps) // Hiq nga pirgja(nëse (ps -> madhësia == 0) // A është pirgu bosh?(fputs ("Gabim: nën rrjedha e rafte \ n", stderr); ndërpres ();) tjetër (kthimi ps -> artikujt [- ps -> madhësia];))
Zona e aplikimit
Një pamje programatike e pirgut përdoret për të përshkuar strukturat e të dhënave të tilla si një pemë ose grafik. Kur përdorni funksione rekurzive, do të përdoret edhe steka, por pamja e saj harduerike. Përveç këtyre detyrave, steka përdoret për të organizuar
Procese të ngjashme ndodhin me një ndërprerje harduerike (procesori X86 ruan automatikisht regjistrin e flamujve në pirg gjatë një ndërprerjeje harduerike). Përveç kësaj, përpiluesit shpërndajnë variabla të procedurës lokale në stack (nëse procesori ofron akses në një vendndodhje arbitrare të stivit).
Para përdorimit të stivit, ai duhet të inicializohet në mënyrë që regjistrat SS: ESP të tregojnë adresën e kokës së stivit në zonën e RAM-it fizik, dhe numri i kërkuar i qelizave të memories duhet të rezervohet për ruajtjen e të dhënave në stack (është e qartë se një pirg në ROM, natyrisht, nuk mund të organizohet). Programet e aplikimit, si rregull, marrin një pirg të gatshëm për përdorim nga sistemi operativ. Në modalitetin e mbrojtur të procesorit, segmenti i gjendjes së detyrës përmban katër përzgjedhës të segmentit të stivës (për nivele të ndryshme privilegje), por vetëm një pirg përdoret në të njëjtën kohë.
