Stack in C ++ STL con Example

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 del contenitore. Gli oggetti contenitore contengono dati di un tipo di dati simile. È possibile creare una pila da vari contenitori di sequenze. Se non viene fornito alcun contenitore, per impostazione predefinita verrà utilizzato il deque containe. Gli adattatori del contenitore non supportano gli iteratori, quindi non possono essere usati per manipolare i dati.

In questo tutorial C ++ imparerai

• Cos'è std :: stack?
• Sintassi dello stack
• Tipi di membri
• Operazioni in Stack
• Implementazione dello stack
• push () e pop ()
• empty (), size (), top ()
• emplace () e swap ()
• Stack in STL

Sintassi dello stack

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

template  > class stack;

• Type - è il tipo di elemento contenuto nello std :: stack. Può essere qualsiasi tipo C ++ valido o anche un tipo definito dall'utente.
• Contenitore : è il tipo di 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. Denota il tipo di contenitore sottostante.
• size_type- Tipo integrale senza segno.

Operazioni in Stack

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

• push - Aggiunge / spinge un elemento nella pila.
• pop - Rimuove / estrae un elemento dalla pila.
• peek - Restituisce l'elemento in cima alla pila senza rimuoverlo.
• isFull - Controlla se uno stack è pieno.
• isEmpty - Controlla se uno stack è vuoto.

Implementazione dello stack

Passaggio 1) Inizialmente abbiamo una pila vuota. La parte superiore di una pila vuota è impostata su -1.

Passaggio 2) Successivamente, abbiamo inserito l'elemento 5 nello stack. La parte superiore della pila indicherà l'elemento 5.

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

Passaggio 4) Abbiamo quindi eseguito un'operazione pop, rimuovendo l'elemento superiore dallo stack. L'elemento 50 viene estratto dalla pila. La parte superiore della pila ora punta all'elemento 5.

push () e pop ()

La funzione stack :: push () aggiunge 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 nella pila.

La funzione stack :: pop () rimuove l'elemento superiore dello stack. Questo è l'ultimo elemento della pila. 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 #include using namespace std;int main() {stack 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. Includere il file di intestazione iostream nel nostro codice per utilizzare le sue funzioni.
2. Includere il file di intestazione dello stack nel nostro codice per utilizzare le sue funzioni.
3. Includere 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. Utilizzare la funzione pop () per rimuovere l'elemento in alto dallo stack, ovvero 40. L'elemento in alto diventa ora 30.
11. Utilizzare la funzione pop () per rimuovere l'elemento in alto dallo stack, ovvero 30. L'elemento in alto diventa ora 20.
12. Usa un ciclo while e una funzione empty () per verificare se lo stack NON è vuoto. Il ! è l'operatore NOT.
13. Stampa il contenuto corrente dello stack sulla console.
14. Chiama la funzione pop () nello stack.
15. Fine del corpo del ciclo while.
16. Fine del corpo della funzione main ().

empty (), size (), top ()

Gli stack hanno funzioni integrate che puoi usare per giocare con lo stack ei suoi valori. Questi includono:

• empty () - 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 #include using namespace std;void createStack(stack  mystack){stack  ms = mystack;while (!ms.empty()){cout << '\t' << ms.top();ms.pop();}cout << '\n';}int main(){stack  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. Includere il file di intestazione iostream nel nostro codice per poter utilizzare le sue funzioni.
2. Includere il file di intestazione dello stack nel nostro codice per poter utilizzare le sue funzioni.
3. Includere 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 assegnandogli il nome ms.
7. Usa il ciclo while e la funzione empty () per verificare se lo stack è vuoto.
8. L'inizio del corpo del ciclo while.
9. Usa la funzione top () memorizzata in cima allo stack. Il carattere \ t creerà una nuova scheda.
10. Usa 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 sopra nello stack.
24. Stampa la dimensione della pila sulla console insieme ad altro testo.
25. Stampa l'elemento in cima alla pila sulla console.
26. Stampa del testo sulla console.
27. Elimina l'elemento in cima alla pila. Restituirà quindi gli elementi rimasti nello stack.
28. Chiama la funzione createStack per eseguire le operazioni precedenti.
29. Il programma deve restituire un valore una volta completato con successo.
30. Fine del corpo della funzione main ().

emplace () e swap ()

Queste sono altre funzioni dello stack integrate:

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

Esempio 3:

#include #include #include using namespace std;int main() {stack st1;stack 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. Includere il file di intestazione iostream nel nostro codice per utilizzare le sue funzioni.
2. Includere il file di intestazione dello stack nel nostro codice per utilizzare le sue funzioni.
3. Includere il file di intestazione cstdlib nel nostro codice per utilizzare le sue funzioni.
4. Includere 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 all'interno del corpo di questa funzione.
6. Dichiarare uno stack denominato st1 per memorizzare valori interi.
7. Dichiarare uno stack denominato st2 per memorizzare valori interi.
8. Usa la funzione emplace () per inserire il numero intero 12 nello stack chiamato st1.
9. Usa la funzione emplace () per inserire il numero intero 19 nello stack chiamato st1.
10. Usa la funzione emplace () per inserire il numero intero 20 nello stack chiamato st2.
11. Utilizzare la funzione emplace () per inserire l'intero 23 nello stack denominato st2.
12. Utilizzare 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. Utilizzare 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 quando li stampa sulla console.
16. Esegui la funzione pop () sullo stack st1 per rimuovere l'elemento superiore.
17. Fine del corpo dell'istruzione while.
18. Stampa del testo sulla console. Endl è una parola chiave C ++ per end line. Sposta il cursore del mouse sulla riga successiva per iniziare a stampare da lì.
19. Utilizzare 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 quando li stampa sulla console.
21. Esegui la funzione pop () sullo stack st2 per rimuovere l'elemento in alto.
22. Fine del corpo dell'istruzione while.
23. Fine del corpo della funzione main ().

Stack in STL

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

stack st;

La sintassi precedente dichiara uno stack st per gli elementi del tipo di dati T.

Esempio 3:

#include #include #include using namespace std;int main() {stack 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. Includere il file di intestazione iostream nel nostro codice per utilizzare le sue funzioni.
2. Includere il file di intestazione dello stack nel nostro codice per utilizzare le sue funzioni.
3. Includere il file di intestazione cstdlib nel nostro codice per utilizzare le sue funzioni.
4. Includere 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 all'interno del corpo di questa funzione.
6. Dichiarare 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 alla pila sulla console.
11. Stampa la dimensione della pila 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 del contenitore, che contiene elementi di un tipo di dati simile.
• È possibile creare una pila da vari contenitori di sequenze.
• 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 in alto dal passaggio.
• La funzione empty () serve per controllare se uno stack è vuoto o meno.