Impila dentro C++ STL con esempio

Sintassi dello stack

Per creare uno stack, dobbiamo includere il file file di intestazione nel nostro codice. Usiamo quindi questa sintassi per definire std::stack:

template <class Type, class Container = deque<Type> > class stack;

• Tipologia – è il Tipo di elemento contenuto nello std::stack. Può essere qualsiasi valido C++ tipo o anche un tipo definito dall'utente.
• Contenitore – è il Tipo dell'oggetto contenitore sottostante.

Tipi di membri

Ecco i tipi di membri dello stack:

• value_type- Il primo parametro del modello, T. Denota i tipi di elemento.
• container_type: il secondo parametro del modello, Container. Indica il tipo di contenitore sottostante.
• size_type: tipo integrale senza segno.

Operazioni nello Stack

A C++ stack supporta le seguenti operazioni di base:

• push – Aggiunge/spinge un elemento nello stack.
• pop – Rimuove/estrae un elemento dallo stack.
• peek – Restituisce l'elemento in cima allo stack senza rimuoverlo.
• isFull: controlla se uno stack è pieno.
• isEmpty: controlla se uno stack è vuoto.

Implementazione dello stack

Passo 1) Inizialmente abbiamo uno stack vuoto. La parte superiore di una pila vuota è impostata su -1.

Passo 2) Successivamente, abbiamo inserito l'elemento 5 nello stack. La parte superiore della pila punterà all'elemento 5.

Passo 3) Successivamente, abbiamo inserito l'elemento 50 nello stack. La parte superiore della pila si sposta e punta all'elemento 50.

Passo 4) Abbiamo quindi eseguito un'operazione pop, rimuovendo l'elemento in cima allo stack. L'elemento 50 viene estratto dalla pila. La cima della pila ora punta all'elemento 5.

spingi() e pop()

Le funzioni stack::push() aggiungono un nuovo elemento in cima allo stack. La dimensione dello stack viene aumentata di 1 dopo l'inserimento. La funzione assume questa sintassi:

stack.push(value)

Il valore è l'elemento da inserire nello stack.

La funzione stack:: pop() rimuove l'elemento superiore dello stack. Questo è l'elemento più recente dello stack. La dimensione dello stack viene ridotta di 1 dopo la rimozione. Ecco la sintassi della funzione:

stack.pop()

La funzione non accetta parametri.

Esempio 1:

#include <iostream> 
#include <stack> 
using namespace std;
int main() {
	stack<int> st;
	st.push(10);
	st.push(20);
	st.push(30);
	st.push(40);
	
         st.pop();
	st.pop();

	while (!st.empty()) {
		cout << ' ' << st.top();
		st.pop();
	}
}

Produzione:

Ecco uno screenshot del codice:

Spiegazione del codice:

1. Includi il file di intestazione iostream nel nostro codice per utilizzare le sue funzioni.
2. Includi il file di intestazione dello stack nel nostro codice per utilizzare le sue funzioni.
3. Includi lo spazio dei nomi std nel nostro codice per utilizzare le sue classi senza chiamarlo.
4. Chiama la funzione main(). La logica del programma dovrebbe essere aggiunta all'interno di questa funzione.
5. Crea uno stack st per memorizzare valori interi.
6. Utilizzare la funzione push() per inserire il valore 10 nello stack.
7. Utilizzare la funzione push() per inserire il valore 20 nello stack.
8. Utilizzare la funzione push() per inserire il valore 30 nello stack.
9. Utilizzare la funzione push() per inserire il valore 40 nello stack.
10. Utilizza la funzione pop() per rimuovere l'elemento in cima allo stack, ovvero 40. L'elemento in cima ora diventa 30.
11. Utilizza la funzione pop() per rimuovere l'elemento in cima allo stack, ovvero 30. L'elemento in cima ora diventa 20.
12. Utilizza un ciclo while e la funzione empty() per verificare se lo stack NON è vuoto. IL ! è l'operatore NOT.
13. Stampa del contenuto corrente dello stack sulla console.
14. Chiama la funzione pop() sullo stack.
15. Fine del corpo del ciclo while.
16. Fine del corpo della funzione main().

vuoto(), dimensione(), superiore()

Gli stack hanno funzioni integrate che puoi utilizzare per giocare con lo stack e i suoi valori. Questi includono:

