...
Structuri de date

Structuri de date: tipuri, exemple și când folosești fiecare

Pe scurt

O structură de date este felul în care organizezi datele în memorie ca să le poți folosi eficient. Cele mai importante sunt tabloul (lista), lista înlănțuită, stiva, coada, hash map-ul (dicționarul), arborele, heap-ul și graful. Fiecare face rapid anumite operații și încet altele: un hash map găsește o cheie dintr-un singur salt, o stivă îți dă mereu ultimul element adăugat, un arbore ține datele sortate. Mai jos le încerci pe primele trei și vezi cât costă fiecare operație.

  • 8structuri de date explicate
  • O(1)căutarea într-un hash map
  • 3demonstrații interactive
  • 2lecții gratuite, fără card
STIVĂ · LIFO push(1) push(2) push(3) push(4) pop() → 4 ARBORE BINAR 8 3 10 1 6 9 14 COADĂ · FIFO 12 7 21 5 18 12 7 21 5 18 ← iese primul intră la coadă ← O(1)

Stiva, coada și hash map-ul, în acțiune

Apasă pe butoane și urmărește linia de Python de sub fiecare structură. Toate trei fac operațiile de bază în O(1).

Stiva

ultimul intrat, primul ieșit
stiva = [] Lecția despre stivă →

Coada

primul venit, primul servit
coada = deque() Lecția despre coadă →

Hash map

găsești o cheie dintr-un salt
varste = {} Lecția despre hash map →

Încearcă: paranteze valide cu o stivă

Problema clasică de interviu pentru stivă, direct din cursul de algoritmi. Scrii codul Python în editor și primești verificarea pe loc.

Exercițiu din lecția 52 · cursul de algoritmi

Paranteze valide

Scrie funcția paranteze_valide(text) care returnează True dacă parantezele din text sunt valide și False altfel, folosind o stivă. Testele sunt deja scrise.

  1. Creează dicționarul cu perechile și o listă goală stiva.
  2. Pentru o paranteză deschisă: append. Pentru una închisă: verifică vârful și fă pop.
  3. La final, returnează dacă stiva este goală. Trebuie să apară: True, False, True, False, True, False.
Indiciu: Textul gol '' este valid: bucla nu se execută, stiva rămâne goală, deci rezultatul este True.
def paranteze_valide(text):
    pereche = {')': '(', ']': '[', '}': '{'}
    stiva = []
    for c in text:
        if c in pereche:
            if not stiva or stiva[-1] != pereche[c]:
                return False
            stiva.pop()
        else:
            stiva.append(c)
    return len(stiva) == 0


print(paranteze_valide('()[]{}'))
print(paranteze_valide('([)]'))
print(paranteze_valide('{[]}'))
print(paranteze_valide('(('))
print(paranteze_valide(''))
print(paranteze_valide(')('))
Începe gratuit cursul de algoritmi →
main.pyPython
ConsolăGata de pornire
Apasă „Rulează codul”. Prima dată Python se încarcă în browser în câteva secunde.

Ce este o structură de date

O structură de date este un mod de a păstra și organiza datele într-un program, împreună cu operațiile pe care le poți face pe ele: adăugare, ștergere, căutare, parcurgere. Aceleași date pot fi ținute în mai multe feluri, iar alegerea contează enorm pentru viteză.

Exemplu: ai un milion de utilizatori și vrei să afli dacă un email există deja. Într-o listă, îi verifici pe rând, deci până la un milion de pași. Într-un set sau hash map, emailul e transformat într-un număr (hash) care îți spune direct unde să cauți, deci un singur pas. De aceea structurile de date merg mână în mână cu algoritmii: un algoritm bun pe o structură greșită rămâne lent.

Stiva și coada în Python, C++ și Java

Toate limbajele au stive și cozi gata făcute. Operațiile de bază sunt aceleași și costă O(1).

from collections import deque

stiva = []
stiva.append(1)        # push
stiva.append(2)
print(stiva.pop())     # 2: ultimul intrat iese primul

coada = deque()
coada.append(1)        # intră la coadă
coada.append(2)
print(coada.popleft()) # 1: primul venit iese primul

Cât costă fiecare operație

StructurăAcces după pozițieCăutareInserareȘtergere
Tablou / listăO(1)O(n)O(n), O(1) la finalO(n), O(1) la final
Listă înlănțuităO(n)O(n)O(1) dacă ai nodulO(1) dacă ai nodul
Stivădoar vârfulO(n)O(1)O(1)
Coadă (deque)doar capeteleO(n)O(1)O(1)
Hash map / setnu are ordineO(1) în medieO(1) în medieO(1) în medie
Arbore binar de căutare echilibratO(log n)O(log n)O(log n)O(log n)
Heapminimul în O(1)O(n)O(log n)O(log n) pentru minim

Dacă notația O(…) e nouă pentru tine, o găsești explicată pe pagina despre algoritmi și complexitate.

Cum alegi structura de date potrivită

  • Vrei să găsești repede ceva după o cheie (un email, un id, un cuvânt)? Hash map sau set.
  • Vrei elementele în ordinea în care au venit? Coadă.
  • Vrei să revii la ultimul pas (undo, paranteze, recursivitate)? Stivă.
  • Vrei mereu cel mai mic sau cel mai mare element, din date care se schimbă? Heap.
  • Vrei datele sortate tot timpul și căutări rapide? Arbore binar de căutare echilibrat.
  • Datele sunt legături între lucruri (prieteni, drumuri, dependențe)? Graf.
  • Altfel, începe cu un tablou: e simplu, rapid la parcurgere și suficient în majoritatea cazurilor.

