DOUG LLOYD: Bine, astfel de acest punct ești probabil destul de familiar cu tablouri si liste legate care este de două primar structuri de date care le-am a vorbit despre pentru păstrarea seturi de date de tipuri de date similare organizate. Acum vom vorbi despre un cuplu de variații pe tablouri si liste legate. În acest film vom pentru a vorbi despre stive. Mai exact vom vorbi despre o structură de date numită stivă. Reamintim de la discuțiile anterioare despre indicii și memorie, că stiva este, de asemenea, nume pentru un segment de memorie în cazul în care a declarat static memorie memory-- pe care le nume, variabile pe care le nume, et cetera și funcția de cadre pe care le, de asemenea, există cadre stiva de apel. Deci, aceasta este o structură de date stiva nu un segment de memorie stivă. BINE. 

Dar ceea ce este o stivă? Deci e destul de mult doar un tip special de structura care menține datele într-un mod organizat. Și nu există două foarte metode comune de punere în aplicare stive folosind două structuri de date că suntem deja familiarizați cu, tablouri si liste legate. Ce face o deosebită stivă este mod în care am pus informații în stiva, și modul în care elimina informațiile din stivă. În special cu stive regula este doar cel mai recent element în plus pot fi eliminate. 

Deci, cred că despre ea ca daca este o stivă. Suntem piling informații pe partea de sus de el însuși, și numai lucrul la partea de sus a gramada pot fi eliminate. Nu putem elimina lucru sub pentru că orice altceva ar fi colaps și cădea peste. Deci, suntem cu adevărat construim o stivă care trebuie apoi să eliminați bucata cu bucata. Din acest motiv ne-am referi în mod obișnuit la un stack ca o structură LIFO, ultimul intrat, primul ieșit. LIFO, ultimul intrat, primul ieșit. 

Deci, din cauza acestei restricții privind modul în care informațiile pot fi adăugate la și scoase dintr-o stivă, nu există cu adevărat doar două lucruri pe care le putem face cu un stack. Putem împinge, care este termen care le folosim pentru adăugarea un nou element la capătul superior al acesteia stivă, sau în cazul în care stiva nu există si suntem o crearea de la zero, creând teancul în primul rând ar fi împingere. Și apoi pop, asta e un fel de CS termen care le folosim pentru a elimina cele mai recent adăugat elementul din vârful stivei. 

Așa că am de gând să se uite la ambele implementari, pe ambele matrice și lista de legat pe bază de. Și am de gând să începe cu matrice pe bază de. Deci, aici e ideea de bază a ceea ce structura de date set de rețele pe bază de ar arăta. Avem o definiție tastat aici. In interiorul că avem doi membri sau câmpuri ale structurii. Avem o serie. Și din nou Sunt folosind arbitrară valoare tip de date. 

Deci, acest lucru ar putea fi orice tip de date, Int char sau un alt date tip ați creat anterior. Deci, avem o serie de capacitate dimensiune. Capacitate fiind o lira definit constant, probabil în altă parte în dosarul nostru. Deci observați deja cu aceasta special implementare suntem limitrofe noi înșine ca de obicei, a fost în cazul tablouri, care nu putem redimensiona dinamic, în cazul în care există un anumit număr elementelor maximă care putem pune în stivă nostru. În acest caz, este elemente de capacitate. 

De asemenea, ține evidența partea de sus a stivei. Care element este cel mai recent adăugate la stiva? Și așa ne-am urmări care într-o variabilă numită top. Și toate acestea se înfășurat împreună într-un nou tip de date numit un stack. Și odată ce suntem creat acest nou tip de date putem trata ca orice alt tip de date. Putem declara stivă s, la fel ca am putea face int x, sau y char. Și când spunem stivă s, și ceea ce se întâmplă este ne un set de memorie rezervat pentru noi. 

În acest caz, capacitatea de M-am decis, aparent este de 10 pentru că am o variabil unic de tip stivă care conține două câmpuri amintesc. O matrice, în acest caz se întâmplă să fie o serie de numere întregi așa cum este cazul în majoritatea exemplele mele. Și o altă variabilă întreg capabil să stocheze partea de sus, cel mai recent adăugat element stiva. Deci, unul singur teanc de ceea ce am doar arata ca acest lucru definit. Este o cutie care conține o serie de 10 ceea ce va fi numere întregi în acest caz și altă variabilă integer acolo în verde pentru a indica vârful stivei. 

