Tuesday, August 11th 2020

Stack e Queue in C++

Quando programmiamo ci capita spesso di dover implementare un struttura LIFO o FIFO, per gestire particolari problematiche.

C++ ci fornisce due classi già pronte: stack e queue.

Stack

Lo stack implementa una struttura LIFO (Last In First Out), utile quando dobbiamo creare un parser, o comunque scomporre e ricomporre elementi.

Le funzioni di utility incluse nello stack sono le seguenti:

  • size(): ritorna il numero di elementi presenti nello stack

  • empty(): ritorna true se lo stack è vuoto

  • top(): ritorna l’elemento in cima allo stack

  • push(T): aggiunge un elemento allo stack

  • pop(): rimuove un elemento dallo stack

#include <iostream>
#include <stack>

using namespace std;

int main() {

    //Tra '<' e '>' metto il tipo di elementi
    stack<int> pila;

    //Aggiungo 3 numeri nello stack
    pila.push(10);
    pila.push(20);
    pila.push(30);

    //Stampo il numero di elementi dello stack
    cout << pila.size() << endl;

    //Rimuovo un elemento dallo stack
    pila.pop();

    //Stampo l'elemento in cima allo stack
    cout << "Elemento in cima: " << pila.top() << endl;

    //Verifico se lo stack è vuoto
    cout << "vuoto = " << pila.empty();

    return 0;
}

Queue

La queue implementa una struttura FIFO (First In First Out), utile quando dobbiamo gestire una coda di messaggi o di altri elementi.

Le funzioni di utility incluse nella queue sono le seguenti:

  • size(): ritorna il numero di elementi presenti nella coda

  • empty(): ritorna true se la coda è vuoto

  • front(): ritorna il primo elemento in coda

  • back(): ritorna l’ultimo elemento in coda

  • push(T): aggiunge un elemento alla coda

  • pop(): rimuove un elemento dalla coda

#include <iostream>
#include <queue>

using namespace std;

int main() {

    //Tra '<' e '>' metto il tipo di elementi
    queue<int> coda;

    //Aggiungo 3 numeri alla coda
    coda.push(10);
    coda.push(20);
    coda.push(30);

    //Stampo il numero di elementi della coda
    cout << coda.size() << endl;

    //Rimuovo un elemento dalla coda
    coda.pop();

    //Stampo il primo elemento in coda
    cout << "Primo in coda: " << coda.front() << endl;

    //Stampo l'ultimo elemento in coda
    cout << "Ultimo in coda: " << coda.back() << endl;

    //Verifico se la coda è vuota
    cout << "vuoto = " << coda.empty();

    return 0;
}