Structurile de date în Python, Java și C++

StructurăPythonJavaC++
Tablou dinamiclistArrayListvector
Hash mapdictHashMapunordered_map
SetsetHashSetunordered_set
Stivălist (append / pop)ArrayDequestack
Coadăcollections.dequeArrayDequequeue
HeapheapqPriorityQueuepriority_queue
Arbore sortatbibliotecă externăTreeMapmap

Ideile sunt aceleași în orice limbaj; se schimbă doar numele. Odată ce le înțelegi într-unul, le recunoști imediat în celelalte.

În ce ordine înveți structurile de date

Cu câte o structură pe săptămână și exerciții zilnice, le stăpânești pe toate în aproximativ două luni.

  1. 1Tablouri și șiruri

    Parcurgeri, two pointers, sliding window.

  2. 2Hash map și set

    Cea mai folosită structură la interviuri: frecvențe, perechi, duplicate.

  3. 3Stive și cozi

    Paranteze valide, stiva monotonă, BFS.

  4. 4Liste înlănțuite

    Inversare, cicluri, interclasare.

  5. 5Arbori și heap

    Parcurgeri, BST, top k cu heap.

  6. 6Grafuri

    BFS, DFS, drumuri minime, sortare topologică.

4,9 din 5 · 128 de recenzii Google

Ce spun cursanții

Toate recenziile pe Google
Video · 13 minute

Absolvenții noștri, în cuvintele lor

Cursanți care au pornit de la zero povestesc cum au învățat, ce i-a ajutat și unde au ajuns după cursuri.

Vezi pe YouTube

Super usor de inteles. Cursurile de programare video onlinesunt foarte bine explicate

Fotografia lui Laura Chiriazi, cursant al Academiei ProgramatorilorLaura ChiriaziRecenzie pe Google

Recomand, lecțiile sunt explicate pe întelesul cursantului si pe langa asta practica este compusă din exerciții din care inveti sa programezi!

Fotografia lui Ioan John, cursant al Academiei ProgramatorilorIoan JohnRecenzie pe Google

Am achiziționat pachetul de 36 de ședințe individuale pentru cursul de Java, avându-l ca instructor pe Tudor. Cursul este foarte bine structurat și este plin de exemple din viața cotidiană, aspect care îl face ușor de înțeles. De asemenea, Tudor a dat dovadă de profesionalism și răbdare pe parcursul ședințelor prin faptul că explică materia până în momentul în care înțelegi. Recomand cu căldură cursurile susținute de Tudor.

Fotografia lui Alexandru, cursant al Academiei ProgramatorilorAlexandruRecenzie pe Google

Întrebări frecvente

Ce este o structură de date?

O structură de date este un mod de a organiza și păstra datele într-un program, împreună cu operațiile pe care le poți face pe ele (adăugare, ștergere, căutare, parcurgere). Exemple: tabloul, lista înlănțuită, stiva, coada, hash map-ul, arborele, heap-ul și graful.

Care sunt tipurile de structuri de date?

Se împart în structuri liniare, în care elementele stau unul după altul (tablou, listă înlănțuită, stivă, coadă), și structuri neliniare (arbori, heap-uri, grafuri). Separat există structurile bazate pe hash (hash map și set), care găsesc o cheie direct, fără parcurgere.

Care este diferența dintre stivă și coadă?

Stiva scoate mereu ultimul element adăugat (LIFO: last in, first out), ca un teanc de farfurii. Coada scoate mereu primul element adăugat (FIFO: first in, first out), ca un rând la casă. Amândouă adaugă și scot în O(1).

Ce este un hash map?

Un hash map (dicționar în Python) păstrează perechi cheie-valoare. Cheia trece printr-o funcție hash care o transformă într-un număr ce indică direct locul din memorie, așa că adăugarea și căutarea durează în medie O(1), indiferent câte elemente sunt.

Care e diferența dintre un tablou și o listă înlănțuită?

Tabloul ține elementele unul lângă altul în memorie, deci ajungi la orice poziție în O(1), dar inserarea la mijloc mută celelalte elemente. Lista înlănțuită leagă nodurile prin referințe: inserezi și ștergi ușor dacă ai nodul, dar ca să ajungi la al k-lea element treci prin toate dinainte.

Ce structuri de date trebuie să știu la interviu?

Tabloul și șirurile de caractere, hash map-ul și set-ul, stiva, coada, lista înlănțuită, arborele binar și arborele binar de căutare, heap-ul și grafurile. Hash map-ul apare cel mai des: multe probleme O(n²) devin O(n) cu el.

Structurile de date se învață înainte sau după algoritmi?

Împreună. Un algoritm lucrează mereu pe o structură de date, iar alegerea structurii decide cât de rapid e algoritmul. Ordinea bună e: un limbaj, notația Big O, tablouri, hash map, stive și cozi, apoi recursivitate, arbori și grafuri.

Unde învăț structuri de date în română?

În cursul de algoritmi pentru interviuri de la Academia Programatorilor, unde implementezi fiecare structură în Python și rezolvi probleme clasice de interviu cu ea, direct în browser, cu verificare automată. Primele 2 lecții sunt gratuite.

Începe azi, gratuit

Primele lecții din fiecare curs sunt gratuite. Fără card, fără instalări: scrii primul cod în câteva minute.