Pentru a seta superior al acesteia stivă spunem doar s.top. Așa am acces la o câmp de rechemare structură. s.top este egal cu 0 în mod eficient face acest lucru pentru a stiva noastră. Deci, din nou, avem două operațiuni pe care le pot efectua acum. Putem împinge și putem pop. Să începem cu apăsare. Din nou, împingând este adăugarea unui nou Element de sus a stivei. 

Deci, ceea ce avem nevoie pentru a face în această matrice de punere în aplicare pe baza? Ei bine, în general, Funcția se va împinge a trebuie să accepte o pointer la stiva. Acum, ia un al doilea și cred despre el. De ce am vrea să acceptăm un pointer la stiva? Reamintim de la clipuri video anterioare referitoare la Domeniul de aplicare și indicii variabilă, ce s-ar întâmpla dacă ne-am trimis stack, e mai degrabă în ca parametru? Ce ar fi de fapt a trecut acolo? Amintiți-vă vom crea o copie când l-am trece la o funcție daca nu vom folosi indicii. Și astfel această funcție împinge nevoilor să accepte un pointer la stiva astfel încât suntem de fapt în schimbare stiva intenționăm să se schimbe. 

Un alt lucru împinge probabil vrea să accepta este un element de date a valorii tip. In acest caz, din nou, un număr întreg care vom adăuga la partea de sus a stivei. Deci avem doi parametri noastre. Ce vom acum face în interiorul împinge? Ei bine, pur și simplu, ne doar de gând să adăugați că elementul în partea de sus a stivei și apoi modificați în cazul în care partea de sus a stiva este că e dot valoare de top. Deci, asta este ceea ce o funcție declarație de apăsare s-ar putea arata ca intr-un -matrice pe bază de punere în aplicare. 

Din nou, aceasta nu este o regula tare si rapid care le-ar putea schimba acest lucru și au aceasta variază în moduri diferite. Poate că s este declarat la nivel global. Și astfel încât să nu nevoie, chiar pentru a trece este ca un parametru. Aceasta este din nou doar o caz general pentru apăsare. Și acolo sunt diferite moduri de a pune în aplicare. Dar în acest caz nostru împinge va avea două argumente, un pointer la o stivă și un element de date din valoarea de tip, întreg în acest caz. 

Deci, ne-am declarat s, am a declarat s.top este egal cu 0. Acum, haideți să împingeți Numărul 28 pe stiva. Ei bine, ce înseamnă asta? Ei bine, în prezent partea de sus a stivei este 0. Și așa mai departe ceea ce este practic se va întâmpla este vom lipi numărul 28 în matrice Localizare 0. Destul de simplu, chiar, că a fost în partea de sus, iar acum suntem bine să plec. Și atunci avem nevoie pentru a schimba ceea ce partea de sus a stivei va fi. Astfel încât data viitoare am împinge un element în, vom stoca în Locație matrice, probabil, nu 0. Noi nu vrem să suprascrieți ceea ce ne-am pus acolo. Și așa vom muta doar în partea de sus a 1. Asta face, probabil, sens. 

Acum, dacă vrem să pună un alt element pe stiva, spune că vrea să împingă 33, Ei bine, acum noi suntem doar de gând să ia 33 și a pus la matrice număr de locație 1, și apoi modificați în partea de sus a noastră stiva să fie matrice locație numărul doi. Deci, în cazul în care data viitoare vrem să împinge un element pe stivă, Va fi pus în matrice locație 2. Și să faci asta o dată. Vom împinge 19 pe a stivelor. Vom pune 19 în matrice locație 2 și de a schimba partea de sus a stivei noastre să fie matrice locație 3 astfel încât în ​​cazul în care următoarea dată când am nevoie pentru a face un impuls suntem bine să plec. 