• vuoto()- controlla se uno stack è vuoto o meno.
• size()- restituisce la dimensione dello stack, ovvero il numero di elementi in uno stack.
• top()- accede all'elemento dello stack in alto.

Esempio 2:

#include <iostream> 
#include <stack>  
using namespace std;
void createStack(stack <int> mystack)
{
	stack <int> ms = mystack;
	while (!ms.empty())
	{
		cout << '\t' << ms.top();
		ms.pop();
	}
	cout << '\n';
}
int main()
{
	stack <int> st;
	st.push(32);
	st.push(21);
	st.push(39);
	st.push(89);
	st.push(25);

	cout << "The stack st is: ";
	createStack(st);
	cout << "\n st.size() : " << st.size();
	cout << "\n st.top() : " << st.top();
	cout << "\n st.pop() : ";
	st.pop();
	createStack(st);
	return 0;
}

Produzione:

Ecco uno screenshot del codice:

Spiegazione del codice:

1. Includi il file header iostream nel nostro codice per poter utilizzare le sue funzioni.
2. Includi il file di intestazione dello stack nel nostro codice per poter utilizzare le sue funzioni.
3. Includi lo spazio dei nomi std nel nostro programma per poter utilizzare le sue classi senza chiamarlo.
4. Crea la funzione createStack che possiamo usare per creare lo stack mystack. Lo stack conterrà un insieme di numeri interi.
5. L'inizio del corpo della funzione createStack.
6. Crea un'istanza del tipo di dati mystack e assegnagli il nome ms.
7. Utilizza il ciclo while e la funzione empty() per verificare se lo stack è vuoto.
8. L'inizio del corpo del ciclo while.
9. Utilizza la funzione top() memorizzata in cima allo stack. Il carattere \t creerà una nuova scheda.
10. Utilizza la funzione pop() per eliminare l'elemento in cima allo stack.
11. Fine del corpo del ciclo while.
12. Stampa una riga vuota sulla console.
13. Fine del corpo della funzione createStack.
14. Chiama la funzione main(). La logica del programma dovrebbe essere aggiunta all'interno del corpo della funzione main().
15. L'inizio del corpo della funzione main().
16. Crea un oggetto stack st.
17. Utilizzare la funzione push() per inserire l'elemento 32 nello stack.
18. Utilizzare la funzione push() per inserire l'elemento 21 nello stack.
19. Utilizzare la funzione push() per inserire l'elemento 39 nello stack.
20. Utilizzare la funzione push() per inserire l'elemento 89 nello stack.
21. Utilizzare la funzione push() per inserire l'elemento 25 nello stack.
22. Stampa del testo sulla console.
23. Chiama la funzione createStack per eseguire le operazioni di inserimento di cui sopra nello stack.
24. Stampa la dimensione dello stack sulla console insieme ad altro testo.
25. Stampa l'elemento in cima allo stack sulla console.
26. Stampa del testo sulla console.
27. Elimina l'elemento in cima allo stack. Restituirà quindi gli elementi rimanenti nello stack.
28. Chiama la funzione createStack per eseguire le operazioni di cui sopra.
29. Il programma deve restituire valore in caso di completamento positivo.
30. Fine del corpo della funzione main().

emplace() e swap()

Queste sono altre funzioni dello stack integrate:

• emplace()- costruisce quindi inserisce il nuovo elemento in cima allo stack.
• swap()- scambia il contenuto dello stack con il contenuto di un altro stack.

Esempio 3:

#include <iostream>    
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st1;
	stack<int> st2;

	st1.emplace(12);
	st1.emplace(19);

	st2.emplace(20);
	st2.emplace(23);

	st1.swap(st2);

	cout << "st1 = ";
	while (!st1.empty()) {
		cout << st1.top() << " ";
		st1.pop();
	}

	cout << endl << "st2 = ";
	while (!st2.empty()) {
		cout << st2.top() << " ";
		st2.pop();
	}
}

Produzione:

Ecco uno screenshot del codice:

Spiegazione del codice:

