Folosim limbaje de programare din ce în ce mai avansate care ne permit să scriem mai puțin cod și să obținem rezultate grozave. Trebuie să plătești pentru asta. Pe măsură ce facem din ce în ce mai puține lucruri de nivel scăzut, devine normal ca mulți dintre noi să nu înțeleagă pe deplin ce sunt stiva și heap-ul, cum se întâmplă de fapt compilarea, care este diferența dintre tastarea statică și cea dinamică etc. Nu spun că toți programatorii nu știu despre aceste concepte - cred doar că uneori merită să ne întoarcem la lucruri atât de vechi.
Astăzi vom vorbi doar despre un singur subiect: stiva și grămada. Atât stiva, cât și heap-ul se referă la diferite locații în care are loc gestionarea memoriei, dar strategia pentru această gestionare este dramatic diferită.
Grămadă
Stiva este o zonă de RAM care este creată pentru fiecare fir. Funcționează în ordinea LIFO (Last In, First Out), adică ultima bucată de memorie adăugată la stivă va fi prima din coadă pentru ieșirea din stivă. De fiecare dată când o funcție declară o nouă variabilă, aceasta este împinsă în stivă, iar atunci când acea variabilă iese din domeniul de aplicare (de exemplu, când funcția se termină), este automat scoasă din stivă. Când o variabilă de stivă este eliberată, această zonă de memorie devine disponibilă pentru alte variabile de stivă.
Această natură a stivei face managementul memoriei foarte logic și simplu de executat pe CPU; aceasta duce la viteză mare, mai ales că timpul ciclului pentru actualizarea octetului stivei este foarte scurt, adică acest octet este cel mai probabil legat de memoria cache a procesorului. Cu toate acestea, această formă strictă de guvernare are dezavantaje. Dimensiunea stivei este o valoare fixă, iar depășirea memoriei alocate pe stivă va avea ca rezultat o depășire a stivei. Mărimea este setată la crearea fluxului și fiecare variabilă are o dimensiune maximă în funcție de tipul de date. Acest lucru vă permite să limitați dimensiunea unor variabile (de exemplu, numere întregi) și vă obligă să predeclarați dimensiunea unor tipuri de date mai complexe (de exemplu, matrice), deoarece stiva nu le va permite să o modifice. În plus, variabilele situate pe stivă sunt întotdeauna locale.
Ca rezultat, stiva vă permite să gestionați memoria în cel mai eficient mod - dar dacă aveți nevoie să utilizați structuri de date dinamice sau variabile globale, atunci ar trebui să acordați atenție grămezii.
Morman
Heap-ul este stocarea memoriei, situată tot în RAM, care permite alocarea dinamică a memoriei și nu funcționează ca o stivă: este doar un depozit pentru variabilele tale. Când alocați o bucată de memorie pe heap pentru a stoca o variabilă, o puteți accesa nu numai în fir, ci în întreaga aplicație. Acesta este modul în care sunt definite variabilele globale. Când aplicația se termină, toate zonele de memorie alocate sunt eliberate. Dimensiunea heap-ului este setată la pornirea aplicației, dar, spre deosebire de stivă, este limitată doar fizic, iar acest lucru vă permite să creați variabile dinamice.
Interacționați cu heap-ul prin referințe, numite în mod obișnuit pointeri - variabile ale căror valori sunt adrese ale altor variabile. Prin crearea unui pointer, indicați o locație de memorie din heap, care setează valoarea inițială pentru variabilă și spune programului unde să acceseze acea valoare. Datorită naturii dinamice a heap-ului, CPU nu participă la controlul acestuia; în limbile fără un colector de gunoi (C, C ++), dezvoltatorul trebuie să elibereze manual bucăți de memorie care nu mai sunt necesare. Nerespectarea acestui lucru poate duce la pierderi de memorie și la fragmentare, ceea ce va încetini în mod semnificativ heap-ul.
În comparație cu stiva, heap-ul este mai lent, deoarece variabilele sunt împrăștiate în memorie, mai degrabă decât să se așeze în partea de sus a stivei. Gestionarea necorespunzătoare a memoriei în heap îi încetinește activitatea; totuși, acest lucru nu îi diminuează importanța - dacă trebuie să lucrați cu variabile dinamice sau globale, utilizați heap-ul.
IBM a făcut greșeala dramatică de a nu furniza o implementare hardware pentru stivă. Această serie conținea multe alte soluții nereușite, dar, din păcate, a fost copiată în Uniunea Sovietică sub numele ES EVM (Seria Unită), iar toate dezvoltările proprii au fost suspendate. Acest lucru a adus industria sovietică înapoi cu mulți ani în domeniul dezvoltării computerelor.Coadă
Coada ca structură de date este de înțeles chiar și pentru persoanele care nu sunt familiarizate cu programarea. Coada conține elemente, parcă aliniate unul după altul într-un lanț. Coada are un început și un sfârșit. Puteți adăuga articole noi doar la sfârșitul cozii; puteți ridica articole doar de la început. Spre deosebire de o coadă obișnuită, pe care o puteți părăsi oricând dacă doriți, nu puteți elimina elemente din mijlocul cozii de programare.
Coada poate fi gândită ca un tub. La un capăt al tubului se pot adăuga bile - elementele cozii, de la celălalt capăt sunt îndepărtate. Articolele din mijlocul cozii, de ex. bilele din interiorul tubului nu sunt disponibile. Capătul tubului la care se adaugă bilele corespunde sfârșitului cozii, capătul din care sunt duse la începutul cozii. Astfel, capetele tubului nu sunt simetrice, bilele din interiorul tubului se deplasează doar într-o singură direcție.
În principiu, ar fi posibil să se permită adăugarea articolelor la ambele capete ale cozii și să le ridice și de la ambele capete. O astfel de structură de date există și în programare, numele ei este „dec”, din engleză. Coadă dublă, adică coadă cu două capete. Dec este folosit mult mai rar decât coada.
Utilizarea cozii în programare corespunde aproape rolului său în viața de zi cu zi. Coada este aproape întotdeauna asociată cu deservirea cererilor, în cazurile în care acestea nu pot fi executate instantaneu. Coada menține, de asemenea, ordinea în care sunt servite cererile. Luați în considerare, de exemplu, ce se întâmplă atunci când o persoană apasă o tastă de pe tastatura unui computer. Astfel, persoana cere computerului să efectueze o acțiune. De exemplu, dacă imprimă doar text, atunci acțiunea ar trebui să constea în adăugarea unui caracter la text și poate fi însoțită de redesenarea zonei ecranului, derularea ferestrei, reformatarea unui paragraf etc.
Orice sistem de operare, chiar și cel mai simplu, este întotdeauna multitasking într-o măsură sau alta. Aceasta înseamnă că în momentul în care o tastă este apăsată, sistemul de operare poate fi ocupat cu alte lucrări. Cu toate acestea, sistemul de operare nu are dreptul să ignore apăsarea tastei în orice situație. Prin urmare, computerul este întrerupt, își amintește starea și trece la procesarea apăsării tastei. Această procesare ar trebui să fie foarte scurtă pentru a nu perturba alte sarcini. Comanda emisă prin apăsarea unei taste este pur și simplu adăugată la sfârșitul cozii de cereri în așteptare. După aceea, întreruperea se termină, computerul își restabilește starea și continuă lucrul care a fost întrerupt prin apăsarea tastei. Solicitarea din coadă nu va fi executată imediat, ci doar atunci când îi va veni rândul.
În Windows, aplicațiile cu ferestre se bazează pe mesajele care sunt trimise către acele aplicații. De exemplu, există mesaje despre apăsarea butonului mouse-ului, despre închiderea unei ferestre, despre necesitatea redesenării zonei ferestrei, despre selectarea unui element de meniu etc. Fiecare program are coada de cereri... Când programul primește intervalul de timp de execuție, selectează următoarea solicitare din capul cozii și o execută. Astfel, munca unei aplicații ferestre constă, în termeni simpli, în executarea secvențială a cererilor din coada acesteia. Coada este menținută de sistemul de operare.
O abordare a programării, care constă nu într-un apel direct de proceduri, ci în transmiterea de mesaje care sunt introduse coada de cereri, are multe avantaje și este una dintre caracteristicile programării orientate pe obiecte. Deci, de exemplu, dacă un program de fereastră trebuie să se termine din orice motiv, este mai bine să nu apelați imediat comanda de ieșire, ceea ce este periculos, deoarece încalcă logica de lucru și poate duce la pierderea datelor. În schimb, programul își trimite un mesaj de închidere, care va fi livrat către coada de cereriși executat în urma solicitărilor anterioare.
Implementarea cozii de matrice
După cum sa menționat deja, matricea este dată programatorului de mai sus, toate celelalte structuri de date trebuie implementate pe baza acesteia. Desigur, o astfel de implementare poate fi în mai multe etape, iar matricea nu acționează întotdeauna ca o bază de implementare imediată. În cazul unei cozi, cele mai populare două implementări sunt implementarea bazată pe matrice continuă, numită și implementarea bufferului circular și implementare de referință, sau o implementare bazată pe liste. Implementări de referință vor fi discutate mai jos.
Odată cu implementarea continuă a unei cozi, o matrice de lungime fixă N acționează ca bază, astfel, coada este limitată și nu poate conține mai mult de N elemente. Indicii elementelor de matrice variază de la 0 la N - 1. Pe lângă o matrice, implementarea cozii stochează trei variabile simple: indexul începutului cozii, indexul sfârșitului cozii și numărul de elemente din coadă. Elementele cozii sunt cuprinse în segmentul de matrice de la indexul de început până la indexul de sfârșit.
Când adăugați un nou element la sfârșitul cozii, indexul final crește mai întâi cu unu, apoi noul element este scris în celula matricei cu acest index. În mod similar, la preluarea unui element din capul cozii, conținutul celulei matrice cu indexul capului cozii este stocat ca rezultat al operației, apoi indicele capului cozii este mărit cu unu. . Atât indicele de început, cât și indicele de sfârșit se deplasează de la stânga la dreapta în timpul funcționării. Ce se întâmplă când indexul de sfârșit de linie ajunge la sfârșitul matricei, adică N - 1?
Ideea cheie din spatele implementării unei cozi este că matricea este conectată mental într-un inel. Se consideră că ultimul element al tabloului este urmat de primul său element (reamintim că ultimul element are indicele N - 1, iar primul are indicele 0). La deplasarea indexului sfârșitului cozii la dreapta, în cazul în care indică către ultimul element al matricei, se trece la primul element. Astfel, un segment continuu al matricei ocupat de elementele cozii poate trece prin sfârșitul matricei până la începutul acestuia.
Grămadă
Stiva este cea mai populară și probabil cea mai importantă structură de date din programare. O stivă este un dispozitiv de stocare din care articolele sunt scoase în ordine inversă adăugării lor. Este ca o coadă greșită, în care primul care servește este cel care a intrat ultimul. În literatura de programare, abrevierile care indică disciplina cozii și stivei sunt în general acceptate. Disciplina de coadă este desemnată FIFO, ceea ce înseamnă First In First Out. Disciplina stivei este indicată de LIFO, ultimul intrat, primul ieşit.
O stivă poate fi considerată ca un tub vertical cu fundul cu arc. Capătul superior al tubului este deschis, puteți adăuga sau, după cum se spune, împinge elemente în el. Termenii obișnuiți în limba engleză în acest sens sunt foarte colorați, operația de adăugare a unui element la stivă este desemnată push, ceea ce înseamnă „împinge, împinge”. Elementul nou adăugat împinge articolele împinse în stivă mai devreme cu o poziție în jos. Când elementele sunt scoase din stivă, ele par să fie împinse în sus, în engleză pop ("shoot").
Un exemplu de teanc este un car de fân, un teanc de hârtie pe o masă, un teanc de farfurii și altele asemenea. De aici provine numele stivei, care în engleză înseamnă stivă. Plăcile sunt scoase din stivă în ordinea inversă adăugării. Este disponibilă doar placa superioară, adică. farfurie în vârful stivei... Un bun exemplu ar fi, de asemenea, o fundătură de cale ferată, în care pot fi asamblate vagoane.
Utilizarea stivei în programare
Stiva este folosită destul de des și într-o varietate de situații. Următorul obiectiv îi unește: trebuie să salvezi până la sfârșit niște lucrări care nu au fost încă finalizate, dacă trebuie să treci la o altă sarcină. Stiva este folosită pentru a salva temporar starea unei lucrări neterminate până la sfârșit. După salvarea stării, computerul trece la o altă sarcină. La sfârșitul execuției sale, starea de lucru în așteptare este restabilită din stivă, iar computerul reia lucrul întrerupt.
De ce este folosit stiva pentru a salva starea jobului întrerupt? Să presupunem că computerul îndeplinește sarcina A. În procesul de execuție, devine necesară finalizarea sarcinii B. Starea sarcinii A este reținută și computerul continuă să execute sarcina B. Dar la urma urmei, atunci când execută sarcina B, computerul poate trece la o altă sarcină C și va fi necesar să salvezi starea sarcinii B înainte de a trece la C. Ulterior, la sfârșitul lui C, starea sarcinii B va fi mai întâi restabilită, apoi, la sfârșitul lui B, starea sarcinii A va fi restabilită. Astfel, recuperarea are loc în ordinea inversă a economisirii, ceea ce este în concordanță cu disciplina stivei.
Stiva vă permite să organizați recursiunea, de ex. apelul subrutinei către sine, fie direct, fie printr-un lanț de alte apeluri. De exemplu, să presupunem că subrutina A execută un algoritm care depinde de parametrul de intrare X și, eventual, de starea datelor globale. Pentru cele mai simple valori ale lui X, algoritmul este implementat direct. Pentru valori X mai complexe, algoritmul este implementat ca o reducere la aplicarea aceluiași algoritm la valori X mai simple. În acest caz, subrutina A se referă la sine, trecând o valoare X mai simplă ca parametru. Într-un astfel de apel, valoarea anterioară a parametrului X, precum și toate variabilele locale ale subrutinei A, sunt salvate în stivă. În continuare, se creează un nou set de variabile locale și o variabilă care conține o nouă valoare (mai simplă) a parametrului X. Subrutina numită A operează pe un nou set de variabile fără a distruge setul anterior. La sfârșitul apelului, vechiul set de variabile locale și starea veche a parametrului de intrare X sunt restaurate din stivă, iar subrutina continuă din punctul în care a fost întreruptă.
De fapt, nici măcar nu trebuie să stocați valorile variabilelor locale ale subrutinei pe stivă într-un mod special. Faptul este că variabilele locale ale unei subrutine (adică, internă, variabile de lucru, care sunt create la începutul execuției sale și distruse la sfârșit) sunt plasate pe o stivă implementată în hardware bazată pe memoria obișnuită cu acces aleatoriu. La începutul activității sale, subrutina ocupă un loc în stivă pentru variabilele sale locale, această bucată de memorie din stiva hardware este de obicei numită bloc variabil local sau in engleza cadru("cadru"). La sfârșitul activității sale, subrutina eliberează memorie prin eliminarea unui bloc din variabilele sale locale din stivă.
Pe lângă variabilele locale, stiva hardware stochează adresele returnate pentru apelurile subrutine. Să fie apelată o subrutină la un moment dat în programul A B... Înainte de apelarea subrutinei B, adresa instrucțiunii care urmează instrucțiunii care apelează B este stocată în stivă. Acesta este așa-numitul adresa expeditorului pentru a programa A. La sfârșitul activității sale, subrutina B trimite adresa de retur programului A din stivă și returnează controlul la această adresă. Astfel, calculatorul continuă să execute programul A din instrucțiunea care urmează instrucțiunii de apelare. Majoritatea procesoarelor au instrucțiuni speciale care acceptă apelarea unei subrutine împingând mai întâi adresa de retur pe stivă și revenind din subrutină la adresa apărută din stivă. De obicei, comanda de apelare se numește apel, comanda de returnare este returnare.
Parametrii unei subrutine sau funcție sunt, de asemenea, împinși în stivă înainte de a o apela. Ordinea în care sunt introduse în stivă depinde de convențiile limbajelor de nivel înalt. Deci, în C sau C ++, primul argument al unei funcții este în partea de sus a stivei, al doilea este sub ea și așa mai departe. În Pascal, opusul este adevărat, în partea de sus a stivei se află ultimul argument al funcției. (Prin urmare, apropo, funcțiile cu un număr variabil de argumente, cum ar fi printf, sunt posibile în C, dar nu în Pascal.)
În Fortran-4, unul dintre cele mai vechi și de succes limbaje de programare, argumentele sunt trecute printr-o zonă specială de memorie, care este posibil să nu fie localizată pe stivă, deoarece calculatoare precum IBM 360 sau computerele ES fără implementare hardware încă existau. până la sfârșitul anilor 70 ai secolului XX.stiva. Adresele de returnare au fost, de asemenea, stocate nu în stivă, ci în locații de memorie fixate pentru fiecare subrutină. Programatorii numesc astfel de memorie statică în sensul că variabilele statice ocupă întotdeauna același loc în memorie în orice moment în care programul rulează. Când se utilizează numai memorie statică, recursiunea nu este posibilă, deoarece atunci când se efectuează un nou apel, valorile anterioare ale variabilelor locale sunt distruse. În referința Fortran-4, s-au folosit doar variabile statice, iar recursiunea a fost interzisă. Până acum, limbajul Fortran este utilizat pe scară largă în calculele științifice și de inginerie, cu toate acestea, standardul modern Fortran-90 introduce deja memoria stivă, eliminând deficiențele versiunilor anterioare ale limbajului.
Implementarea stivei bazată pe matrice
Implementarea stivei bazată pe matrice este un clasic al programării. Uneori, chiar și conceptul de stivă nu este identificat destul de corect cu această implementare.
Baza implementării este o matrice de dimensiune N, astfel, este implementată o stivă de dimensiune limitată, a cărei adâncime maximă nu poate depăși N. Indicii celulelor matrice variază de la 0 la N - 1. Elementele stivei sunt stocate într-o matrice după cum urmează: elementul din partea de jos a stivei este situat la începutul matricei, adică. la indexul 0, elementul de deasupra celui mai jos element al stivei este stocat la indexul 1 și așa mai departe. Partea de sus a stivei este stocată undeva în mijlocul matricei. Indexul articolului din partea de sus a stivei este stocat într-o variabilă specială numită în mod obișnuit indicatorul N - 1. Elementele stivei ocupă un segment contiguu al matricei, începând cu celula al cărei index este stocat în pointerul stivei și terminând cu ultima celulă din matrice. În această variantă, stiva crește în direcția indicilor descrescători. Dacă stiva este goală, atunci indicatorul stivei conține valoarea N (care este cu unul mai mult decât indexul ultimei celule din matrice).
Bună, sunt student în anul II la o universitate tehnică. După ce am sărit peste câteva perechi de programare din motive de sănătate, m-am lovit de o neînțelegere a unor subiecte precum „Stiva” și „Coadă”. Prin încercare și eroare, după câteva zile, în sfârșit, mi-am dat seama ce era și cu ce se mânca. Pentru ca înțelegerea dvs. să nu dureze atât de mult, în acest articol vă voi spune despre ce este o „Stiva”, cum și prin ce exemple am înțeles ce este. Dacă vă place, voi scrie a doua parte, care va atinge un astfel de concept precum „Coadă”
Teorie
Pe Wikipedia, definiția unei stive este:
Stivă (stivă engleză - o stivă; stiva este citită) este un tip de date abstract care este o listă de elemente organizate conform principiului LIFO (în engleză last in - first out, "last in - first out").
Aceasta este o definiție destul de completă, dar ar putea fi puțin dificil de înțeles pentru începători.
Prin urmare, primul lucru pe care aș dori să mă concentrez este prezentarea stivei sub formă de lucruri din viață. Primul lucru care mi-a venit în minte a fost interpretarea sub forma unui teanc de cărți, unde cartea de sus este cea de sus.
De fapt, un teanc poate fi reprezentat ca un teanc de orice obiecte, fie că este vorba de un teanc de foi, caiete, cămăși și altele asemenea, dar exemplul cu cărți cred că va fi cel mai optim.
Deci, în ce constă stiva?
Stiva este formată din celule (în exemplu, acestea sunt cărți), care sunt prezentate sub forma unei structuri care conține unele date și un pointer către tipul acestei structuri către următorul element.
Greu? Nu contează, hai să ne dăm seama.
Această imagine prezintă o stivă schematică. Blocul „Date / * următorul” este celula noastră. * în continuare, după cum putem vedea, indică către următorul element, cu alte cuvinte, * indicatorul următor stochează adresa celulei următoare. Indicatorul * TOP indică partea de sus a stivei, adică stochează adresa acesteia.
Cu teoria terminată, să trecem la practică.
Practică
În primul rând, trebuie să creăm o structură care va fi „celula” noastră.
cod C++
struct comp (// O structură numită comp (din componenta cuvânt) int Data; // Unele date (pot fi oricare, de exemplu, puteți scrie int cheia; char Data; puteți adăuga și câteva date) comp * next ; // Un pointer de tip comp la următorul element);
Pentru începători, poate să nu fie clar de ce indicatorul nostru este de tip comp, sau mai degrabă, indicatorul de tipul de structură comp. Permiteți-mi să explic că, pentru ca indicatorul * următor să stocheze structura comp, trebuie să indice tipul acestei structuri. Cu alte cuvinte, specificați ce va stoca pointerul.
După ce am setat „Celula”, să trecem la crearea funcțiilor.
Funcții
Funcția de a crea o „stivă”/adăugarea unui articol la „stivă”
La adăugarea unui element, vom avea două situații:
- Stiva este goală și trebuie creată
- Stiva există deja și trebuie doar să-i adăugați un nou element
cod C++
void s_push (comp ** top, int D) (// funcție de tip void (nu returnează nimic) care duce un pointer către partea de sus a stivei și o variabilă care va fi scrisă în celula comp * q; // Creați o noul pointer q de tipul de structură comp. de fapt, acesta este noul nostru element q = new comp (); // alocați memorie pentru noul element q-> Data = D; // scrieți numărul necesar în elementul Data dacă (sus == NULL) (// Dacă nu există un vârf, adică stiva este goală * top = q; // partea de sus a stivei va fi un element nou) altfel // dacă stiva nu este goală ( q-> next = * top; // Facem legătura de la noul element la vârf. Adică punem cartea în partea de sus a stivei . * top = q; // Notăm că partea de sus este acum un nou element))
Să luăm puțin mai multe detalii.
În primul rând, de ce funcția ia ** top, adică un pointer către un pointer, de dragul clarității, voi lăsa această întrebare pentru mai târziu. În al doilea rând, să vorbim mai detaliat despre q-> următorul = * sus si ce inseamna asta ->
.
-> înseamnă că, aproximativ vorbind, intrăm în structura noastră și obținem un element al acestei structuri de acolo. In linie q-> următorul = * sus obținem din celula noastră un pointer către următorul element * următor și îl înlocuim cu un pointer care indică vârful stivei * sus. Cu alte cuvinte, comunicăm, de la noul element până la vârful stivei. Nimic complicat aici, la fel ca cu cărțile. Am pus noua carte exact în partea de sus a teancului, adică facem o conexiune de la noua carte la vârful teancului de cărți. După aceea, noua carte devine automat partea de sus, deoarece teancul nu este un teanc de cărți, trebuie să indicăm că noul element este un top, pentru aceasta scriem: * sus = q;.
Funcția de a elimina un element din „Stiva” prin date
Această funcție va elimina un element din stivă dacă numărul de date al celulei (q-> Date) este egal cu numărul pe care noi înșine îl vom desemna.
Pot exista astfel de opțiuni:
- Celula pe care trebuie să o ștergem este partea de sus a stivei
- Celula pe care trebuie să o ștergem se află la sfârșit sau între două celule
cod C++
void s_delete_key (comp ** top, int N) (// funcția care ia partea de sus și numărul de șters comp * q = * top; // creează un pointer de tip comp și îl echivalează (pune) în partea de sus a stack comp * prev = NULL; // creăm un pointer către elementul anterior, de la început va fi gol în timp ce (q! = NULL) (// atâta timp cât pointerul q nu este gol, vom executa codul în o buclă, dacă încă se termină într-o buclă goală dacă (q-> Data == N) (// dacă Datele elementului sunt egale cu numărul pe care trebuie să-l ștergem dacă (q == * sus) (/ / dacă un astfel de indicator este egal cu partea de sus, adică elementul pe care trebuie să-l ștergem este top * top = q- > next; // mutați partea de sus la următorul element liber (q); // ștergeți cell q-> Data = NULL; // Apoi, pentru a evita erori, punem la zero variabilele din celula ștearsă, deoarece în unele compilatoare celula ștearsă are valori ale variabilelor non-NULL, dar literalmente „Citirea memoriei este imposibilă” sau numere „ -2738568384" sau altele, în funcție de compilator. q-> next = NULL;) else // if element n ultimul sau între alte două elemente (prev-> next = q-> next; // Legătură de la elementul anterior la următorul liber liber (q); // șterge celula q-> Date = NULL; // zero variabilele q -> următorul = NULL; )) // dacă Datele elementului NU sunt egale cu numărul pe care trebuie să-l eliminăm prev = q; // amintiți-vă celula curentă ca pe cea anterioară q = q-> următoare; // mutați indicatorul q la următorul element))
În acest caz, indicatorul q joacă același rol ca și indicatorul din blocnotes, rulează peste întregul stivă până când devine NULL ( în timp ce (q! = NULL)), cu alte cuvinte, până la sfârșitul stivei.
Pentru o mai bună înțelegere a ștergerii unui element, să facem o analogie cu teancul deja familiar de cărți. Dacă trebuie să scoatem cartea de sus, o scoatem, iar cartea de sub ea devine partea de sus. La fel este și aici, doar la început trebuie să stabilim că următorul element va deveni vârf. * sus = q-> următorul;și abia apoi îndepărtați elementul liber (q);
Dacă cartea care urmează să fie scoasă se află între două cărți sau între o carte și o masă, cartea anterioară se va întinde pe următoarea sau pe masă. După cum am înțeles deja, cartea noastră este o celulă, iar tabelul este NULL, adică nu există niciun element următor. Se dovedește la fel ca și în cazul cărților, indicăm că celula anterioară va fi legată de următoarea prev-> next = q-> next;, Este demn de remarcat faptul că prev-> următorul poate fi egal atât cu o celulă, cât și cu zero, dacă q-> următorul = NULL, adică nu există nicio celulă (cartea va sta pe masă), după aceea ștergem celula gratuit (q).
De asemenea, este de remarcat faptul că, dacă nu realizați această conexiune, secțiunea de celule care se află după celula ștearsă va deveni inaccesibilă, deoarece chiar conexiunea care conectează o celulă la alta se va pierde și această secțiune se va pierde pur și simplu în memorie.
Funcția de afișare a datelor stiva
Cea mai simplă funcție:
cod C++
void s_print (comp * top) (// duce un indicator spre partea de sus a stivei comp * q = top; // setează q în partea de sus în timp ce (q) (// în timp ce q nu este gol (în timp ce (q) este echivalent cu while (q! = NULL )) printf_s ("% i", q-> Data); // afișează datele celulei stivei q = q-> next; // după ce am afișat, mutam q la următorul element (celulă)))
Aici cred că totul este clar, vreau doar să spun că q trebuie perceput ca un glisor, trece prin toate celulele de sus, unde l-am instalat la început: * q = sus;, până la ultimul articol.
Functie principala
Ei bine, am notat principalele funcții pentru lucrul cu stiva, le numim.
Sa vedem codul:
cod C++
void main () (comp * top = NULL; // la începutul programului nu avem coadă, deci nu există vârf, îi dăm o valoare NULL // Apoi începem să adăugăm numere de la 1 la 5 la stiva noastră s_push (& top, 1); s_push (& top, 2); s_push (& top, 3); s_push (& top, 4); s_push (& top, 5); // după executarea funcțiilor pe stivă , vom avea 54321 s_print (sus); // print s_delete_key (& top, 4); // Apoi ștergem 4, stiva primește 5321 printf_s ("\ n"); // se transferă la o nouă linie s_print (sus ); // sistem de tipărire („pauză”); // pauză)
Să revenim la motivul pentru care am trecut în funcție un pointer către un vârf de vârf. Cert este că dacă am introduce în funcție doar un pointer către vârf, atunci „Stiva” ar fi creată și schimbată doar în cadrul funcției, în funcția principală vârful ar fi și NULL. Trecând un pointer către un indicator, schimbăm partea de sus * de sus în funcția principală. Se pare că, dacă funcția schimbă stiva, trebuie să transferați vârful la acesta ca un pointer către un pointer, așa cum am avut în funcția s_push, s_delete_key. În funcția s_print, „stiva” nu ar trebui să se schimbe, așa că trecem doar un indicator în partea de sus.
În loc de cifrele 1,2,3,4,5, puteți utiliza și variabile de tip int.
Concluzie
Cod program complet:
cod C++
#include
Rezultatul executiei
Deoarece articolele sunt împinse constant în partea de sus a stivei, articolele vor fi afișate în ordine inversă
În concluzie, aș dori să vă mulțumesc pentru timpul dedicat articolului meu, sper cu adevărat că acest material i-a ajutat pe unii programatori începători să înțeleagă ce este o „stivă”, cum să o folosească, iar pe viitor nu vor avea mai orice probleme. Scrie în comentarii părerea ta, precum și cum îmi pot îmbunătăți articolele în viitor. Vă mulțumim pentru atenție.
Etichete: Stivă, stivă C, implementare stivă, stivă pe matrice, stivă în creștere dinamică, stivă pe un disc conectat individual
Grămadă
C tech este probabil cea mai simplă structură de date pe care o vom învăța și pe care o vom folosi în mod constant. O stivă este o structură de date în care elementele susțin principiul LIFO („Last in - first out”): last in, first out. Sau primul care intră - ultimul care iese.
Stiva vă permite să stocați articole și, de obicei, acceptă două operațiuni de bază:
- APĂSAȚI- pune articolul în partea de sus a stivei
- POP- scoate un element din partea de sus a stivei, mutând partea de sus la următorul element
De asemenea, este obișnuit ca o operațiune PEEK să obțină un articol în partea de sus a stivei, dar să nu îl scoată de acolo.
Stiva este una dintre structurile de date de bază și este utilizată nu numai în programare, ci și în circuite, și pur și simplu în producție, pentru implementarea proceselor tehnologice etc.; stiva este folosită ca structură de date auxiliară în mulți algoritmi și alte structuri mai complexe.
De exemplu, să presupunem că avem un teanc de numere. Să rulăm câteva comenzi. Inițial, stiva este goală. Partea de sus a stivei este un pointer către primul element, nu indică nicăieri. În cazul lui c, acesta poate fi NULL.
Stiva constă acum dintr-un element, numărul 3. Partea de sus a stivei indică numărul 3.
Stiva este formată din două elemente, 5 și 3, cu vârful stivei îndreptată către 5.
Stiva este formată din trei elemente, partea de sus a stivei indicând 7.
Va returna valoarea 7, 5 și 3 vor rămâne pe stivă. Vârful va indica următorul element - 5.
Va returna 5, va rămâne doar un element pe stivă, 3, care va fi indicat de partea de sus a stivei.
Se va întoarce 3, stiva va fi goală.
Un teanc este adesea comparat cu un teanc de farfurii. Pentru a obține următoarea farfurie, trebuie să le îndepărtați pe cele anterioare. Partea de sus a stivei este partea de sus a stivei de farfurii.
Când lucrăm cu stiva, sunt posibile două greșeli principale și comune:
- 1. Stack Underflow: Încercarea de a scoate un articol dintr-o stivă goală
- 2. Stack Overflow: Încercarea de a pune un nou articol pe o stivă care nu mai poate crește (de exemplu, RAM insuficientă)
Implementare software
Luați în considerare trei implementări simple de stivă:
Stivă de dimensiune fixă construită pe o matrice
O caracteristică distinctivă este simplitatea implementării și viteza maximă de execuție. O astfel de stivă poate fi folosită atunci când dimensiunea sa maximă este cunoscută dinainte sau se știe că este mică.
Mai întâi, determinăm dimensiunea maximă a matricei și tipul de date care vor fi stocate în ea:
#define STACK_MAX_SIZE 20 typedef int T;
Acum structura în sine
Typedef struct Stack_tag (T date; size_t size;) Stack_t;
Aici dimensiunea variabilă este numărul de elemente și, în același timp, indicatorul către partea de sus a stivei. Vârful va indica următorul element al matricei, în care va fi introdusă valoarea.
Punem un articol nou pe stivă.
Void push (Stack_t * stivă, valoare const T) (stivă-> date = valoare; stivă-> dimensiune ++;)
Singura problemă este că puteți ieși în afara matricei. Prin urmare, ar trebui să verificați întotdeauna că nu există nicio eroare de depășire a stivei:
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 void push (Stack_t * stivă, valoare const T) (dacă (stivă-> dimensiune> = STACK_MAX_SIZE) (ieșire (STACK_OVERFLOW);) stivă-> date = valoare; stivă-> dimensiune ++ ;)
În mod similar, definim o operație Pop care returnează un element de sus și trece la următorul
T pop (Stack_t * stivă) (dacă (stivă-> dimensiune == 0) (ieșire (STACK_UNDERFLOW);) stivă-> dimensiune--; returnează stivă-> date;)
Și o funcție peek care returnează elementul curent din partea de sus
T peek (const Stack_t * stivă) (dacă (stiva-> dimensiune<= 0) { exit(STACK_UNDERFLOW); } return stack->date; )
O altă notă importantă - nu avem o funcție pentru crearea unei stive, așa că trebuie să resetați manual valoarea dimensiunii
Funcții de ajutor pentru imprimarea articolelor stive
Void printStackValue (valoare const T) (printf ("% d", valoare);) void printStack (const Stack_t * stivă, void (* printStackValue) (const T)) (int i; int len = stivă-> dimensiune - 1 ; printf ("stiva% d>", stiva-> dimensiune); pentru (i = 0; i< len; i++) { printStackValue(stack->date [i]); printf ("|"); ) if (stiva-> dimensiune! = 0) (printStackValue (stiva-> date [i]);) printf ("\ n"); )
Rețineți că folosim int în funcția de imprimare, nu size_t, deoarece len poate deveni negativ. Funcția tipărește mai întâi dimensiunea stivei, apoi conținutul acestuia, separând elementele cu |
Examinare
Stack_t stack; stivă.dimensiune = 0; împingeți (& stiva, 3); printStack (& stiva, printStackValue); împingeți (& stiva, 5); printStack (& stiva, printStackValue); împingeți (& stiva, 7); printStack (& stiva, printStackValue); printf ("% d \ n", pop (& stiva)); printStack (& stiva, printStackValue); printf ("% d \ n", pop (& stiva)); printStack (& stiva, printStackValue); printf ("% d \ n", pop (& stiva)); printStack (& stiva, printStackValue); _getch ();
Luați în considerare și situațiile în care există erori de utilizare. Underflow
Void main () (Stack_t stack; stack.size = 0; push (& stack, 3); pop (& stack); pop (& stack); _getch ();)
Void main () (Stack_t stack; size_t i; stack.size = 0; for (i = 0; i< 100; i++) { push(&stack, i); } _getch(); }
Stivă în creștere dinamică pe matrice
Stiva în creștere dinamică este utilizată atunci când numărul de elemente poate fi semnificativ și nu este cunoscut în momentul rezolvării problemei. Dimensiunea maximă a stivei poate fi limitată de un anumit număr sau de dimensiunea memoriei RAM.
Stiva va consta dintr-un pointer către date, dimensiunea matricei (maximum) și numărul de elemente din matrice. Acest număr va indica și partea de sus.
Typedef struct Stack_tag (T * date; size_t size; size_t top;) Stack_t;
Pentru început, aveți nevoie de o dimensiune inițială a matricei, să fie egală cu 10
#define INIT_SIZE 10
Algoritmul de lucru este următorul: verificăm dacă valoarea topului a depășit valoarea mărimii. Dacă valoarea este depășită, atunci creștem dimensiunea matricei. Există mai multe opțiuni pentru a crește matricea. Puteți adăuga un număr, puteți înmulți cu o anumită valoare. Care dintre opțiuni este mai bună depinde de specificul sarcinii. În cazul nostru, vom înmulți mărimea cu numărul MULTIPLICATOR
#define MULTIPLICATOR 2
Nu vom seta dimensiunea maximă. Programul se va bloca la depășirea stivei sau la depășirea stivei. Vom implementa aceeași interfață (pop, push, peek). În plus, deoarece matricea este dinamică, vom realiza câteva funcții de ajutor pentru a crea stiva, a o elimina și a o curăța.
În primul rând, funcțiile pentru crearea și eliminarea stivei și câteva erori
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 Stack_t * createStack () (Stack_t * out = NULL; out = malloc (sizeof (Stack_t)); if (out == NULL) (exit (MORYOUT)_OF)__ out-> size = INIT_SIZE; out-> data = malloc (out-> size * sizeof (T)); if (out-> data == NULL) (liber (out); exit (OUT_OF_MEMORY);) out-> top = 0; return out;) void deleteStack (Stack_t ** stivă) (liber ((* stivă) -> date); liber (* stivă); * stivă = NULL;)
Totul este extrem de simplu și direct, nu există trucuri murdare. Creăm o stivă cu o lungime inițială și valorile zero.
Acum să scriem o funcție de ajutor de redimensionare.
Void redimensionare (Stack_t * stivă) (stivă-> dimensiune * = MULTIPLICATOR; stivă-> date = realloc (stivă-> date, stivă-> dimensiune * dimensiunea (T)); if (stivă-> date == NULL) ( ieșire (STACK_OVERFLOW);))
Aici, rețineți, în cazul în care nu a putut fi alocată suficientă memorie, se va ieși cu STACK_OVERFLOW.
Funcția push verifică dacă ne aflăm în afara matricei. Dacă da, atunci măriți-i dimensiunea.
Void push (Stack_t * stivă, valoare T) (dacă (stivă-> sus> = stivă-> dimensiune) (redimensionare (stivă);) stivă-> date = valoare; stivă-> sus ++;)
Funcțiile pop și peek sunt similare cu cele utilizate pentru o matrice de dimensiune fixă.
T pop (Stack_t * stivă) (dacă (stivă-> sus == 0) (ieșire (STACK_UNDERFLOW);) stivă-> sus--; returnează stivă-> date;) T peek (const Stack_t * stivă) (dacă ( stivă-> sus<= 0) { exit(STACK_UNDERFLOW); } return stack->date; )
Verifica
Void main () (int i; Stack_t * s = createStack (); for (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(); }
Să scriem o altă funcție, implode, care micșorează matricea la o dimensiune egală cu numărul de elemente din matrice. Poate fi folosit atunci când se știe deja că nu se vor mai introduce elemente și memoria poate fi eliberată parțial.
Void implode (Stack_t * stivă) (stivă-> dimensiune = stivă-> sus; stivă-> date = realloc (stivă-> date, stivă-> dimensiune * dimensiunea (T));)
Putem folosi în cazul nostru
Pentru (i = 0; i< 300; i++) { push(s, i); } implode(s); for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); }
Această implementare single-threaded a stivei folosește puține accesări la memorie, este destul de simplă și versatilă, funcționează rapid și poate fi implementată, dacă este necesar, în câteva minute. Este întotdeauna utilizat în continuare, cu excepția cazului în care se indică altfel.
Are un dezavantaj legat de metoda de crestere a memoriei consumate. La înmulțirea cu 2 (în cazul nostru), sunt necesare puține accesări la memorie, dar fiecare creștere ulterioară poate duce la o eroare, mai ales cu o cantitate mică de memorie în sistem. Dacă utilizați un mod mai blând de a aloca memorie (de exemplu, adăugați 10 de fiecare dată), atunci numărul de apeluri va crește și viteza va scădea. Astăzi, de obicei, nu există probleme cu dimensiunea memoriei, iar managerii de memorie și colectorii de gunoi (care nu sunt în C) sunt rapidi, așa că prevalează schimbarea agresivă (de exemplu, de exemplu, implementarea întregii biblioteci standard a limbajului Java) .
Implementarea unei stive pe o listă conectată individual
Ce este o listă individual legată,. Pe scurt: o listă cu legături unice constă din noduri, fiecare dintre acestea conținând informații utile și un link către următorul nod. Ultimul nod se referă la NULL.
Nu vom avea marimi maxime si minime (desi in cazul general poate fi). Fiecare element nou este creat din nou. Mai întâi, să definim structura nodului
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 typedef int T; typedef struct Node_tag (valoarea T; struct Node_tag * next;) Node_t;
Funcția de inserare a primului element este simplă: creăm un nou nod. Aruncăm următorul pointer către nodul vechi. Apoi, indicatorul spre partea de sus a stivei este transferat la nodul nou creat. Partea de sus a stivei indică acum noul nod.
Void push (Node_t ** cap, valoare T) (Node_t * tmp = malloc (dimensiunea (Node_t)); if (tmp == NULL) (ieșire (STACK_OVERFLOW);) tmp-> next = * cap; tmp-> valoare = valoare; * cap = tmp;)
Funcția pop preia primul element (cel indicat de sus), sare indicatorul la următorul element și returnează primul. Există două opțiuni aici - puteți returna un nod sau o valoare. Dacă returnăm valoarea, atunci va trebui să ștergem nodul din interiorul funcției
Node_t * pop1 (Node_t ** cap) (Node_t * out; if ((* head) == NULL) (ieșire (STACK_UNDERFLOW);) out = * head; * head = (* head) -> next; return out; )
T pop2 (Node_t ** cap) (Node_t * out; valoare T; if (* head == NULL) (ieșire (STACK_UNDERFLOW);) out = * head; * head = (* head) -> next; value = out -> valoare; liber (out); valoare returnată;)
Acum, în loc să verifici lungimea unui tablou, verificarea NULL din partea de sus a stivei este folosită peste tot.
Funcție simplă de observare
T peek (const Node_t * head) (dacă (head == NULL) (ieșire (STACK_UNDERFLOW);) return head-> value;)
Iterația este destul de interesantă. Doar trecem de la un nod la altul până ajungem la capăt.
Void printStack (const Node_t * head) (printf ("stiva>"); while (head) (printf ("% d", head-> value); head = head-> next;))
Și încă o problemă - acum nu poți să te uiți doar la dimensiunea stivei. Trebuie să mergi de la început până la sfârșit și să numeri toate elementele. De exemplu, așa
Size_t getSize (const Node_t * head) (size_t size = 0; while (head) (size ++; head = head-> next;) return size;)
Desigur, puteți stoca dimensiunea separat, puteți împacheta stiva cu toate datele într-o singură structură etc. Să luăm în considerare toate acestea când examinăm listele mai detaliat.
ultimul intrat - primul iesit, "ultimul intrat - primul iesit").Cel mai adesea, principiul de funcționare al unui teanc este comparat cu un teanc de farfurii: pentru a o lua pe a doua de sus, trebuie să o scoateți pe cea de sus.
În unele limbi (de exemplu Lisp, Python) orice listă poate fi numită stivă, deoarece operațiunile pop și push sunt disponibile pentru ele. În C++, biblioteca standard are o clasă cu o structură și metode implementate. etc.
YouTube colegial
1 / 3
Informatica. Structuri de date: Stivă. Centrul de învățare online Foxford
#9. Stivă / 1. Asamblator și proceduri / Programare de la zero
Bazele rețelelor de transmisie a datelor. Model OSI și stivă de protocole TCP IP. Elementele de bază ale Ethernetului.
Subtitrări
Stiva de software
Organizarea în memorie
Adesea, stiva este implementată ca o listă unidirecțională (fiecare articol din listă conține, pe lângă informațiile stocate în stivă, un pointer către următorul articol din stivă).
Dar, de asemenea, adesea stiva este situată într-o matrice unidimensională cu adrese ordonate. O astfel de organizare a stivei este convenabilă dacă un element de informație ocupă un număr fix de cuvinte în memorie, de exemplu, 1 cuvânt. Acest lucru elimină necesitatea de a stoca un pointer explicit către următorul element de stivă din elementul de stivă, ceea ce economisește memorie. În acest caz, indicatorul de stivă ( Stack Pointer, - SP) este de obicei un registru de procesor și indică adresa capului stivei.
Să presupunem, de exemplu, că capul stivei este situat la o adresă inferioară, următoarele elemente sunt situate la adrese în creștere. De fiecare dată când un cuvânt este împins în stivă, SP este mai întâi decrementat cu 1 și apoi se face o scriere în memorie la adresa de la SP. De fiecare dată când un cuvânt este scos din stivă (popped), acesta citește mai întâi adresa curentă de la SP și apoi crește conținutul SP cu 1.
Atunci când se organizează o stivă sub forma unei liste unidirecționale, valoarea variabilei stivei este un indicator către partea de sus - adresa vârfului. Dacă stiva este goală, atunci valoarea indicatorului este NULL.
Un exemplu de implementare a stivei în C:
struct stack (char * data; struct stack * next;);
Operațiuni de stivă
Sunt posibile trei operațiuni de stivă: adăugarea unui element (altfel împingere), eliminarea unui articol (pop) și citirea elementului principal (peek).
O apăsare adaugă un nou element indicând elementul care a fost anterior capul. Noul element devine acum cel principal.
Când un element este șters (pop), primul este eliminat, iar capul devine cel la care acest obiect avea un pointer (următorul element). În acest caz, valoarea elementului eliminat este returnată.
void push (STACK * ps, int x) // Adăugați un articol nou în stivă(dacă (ps -> dimensiune == STACKSIZE) // Stiva este debordată?(fputs ("Eroare: overflow stivă \ n", stderr); abort ();) else (ps -> elemente [ps -> dimensiune ++] = x;)) int pop (STACK * ps) // Scoateți din stivă(dacă (ps -> dimensiune == 0) // Stiva este goală?(fputs ("Eroare: stack underflow \ n", stderr); abort ();) else (return ps -> items [- ps -> size];))
Zona de aplicare
O vizualizare programatică a stivei este utilizată pentru a parcurge structuri de date, cum ar fi un arbore sau un grafic. Când folosiți funcții recursive, va fi folosit și stiva, dar aspectul său hardware. Pe lângă aceste sarcini, stiva este folosită pentru organizare
Procese similare apar cu o întrerupere hardware (procesorul X86 salvează automat registrul de steaguri pe stivă în timpul unei întreruperi hardware). În plus, compilatorii alocă variabilele procedurii locale pe stivă (dacă procesorul oferă acces la o locație arbitrară a stivei).
Înainte de a utiliza stiva, aceasta trebuie inițializată astfel încât registrele SS: ESP să indice adresa șefului stivei din zona RAM fizică, iar numărul necesar de celule de memorie trebuie rezervat pentru stocarea datelor în stivă (evident, nu poate exista o stivă în ROM organizată). Programele de aplicație, de regulă, primesc o stivă gata de utilizare de la sistemul de operare. În modul protejat al procesorului, segmentul de stare a sarcinii conține patru selectori de segment de stivă (pentru niveluri de privilegii diferite), dar este utilizat doar o stivă la un moment dat.