OK, așa că e împinge într-o coajă de nucă. Ce zici de popping? Deci popping este un fel de omologul de împingere. E cum am elimina datele de pe stivă. Și în nevoile pop generale să facă următoarele. Acesta trebuie să accepte un pointer la stivă, din nou, în cazul general. Într-un alt caz s-ar putea au declarat stiva la nivel global, caz în care nu aveți nevoie să-l treacă în deoarece are deja acces la aceasta ca o variabilă globală. Dar atunci ce altceva mai trebuie să facem? Ei bine, am fost incrementarea partea de sus a stivei în împingere, așa că, probabil, de gând să doriți la decrement partea de sus a stivei în pop, nu? Și apoi, desigur, ne, de asemenea, de gând să doriți pentru a reveni la valoarea pe care le elimina. Dacă suntem adăugarea de elemente, ne-o dorim pentru a obține elemente din mai târziu, noi, probabil, de fapt, doriți să le stocați așa că am Nu-i doar șterge din stiva și apoi nu fac nimic cu ele. În general, dacă suntem împingere și popping aici vrem pentru a stoca acest informații într-un mod semnificativ și deci nu face sens doar aruncați. Deci, această funcție ar trebui să probabil a reveni o valoare pentru noi. 

Deci, asta este ceea ce o declarație pentru pop s-ar putea arata ca acolo, la partea din stânga sus. Această funcție returnează Date de valoare de tip. Din nou, am fost folosind întregi de-a lungul. Și acceptă un pointer la o stivă ca argumentul său unic sau parametru unic. Deci, ce este pop de gând să faci? Să presupunem că vrem să acum pop un element de pe s. Deci, amintiți-vă am spus că sunt ultima stive în, primul ieșit, structuri de date LIFO. Care element este de gând să fi eliminate din stivă? Ai ghicit 19? Pentru că ai avea dreptate. 19 a fost ultimul element am adaugat la stiva atunci când am fost împingerea elemente pe, Și așa va primul element care se îndepărtează. E ca și cum am spus 28, și apoi am pus 33 pe partea de sus a acesteia, si am pus 19 pe deasupra. Singurul element putem scoate este de 19. 

Acum, în diagrama aici ceea ce am făcut este un fel de șters 19 de matrice. Asta nu e de fapt ceea ce am de gând să faci. Vom merge la fel doar de pretinde că nu este acolo. E încă acolo, în că locație de memorie, dar noi suntem doar de gând să-l ignore prin schimbarea de sus a stivei noastre de a fi 3 la 2. Deci, dacă ar fi să împinge acum un alt element pe stiva, ar scrie peste 19. 

Dar să nu treacă prin probleme de ștergerea 19 din stivă. Putem pretinde pur și simplu nu este acolo. În scopul stivei a dispărut dacă am schimba partea de sus să fie 2 în loc de 3. Bine, astfel că a fost destul de mult. Asta e tot ce trebuie să facem să pop un element off. Să o facem din nou. Deci l-am evidențiat în roșu aici pentru a indica facem un alt apel. Vom face același lucru. 

Deci, ce se va întâmpla? Ei bine, vom stoca 33 în X și vom pentru a schimba vârful stivei la 1. Așa că, dacă am acum pentru a împinge un elementul în stivă care suntem de gând să faci acum, ce se va întâmpla este vom suprascriere matrice locație numărul 1. Astfel încât 33, care a fost un fel de lăsat în spatele că ne-am prefăcut nu este acolo mai, noi suntem doar de gând să-l lovească și a pus acolo în loc de 40. Și apoi, desigur, Din moment ce am făcut un push, vom incrementa partea de sus a stivei la 1 la 2 astfel încât, dacă vom adăuga acum Un alt element Va du-te în matrice locație numărul doi. 

Acum liste legate sunt un alt mod de a pune în aplicare stive. Și dacă această definiție cu privire la Ecranul aici pare familiar pentru tine, este pentru că se pare aproape exact aceeași, în fapt, aceasta destul de mult este exact La fel ca o listă individual legate, dacă vă amintiți de la discuția noastră de legate individual liste într-un alt film. Singura restricție aici este pentru noi ca programatori, nu avem voie să inserați sau ștergeți aleatoriu din lista individual legat care am putea face anterior. Putem introduce doar acum și șterge de la partea din față sau în partea de sus a strâns legat Lista. Asta e de fapt singurul diferență, totuși. Aceasta este de altfel o listă individual legat. E doar restricția înlocuirea pe noi înșine ca programatori care schimba-l într-o stivă. 