1. Includi il file di intestazione iostream nel nostro codice per utilizzare le sue funzioni.
2. Includi il file di intestazione dello stack nel nostro codice per utilizzare le sue funzioni.
3. Includi il file di intestazione cstdlib nel nostro codice per utilizzare le sue funzioni.
4. Includi lo spazio dei nomi std nel nostro codice per utilizzare le sue classi senza chiamarlo.
5. Chiama la funzione main(). La logica del programma verrà aggiunta al corpo di questa funzione.
6. Dichiara uno stack denominato st1 per memorizzare valori interi.
7. Dichiara uno stack denominato st2 per memorizzare valori interi.
8. Utilizzare la funzione emplace() per inserire l'intero 12 nello stack denominato st1.
9. Utilizzare la funzione emplace() per inserire l'intero 19 nello stack denominato st1.
10. Utilizzare la funzione emplace() per inserire l'intero 20 nello stack denominato st2.
11. Utilizzare la funzione emplace() per inserire l'intero 23 nello stack denominato st2.
12. Utilizza la funzione swap() per scambiare il contenuto dei due stack, st1 e st2. Il contenuto dello stack st1 dovrebbe essere spostato nello stack st2. Il contenuto dello stack st2 dovrebbe essere spostato nello stack st1.
13. Stampa del testo sulla console.
14. Utilizza l'istruzione while e la funzione empty() per verificare se lo stack st1 non è vuoto.
15. Stampa il contenuto dello stack st1 sulla console. Il " " aggiunge spazio tra gli elementi dello stack durante la stampa sulla console.
16. Esegui la funzione pop() sullo stack st1 per rimuovere l'elemento in cima.
17. Fine del corpo dell'istruzione while.
18. Stampa del testo sulla console. La fine è a C++ parola chiave per la riga finale. Sposta il cursore del mouse sulla riga successiva per iniziare la stampa da lì.
19. Utilizza l'istruzione while e la funzione empty() per verificare se lo stack st2 non è vuoto.
20. Stampa il contenuto dello stack st2 sulla console. Il " " aggiunge spazio tra gli elementi dello stack durante la stampa sulla console.
21. Esegui la funzione pop() sullo stack st2 per rimuovere l'elemento in cima.
22. Fine del corpo dell'istruzione while.
23. Fine del corpo della funzione main().

Impila in STL

La STL (Standard Template Library) viene fornita con classi di template che forniscono common C++ strutture dati. Pertanto uno stack può essere realizzato anche in AWL. Includiamo semplicemente questa libreria nel nostro codice e la usiamo per definire uno stack.

stack<T> st; 

La sintassi sopra riportata dichiara uno stack st per elementi di tipo di dati T.

Esempio 4:

#include <iostream>      
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st;
	st.push(12);
	st.push(19);
	st.push(20);
	cout << st.top();   
	cout << st.size();  
}

Produzione:

Ecco uno screenshot del codice:

Spiegazione del codice:

1. Includi il file di intestazione iostream nel nostro codice per utilizzare le sue funzioni.
2. Includi il file di intestazione dello stack nel nostro codice per utilizzare le sue funzioni.
3. Includi il file di intestazione cstdlib nel nostro codice per utilizzare le sue funzioni.
4. Includi lo spazio dei nomi std nel nostro codice per utilizzare le sue classi senza chiamarlo.
5. Chiama la funzione main(). La logica del programma dovrebbe essere aggiunta al corpo di questa funzione.
6. Dichiara uno stack st per memorizzare dati interi.
7. Aggiungi l'elemento 12 alla pila.
8. Aggiungi l'elemento 19 alla pila.
9. Aggiungi l'elemento 20 alla pila.
10. Stampa l'elemento in cima allo stack sulla console.
11. Stampa la dimensione dello stack sulla console.
12. Fine del corpo della funzione main().

Sommario

• Uno stack è una struttura dati che opera in base alla tecnica LIFO (Last In first Out).
• Lo std::stack consente solo di aggiungere e rimuovere elementi da un'estremità.
• La classe std::stack è un adattatore contenitore, che contiene elementi con un tipo di dati simile.
• È possibile creare uno stack da vari contenitori di sequenza.
• Se non fornisci un contenitore, per impostazione predefinita verrà utilizzato il contenitore deque.
• La funzione push() serve per inserire elementi nello stack.
• La funzione pop() serve per rimuovere l'elemento principale dal passaggio.
• La funzione empty() serve per verificare se uno stack è vuoto o meno.