Stivele sunt un tip de adaptoare de containere cu tip de lucru LIFO (Last In First Out), unde un element nou este adăugat la un capăt (sus) și un element este îndepărtat numai de la acel capăt. Stack folosește un obiect încapsulat al fiecăreia vector sau deque (implicit) sau listă (clasa de container secvențială) ca container subiacent, oferind un set specific de funcții membre pentru a accesa elementele sale.
sara ali khan varsta
Dacă există confuzie în amintirea diferenței de bază dintre stivă și coadă, atunci avem doar un exemplu de viață real pentru această diferențiere, pentru stivă, stivuire de cărți putem lua cu ușurință cartea de sus și pentru coadă amintiți-vă când trebuie să stați la coadă. de ATM pentru scoaterea numerarului, apoi prima persoană din apropierea ATM-ului are prima șansă să scoată banii de la ATM. Deci, coada funcționează de tipul FIFO (First In First Out).
Sintaxa stivei:-
Pentru a crea o stivă, trebuie să includem fișierul antet în codul nostru. Apoi folosim această sintaxă pentru a defini std::stack:
| șablon |
Tip – este Tipul de element conținut în std::stack. Poate fi orice tip C++ valid sau chiar un tip definit de utilizator.
Container – este tipul obiectului container subiacent.
Tipuri de membri: -
value_type- Primul parametru șablon, T. Denotă tipurile de elemente.
container_type- Al doilea parametru de șablon, Container. Acesta denotă tipul de container subiacent.
size_type- tip integral nesemnat.
Funcțiile asociate cu stiva sunt:
empty() – Returnează dacă stiva este goală – Complexitatea timpului: O(1)
size() – Returnează dimensiunea stivei – Complexitatea timpului: O(1)
top() – Returnează o referință la elementul cel mai de sus al stivei – Complexitatea timpului: O(1)
push(g) – Adaugă elementul „g” în partea de sus a stivei – Complexitatea timpului: O(1)
pop() – Șterge cel mai recent element introdus din stivă – Complexitatea timpului: O(1)
C++
#include> #include> using> namespace> std;> int> main() {> >stack<>int>>stivă;> >stack.push(21);>// The values pushed in the stack should be of the same data which is written during declaration of stack> >stack.push(22);> >stack.push(24);> >stack.push(25);> >int> num=0;> >stack.push(num);> >stack.pop();> >stack.pop();> >stack.pop();> > >while> (!stack.empty()) {> >cout << stack.top() <<>' '>;> >stack.pop();> >}> }> |
>
>Ieșire
22 21>
Complexitatea timpului: Complexitatea de timp a acestui program este O(N), unde N este numărul total de elemente din stiva. Bucla while repetă de N ori, scotând elemente din stivă și imprimându-le.
Complexitatea spațiului: Complexitatea spațială a acestui program este O(N), unde N este numărul total de elemente din stiva. Structura de date a stivei folosește spațiu proporțional cu numărul de elemente stocate în ea. În acest caz, dimensiunea maximă a stivei este 5, deci complexitatea spațiului este constantă și poate fi considerată și ca O(1).
primul laptop
Explicația codului:
- Includeți fișierul antet iostream sau în codul nostru pentru a utiliza funcțiile acestuia.
- Includeți fișierul antet stivei în codul nostru pentru a-și folosi funcțiile dacă este deja inclus, atunci nu este nevoie de fișierul antet stivei, deoarece are deja o funcție încorporată în el.
- Includeți spațiul de nume std în codul nostru pentru a-i folosi clasele fără a-l apela.
- Apelați funcția main(). Logica programului ar trebui adăugată în această funcție.
- Creați o stivă pentru a stoca valori întregi.
- Utilizați funcția push() pentru a introduce valoarea 21 în stivă.
- Utilizați funcția push() pentru a introduce valoarea 22 în stivă.
- Utilizați funcția push() pentru a introduce valoarea 24 în stivă.
- Utilizați funcția push() pentru a introduce valoarea 25 în stivă.
- Utilizați o variabilă întreagă num pentru a introduce o valoare variabilă. Aici valoarea sa este 0, dar putem atribui orice valoare întreagă folosind cin>> num.
- Utilizați funcția push() pentru a introduce valoarea variabilei num.
- Utilizați funcția pop() pentru a elimina elementul de sus din stivă, adică 25. Elementul de sus devine acum 24.
- Utilizați funcția pop() pentru a elimina elementul de sus din stivă, adică 24. Elementul de sus devine acum 22.
- Utilizați o buclă while și funcția empty() pentru a verifica dacă stiva NU este goală. Cel! este operatorul NOT. Deci, când stiva nu este goală, atunci funcția empty() va returna false și operatorul NOT o va converti în adevărat, iar bucla while continuă să ruleze. Dar, când stiva devine goală, atunci funcția empty() va returna true și operatorul NOT o va face falsă și bucla se va termina.
- Imprimarea conținutului curent al stivei pe consolă.
- Apelați funcția pop() din stivă.
- Sfârșitul corpului buclei while.
- Sfârșitul corpului funcției main().
Lista de funcții ale stivei:
- stack::top() în C++ STL
- stack::empty() și stack::size() în C++ STL
- stack::push() și stack::pop() în C++ STL
- stack::swap() în C++ STL
- stack::emplace() în C++ STL
- Articole recente despre C++ Stack