Regula de aici este de a menține întotdeauna o pointer la cap de o listă legată. Aceasta este, desigur, o, în general, regulă importantă în primul rând. Pentru lista legate individual oricum nevoie doar de un pointer la cap pentru a avea că lanț putea să se refere pentru fiecare alt element în lista legate. Dar e deosebit de important, cu un stack. Și așa, în general, tu ești O să vrea de fapt Acest indicator a fi o variabilă globală. Este, probabil, o să fi chiar mai ușor așa. Deci, care sunt analogii de împingere și pop? Dreapta. Deci, împingând din nou este adăugarea un nou element de stiva. Într-o listă legată care înseamnă că vom avea pentru a crea un nou nod pe care suntem merge pentru a adăuga în lista legate, și apoi urmați pașii atente care le-am subliniat anterior în listele individual legate de adauga la lanțul fără a rupe lanțul și pierderea sau orice orphaning Elemente ale listei de legătura. Și asta e de fapt despre ce puțin blob de text acolo rezumă. Și haideți să aruncăm o privire la ea ca o diagramă. 

Deci, aici e lista noastră legată. Acesta conține concomitent patru elemente. Și mai perfect aici e noastră stiva conține patru elemente. Și să spunem că vrem acum să împinge un element nou pe acest stivă. Și vrem să împingă un nou articol căror date valoare este de 12. Ei bine, ce vom face? Ei bine, în primul rând vom spațiu malloc, dinamic aloca spațiu pentru un nou nod. Și, desigur, imediat după facem un apel la noi malloc mereu asigurați-vă că pentru a verifica pentru nul, pentru că dacă ne-am întors nul nu a fost un fel de probleme. Noi nu vrem să dereference că null pointer sau vei suferi o defecțiune seg. Asta nu este bine. Deci ne-am malloced a nodului. Vom presupune că am avut succes aici. Vom pune în 12 câmpul de date de acel nod. Acum nu vă amintiți care a indicii noastre se mută lângă asa ca nu rupe lantul? Avem o serie de opțiuni, dar aici singurul care va fi în siguranță este de a stabili următoare de știri pointer la punct la cap vechi listei sau ceea ce va fi în curând șef veche a listei. Și acum că toate noastre elemente sunt legate împreună, ne putem muta doar lista de la punctul în același loc pe care noi nu. Și acum ne-am impins efectiv o element nou pe partea din față a stivei. 

Pentru a ne pop vreau doar să șterge că prim element. Și așa mai departe, practic ceea ce trebuie să facem aici, bine trebuie să găsim al doilea element. În cele din urmă, care va deveni noul cap după ce am șterge prima. Deci, avem nevoie doar pentru a începe de la la început, a muta o înainte. După avem o așteptare pe o înainte de unde am în prezent sunt putem șterge primul în condiții de siguranță si apoi ne putem muta doar capul pentru a indica ceea ce a fost al doilea mandat și apoi acum este primul după care nod a fost șters. 

Deci, din nou, a lua o privire ca pe o diagrama ne doriți să pop acum un Element de pe acest stack. Deci, ce facem? Ei bine, vom mai întâi de gând să creeze un nou indicator care va pentru a indica în același loc ca și cap. Vom muta o poziție înainte de a spune egali trav trav următor, de exemplu, care ar avansa cel trav pointer poziție înainte. Acum, că avem o țineți pe primul element prin lista pointer numit, și al doilea element prin intermediul unui pointer numit trav, putem șterge cu siguranță că primul element de din stivă fără a pierde restul lanțului deoarece ne au un mod de a se refere la al doilea element transmite prin intermediul pointer trav numit. 

Deci, acum putem elibera acel nod. Putem elibera lista. Și atunci tot ce trebuie să facem acum este muta lista de la punctul în același loc că trav face, si noi suntem un fel de spate în cazul în care am început înainte de 12 împins pe, în primul rând, chiar. Acest lucru este exact acolo unde am fost. Am avut această stivă de patru elemente. Am adăugat un al cincilea. Am împins o cincime element de pe, și apoi ne-am mi-a venit ca cel mai recent Element adăugat înapoi. 

Asta e într-adevăr destul de mult tot ceea ce este de a stive. Puteți le pună în aplicare ca matrice. Puteți le pună în aplicare ca listele legate. Există, desigur, alte modalități de a le pune în aplicare, de asemenea. Practic motivul pentru care am ar folosi stive este de a menține datele în așa fel că cel mai recent adăugat element este primul lucru pe care suntem O să vrea să mă întorc. Sunt Doug Lloyd, aceasta este CS50.