grămadă # 151; O structură de date dinamică reprezentând un set ordonat de elemente în care adăugarea de elemente noi și îndepărtarea celor existente se face dintr-un capăt, numit partea de sus a stivei.
Prin definiție, elementele sunt eliminate din stivă în ordinea inversă adăugării lor la această structură, adică, Principiul "a venit ultima dată # 151; primul a mers. "
Cel mai evident exemplu al organizării stivei este piramida copiilor, în care adăugarea și îndepărtarea inelelor se efectuează exact în conformitate cu definiția stivei.
Stiva poate fi organizată pe baza oricărei structuri de date, în cazul în care depozitarea mai multor elemente similare și care pot fi realizate prin definirea stivei: un șir liniar, tastate fișier, listă unidirecțională sau bidirecțională. În cazul nostru, cele mai potrivite pentru realizarea stivei este o listă de-un fel, și într-o stivă alege începutul listei.
Selectați operațiile tipice ale stiva și ale elementelor sale:
Implementăm aceste operații utilizând modulul dezvoltat anterior pentru listele unidirecționale (a se vedea materialul "Structuri de date dinamice: liste").
Folosind bibliotecile dezvoltate aici, vom rezolva problema.
Un exemplu. Scrieți un program care calculează ca un număr întreg valoarea exprimată (fără variabile) scrisă (fără erori) în forma postfix din fișierul text. Fiecare rând al fișierului conține exact o expresie.
Algoritmul soluției. Expresia este privită de la stânga la dreapta. Dacă numărul este găsit, valoarea sa (în ansamblu) împins pe stiva, iar dacă apare semnul de funcționare, stiva este extras din ultimele două elemente (operanzii este operațiunea), o operație pe ele, iar rezultatul său este scris în stivă. În final, numai un singur număr rămâne în stack # 151; înțelesul întregii expresii.
Testați întrebările și sarcinile- Ce structură de date se numește stivă?
- Pe baza structurilor care pot fi organizate?
- Aduceți exemple despre cum să organizați ceva pe baza stivei.
- Cu ajutorul teancului, introduceți caracterele acestei linii în ordine inversă.
Acest site a fost creat cu uCoz