Impila dentro C++ STL con esempio

Cos'è std::stack?

Uno stack è una struttura dati che opera in base alla tecnica LIFO (Last In First Out). Lo std::stack consente di aggiungere e rimuovere elementi solo da un'estremità.

La classe std::stack è un adattatore di contenitori. Gli oggetti contenitore contengono dati di un tipo simile. È possibile creare uno stack utilizzando diversi contenitori di sequenze. Se non viene specificato alcun contenitore, verrà utilizzato per impostazione predefinita il contenitore deque. Gli adattatori di contenitori non supportano gli iteratori, quindi non possono essere utilizzati per manipolare i dati.

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;

• Tipo – è 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:

• tipo_valore– Il primo parametro del modello, T. Indica i tipi di elemento.
• tipo_container– Il secondo parametro del modello, Container. Indica il tipo di contenitore sottostante.
• tipo_dimensione– Tipo intero senza segno.

Operazioni nello Stack

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

• spingere – Aggiunge/spinge un elemento nella pila.
• pop – Rimuove/estrae un elemento dalla pila.
• sbirciare – Restituisce l'elemento in cima alla pila senza rimuoverlo.
• è pieno – Verifica se uno stack è pieno.
• è vuoto – Verifica se una pila è vuota.

Implementazione dello stack

I seguenti passaggi mostrano come si sposta la parte superiore della pila quando gli elementi vengono inseriti e poi estratti:

Passaggio 1) Inizialmente abbiamo uno stack vuoto. La cima di uno stack vuoto è impostata a -1.

Passaggio 2) Successivamente, abbiamo inserito l'elemento 5 nello stack. La cima dello stack punterà all'elemento 5.

Passaggio 3) Successivamente, abbiamo inserito l'elemento 50 nello stack. La cima dello stack si sposta e punta all'elemento 50.

Passaggio 4) Abbiamo quindi eseguito un'operazione pop, rimuovendo l'elemento in cima allo stack. L'elemento 50 viene estratto dallo stack. La cima dello stack ora punta all'elemento 5.

spingi() e pop()

La funzione stack::push() aggiunge un nuovo elemento in cima allo stack. La dimensione dello stack viene incrementata di 1 dopo l'inserimento. La funzione ha la seguente sintassi:

stack.push(value)

Il valore è l'elemento da inserire nello stack.

La funzione `stack::pop()` rimuove l'elemento in cima allo stack. Questo è l'elemento più recente dello stack. La dimensione dello stack si riduce 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:

Code Spiegazione:

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()– verifica se una pila è vuota o meno.
• dimensione()– restituisce la dimensione dello stack, ovvero il numero di elementi presenti nello stack.
• superiore()– accede all'elemento dello stack in cima.

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:

Code Spiegazione:

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:

• posizionare()– costruisce quindi un nuovo elemento in cima allo stack.
• scambio()– scambia il contenuto di una pila con il contenuto di un'altra pila.

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:

Code Spiegazione:

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:

Code Spiegazione:

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().

DOMANDE FREQUENTI