Tipuri particulare de liste în funcție de modul de acces (stivă, coadă)
Aceleași elemente pot ieși în ordine diferită. Comparăm stiva LIFO cu o coadă FIFO și alegem regula potrivită situației.
Distribuie
Trimite pe…
Anulare în editor sau coadă la cantină?
Situația și ce ai de aflat
A, B, C intră în această ordine. Regula de servire depinde de situație.
A, B și C sosesc în această ordine. În ce ordine le prelucrăm pentru Undo și pentru servirea la cantină?
Legătura cu lecția: Alegem stivă sau coadă după ordinea de prelucrare cerută, nu doar după aspectul colecției.
Observă datele de pornire.
Urmărește ce se schimbă.
Verifică și explică rezultatul.
Sosesc trei acțiuni sau persoane
A, B, C intră în această ordine. Regula de servire depinde de situație.
PARTEA 1
Stiva: ultimul intrat, primul ieșit
Stiva și vârful ei
- LIFO: ultimul intrat este primul scos.
- Adaugi și elimini din același capăt, numit vârf.
Explicația pe larg
O stivă adaugă și extrage elemente la același capăt, numit vârf. Regula LIFO înseamnă Last In, First Out: ultimul intrat, primul ieșit. Analogia din manual este teancul de farfurii sau de lucrări. Dacă punem A, apoi B, apoi C, primul element extras este C.
De ce este potrivită pentru anulare?
- Ultima acțiune se anulează prima.
- Păstrează istoricul în ordinea efectuării acțiunilor.
Ordine inversă
Ce a fost adăugat recent este disponibil imediat la vârf.
Acces restricționat
O stivă nu oferă, ca operație a modelului său, extragerea arbitrară din mijloc.
Alegere motivată
Este potrivită când problema cere întoarcerea peste pașii recenți, nu când trebuie respectată sosirea.
Dacă A a fost pus primul, poate ieși primul din stiva A,B,C?
Nu prin operațiile obișnuite ale stivei. Trebuie extrase mai întâi C și B.
Explicația pe larg
Când anulăm succesiv modificări, refacem pașii în ordine inversă realizării lor. Dacă am scris un titlu, am schimbat fontul și apoi culoarea, anularea cea mai recentă se referă la culoare. Într-un model simplu de Undo, stiva păstrează acțiunile necesare revenirii. Aplicațiile reale pot avea mecanisme suplimentare, dar regula de bază rămâne recognoscibilă.
Anticipează LIFO
Adaugi A, B, C într-o stivă. Ce extragi întâi?
Alege un răspuns.
Inserarea și extragerea unei stive se fac:
Alege un răspuns.
Observă · urmărește · încearcă
Aceleași sosiri, alte ieșiri
Compară o stivă și o coadă în care sosesc A, B, C.
Un singur element este și primul, și ultimul.
Datele sunt aceleași, regula extragerii diferă.
Stiva extrage ultimul intrat. Coada extrage primul intrat.
Aici rezultatele coincid întâmplător; regulile nu devin identice.
Privește → anticipează → explică. Acoperă exemplul, spune ce se întâmplă și descoperă-l pentru verificare. Apoi folosește demonstrația de mai jos pentru a urmări schimbările.
Vezi cum se întâmplă
Alege un pas sau pornește demonstrația. Te poți opri oricând pentru explicații.
Adăugăm A
Un singur element este și primul, și ultimul.
Acum anticipează tu
După adăugarea A, B, C, ce ordine completă produce stiva?
Alege, apoi citește explicația.
La tablă: oprește înaintea unui pas, cere o predicție și discută ce s-a schimbat și ce a rămas la fel.
PARTEA 2
Coada: primul intrat, primul ieșit
Coada are față și spate
- FIFO: primul intrat este primul scos.
- Adaugi la spate și extragi din față.
Explicația pe larg
O coadă adaugă la spate și extrage din față. Regula FIFO înseamnă First In, First Out: primul intrat, primul ieșit. Pentru sosirea A, B, C, extragerile sunt A, apoi B, apoi C. Analogia din manual este rândul la ghișeu sau prelucrarea cererilor în ordinea primirii.
Aceleași date, altă regulă
| Criteriu | Stivă | Coadă |
|---|---|---|
| Inserare | la vârf | la spate |
| Extragere | de la vârf | din față |
| Pentru A,B,C | C,B,A | A,B,C |
| Regulă | LIFO | FIFO |
- Aceleași intrări pot produce ordini de ieșire diferite.
- Stivă: farfurii; coadă: persoane la ghișeu.
Este coada întotdeauna cea mai bună pentru cereri?
Este potrivită când toate trebuie tratate în ordinea sosirii. Dacă există urgențe definite explicit, cerința poate impune priorități. Alegerea se justifică prin regulile problemei, nu printr-o preferință universală.
Explicația pe larg
O listă generală poate fi folosită pentru implementare, dar simpla stocare a datelor nu este suficientă: trebuie respectate operațiile și restricțiile modelului. O implementare care scoate orice element ales nu se mai comportă ca o stivă sau o coadă simplă. La programare, contează și eficiența operațiilor concrete ale structurii folosite.
Compară ordinea extragerii
Scrie până la zece etichete simple în ordinea adăugării. Simulatorul arată, pentru aceleași date, ordinea ieșirii din stivă și din coadă.
Simulator pentru exemplul acestei lecții; nu execută cod Python arbitrar. Datele rămân în această pagină.
Alege și justifică
Cererile se rezolvă în ordinea sosirii. Ce model alegi?
Alege un răspuns.
O coadă simplă prioritizează automat ultimul venit?
Alege un răspuns.
Execută și urmărește programul
Schimbă valorile, pregătește execuția și avansează câte o instrucțiune. Linia evidențiată este cea tocmai executată; variabilele și ieșirea arată starea de după acel pas.
Pregătește datele pentru execuție.
Program Python
sosiri = input().split()2stiva = sosiri.copy()3coada = sosiri.copy()4ultimul = stiva.pop()5primul = coada.pop(0)6print(ultimul, primul)Variabile după pas
| Nume | Valoare | Tip |
|---|---|---|
| Nicio atribuire încă. | ||
Ieșire
Nicio afișare încă.
Listă Python folosită didactic pentru a compara regulile. pop(0) nu este implementarea eficientă a unei cozi mari.
Atelierul reproduce execuția programului afișat, pentru datele acceptate de câmpuri. Nu execută cod Python introdus liber și nu accesează fișierele dispozitivului. Poți copia programul într-un mediu Python pentru a compara rezultatele.
Pune blocurile de cod în ordine
Citește cel puțin o etichetă. Fă o copie pentru stivă și una pentru coadă; extrage ultimul sosit, apoi primul sosit și afișează ambele etichete.
Alege blocurile în ordinea dorită. În soluție, folosește săgețile pentru a le muta. Blocurile nu se modifică în timpul jocului.
Blocuri de ales
Soluția ta
Alege primul bloc din zona de alături.
Începe prin alegerea datelor sau a scopului.
Compară cu modelul
sosiri = input().split()
stiva = sosiri.copy()
coada = sosiri.copy()
ultimul = stiva.pop()
primul = coada.pop(0)
print(ultimul, primul)Datele și inițializările trebuie pregătite înaintea prelucrării; afișarea folosește rezultatele calculate. Blocurile indentate rămân împreună. Comparăm cu programul-model; alte soluții pot fi corecte.
Teme / Exerciții
1 · Urmărește stiva
Adaugă 4,7,2, extrage o dată, adaugă 9 și extrage de două ori. Scrie elementele extrase.
Indiciu / verificare
Sunt extrase 2, apoi 9, apoi 7. La final rămâne 4.
2 · Urmărește coada
Aplică aceeași succesiune de operații unei cozi. Compară rezultatele.
Indiciu / verificare
Sunt extrase 4, apoi 7, apoi 2. La final rămâne 9.
3 · Model real
Alege o situație potrivită pentru LIFO și una pentru FIFO. Precizează locul inserării, al extragerii și motivul alegerii.
Indiciu / verificare
Undo poate ilustra LIFO; cereri tratate în ordinea primirii ilustrează FIFO. Menționează ipotezele, de exemplu absența priorităților.
Alege nivelul de antrenament
Basic consolidează ideea, Mediu combină pașii, iar Avansat cere justificări și cazuri-limită. Profesorul poate selecta sarcinile; nu este necesar să rezolvi toate nivelurile într-o singură temă. Exercițiile de mai sus sunt păstrate; acestea sunt propuneri originale suplimentare.
Basic
1 · Stivă
Desenează adăugarea A, B, C și prima extragere din stivă.
Reper de verificare
Iese C.
2 · Coadă
Desenează aceeași sosire și prima extragere FIFO.
Reper de verificare
Iese A.
Mediu
1 · Operații amestecate
În stivă: adaugă A, adaugă B, extrage, adaugă C, extrage. Notează ieșirile.
Reper de verificare
B, C; rămâne A.
2 · Coada de cereri
În coadă: adaugă A, B, extrage, adaugă C, extrage.
Reper de verificare
A, B; rămâne C.
Avansat
1 · Anulare și refacere
Proiectează conceptual Undo/Redo folosind două stive.
Reper de verificare
O acțiune nouă după Undo cere o regulă pentru istoricul Redo.
2 · Structură vidă
Descrie ce trebuie verificat înaintea extragerii și cum comunici lipsa elementelor.
Reper de verificare
Nu inventa o valoare extrasă dintr-o structură vidă.
Pentru predare: trimite codul sau pașii soluției, minimum două teste și o explicație a rezultatului. Pentru probleme conceptuale, predă schema și justificarea.
Privește, oprește și explică
Tutoriale video din manualele digitale CD PRESS. Alege manualul specializării tale. Videoclipul se încarcă la cerere, de la sursa originală. Explicațiile scrise și exemplele lecției permit și studiul fără sunet.
▶ Matematică-informatică · Modele conceptuale de organizare a datelor. Lista, stiva și coada
Ce să urmărești: Urmărește ordinea inserării și extragerii. Anticipează ce element iese primul dintr-o stivă și dintr-o coadă.
© Editura CD PRESS · Manualul digital Matematică-informatică. Dacă playerul nu funcționează, deschide manualul și alege „Activități digitale animate” → „Modele conceptuale de organizare a datelor. Lista, stiva și coada”.
Reține și explică
- Stiva folosește un singur capăt și regula LIFO.
- Coada folosește capete opuse și regula FIFO.
- Aceleași date pot produce ordini diferite de extragere.
- Modelul se alege în funcție de cerință.
Repere pentru profesor
Lecție MI, pp. 72–76; nu este inclusă ca lecție distinctă în parcursul SN furnizat. Se prezintă conceptual înaintea implementărilor. Distinge modelul de structura folosită pentru implementare și evită afirmații absolute despre sisteme reale cu priorități.
Continuă parcursul
Matematică-informatică