stacks queues stl
Impara l'implementazione di stack e code in STL con esempi.
Stack e code sono due contenitori in STL che sono di natura molto semplice. Sono i contenitori più semplici che hanno ampie applicazioni nella programmazione del software.
In questo tutorial, vedremo un'implementazione dettagliata di entrambi questi contenitori in STL. Esamineremo anche le varie operazioni supportate da stack e queue con esempi.
=> Guarda qui la serie di formazione C ++ semplice.
Cosa imparerai:
Pile
Il contenitore dello stack in STL è un tipo di adattatori del contenitore. Viene utilizzato per replicare una struttura di dati dello stack in C ++. Stack container è un insieme di elementi in cui gli elementi vengono inseriti a un'estremità e vengono eliminati anche alla stessa estremità.
Questo punto comune di aggiunta ed eliminazione è noto come 'Top of the stack'.
La rappresentazione pittorica dello stack è mostrata di seguito.
Come mostrato nella rappresentazione sopra, lo stack è un contenitore in cui gli elementi vengono aggiunti ed eliminati dalla stessa estremità denominata Top of the stack.
Poiché l'aggiunta e la cancellazione avvengono alla stessa fine, possiamo dire che lo stack container è un tipo di lavoro LIFO (last in, first out). Ciò significa che l'elemento aggiunto per primo sarà l'ultimo a essere eliminato.
Per implementare lo stack container, dobbiamo includere l'intestazione nel nostro programma.
#include
La sintassi della dichiarazione generale per il contenitore dello stack è:
stack stackName;
Operazioni sullo stack
Successivamente, esaminiamo le varie operazioni che impilano il contenitore nei supporti STL.
- spingere : l'operazione push viene utilizzata per inserire un elemento nello stack. Questa operazione aggiunge sempre elementi in cima allo stack.
Considera uno stack vuoto mystack di tipo intero .
Successivamente, aggiungiamo l'elemento 1 allo stack.
Quindi, aggiungiamo l'elemento 3 allo stack.
Secondo la rappresentazione, a seguito di un'operazione push, un elemento viene aggiunto in cima allo stack. Dopo ogni operazione di push, la dimensione dello stack viene aumentata di 1.
- pop : l'operazione pop viene utilizzata per rimuovere un elemento dallo stack. L'elemento rimosso è quello a cui punta la parte superiore della pila. Come risultato dell'operazione pop, la dimensione dello stack viene ridotta di 1.
Vediamo come appare l'operazione pop:
Considera lo stack mystack come sopra in cui abbiamo già spinto 2 elementi.
Ora chiamiamo la funzione pop (). Quando questa chiamata viene eseguita, l'elemento in cima allo stack viene rimosso e 'Top' punta all'elemento successivo come mostrato di seguito.
Se chiamiamo di nuovo pop (), l'elemento successivo (in questo caso 1) verrà rimosso risultando in uno stack vuoto.
come restituire un array di stringhe in java
- superiore : Restituisce l'elemento più in alto dello stack.
- vuoto : Controlla se la pila è vuota o meno.
- taglia: Restituisce la dimensione dello stack, ovvero il numero di elementi nello stack.
Di seguito è riportato un esempio di implementazione di Stack per comprendere meglio le operazioni.
#include #include using namespace std; void printStack(stack stk) { while (!stk.empty()) { cout << ' ' << stk.top(); stk.pop(); } cout << '
'; } int main () { stack oddstk; oddstk.push(1); oddstk.push(3); oddstk.push(5); oddstk.push(7); oddstk.push(9); cout << 'The stack is : '; printStack(oddstk); cout << '
Size of stack: ' << oddstk.size(); cout << '
Top of stack: ' << oddstk.top(); cout << '
oddstk.pop() : '; oddstk.pop(); printStack(oddstk); cout<<'
Another pop(): '; oddstk.pop(); printStack(oddstk); return 0; }
L'esempio sopra mostra chiaramente l'operazione push che genera uno stack. Mostra anche lo stack dopo due operazioni pop consecutive.
Quindi abbiamo visto lo stack e le sue operazioni in STL. Inoltre, in questo tutorial, vedremo l'implementazione dettagliata di un altro semplice contenitore STL che è 'Queue'.
Coda
La coda è ancora un altro contenitore in STL che è anche molto semplice e utile. Il contenitore della coda è una replica della struttura dei dati della coda in C ++. A differenza dello stack, nel contenitore della coda ci sono due estremità, cioè anteriore e posteriore.
Gli elementi vengono aggiunti alla coda in fondo mentre vengono eliminati dalla parte anteriore della coda. In generale, la coda utilizza il tipo di arrangiamento FIFO (First in, First Out).
Per implementare un contenitore di code in un programma, dobbiamo includere un'intestazione nel codice.
#include
La sintassi generale per la dichiarazione della coda è:
queue nome_coda;
Dichiariamo il contenitore della coda come segue:
Queue myqueue;
Operazioni in coda
Adesso vedremo le varie operazioni supportate dalla coda.
- spingere: La funzione 'push' aggiunge l'elemento alla fine della coda, cioè in fondo alla coda.
- pop: La funzione 'pop' rimuove il primo elemento della coda, ovvero l'elemento all'inizio della coda.
Cerchiamo di capire le funzioni push e pop della coda.
miglior strumento per creare diagramma di flusso
Considera una coda vuota dichiarata sopra myqueue. Ora spingiamo un numero pari 2 in coda con l'operazione
myqueue.push (2);
Ora la coda sarà simile a:
Successivamente, aggiungiamo '4' alla coda con la chiamata 'myqueue.push (4)'.
Ora la coda appare come mostrato di seguito:
Come visto sopra, gli elementi vengono inseriti nella coda dal retro o dal retro.
Ora inseriamo l'operazione su myqueue.
myqueue.pop ();
Quindi, come si vede, quando viene chiamato pop (), l'elemento in primo piano nella coda viene rimosso. Ciò significa che il primo elemento che viene immesso nella coda è il primo elemento a essere fuori dalla coda.
- davanti: Questa funzione restituisce un riferimento al primo elemento della coda.
- indietro: Indietro restituisce un riferimento all'ultimo elemento nella coda.
- vuoto: Controlla se la coda è vuota.
- taglia: Restituisce la dimensione della coda, ovvero il numero di elementi nella coda.
Di seguito è riportato un programma di esempio che dimostra le operazioni utilizzate dal contenitore della coda.
#include #include using namespace std; void printQueue(queue myqueue) { queue secqueue = myqueue; while (!secqueue.empty()) { cout << ' ' << secqueue.front(); secqueue.pop(); } cout << '
'; } int main() { queue myqueue; myqueue.push(2); myqueue.push(4); myqueue.push(6); myqueue.push(8); cout << 'The queue myqueue is : '; printQueue(myqueue); cout << '
myqueue.size() : ' << myqueue.size(); cout << '
myqueue.front() : ' << myqueue.front(); cout << '
myqueue.back() : ' << myqueue.back(); cout << '
myqueue.pop() : '; myqueue.pop(); printQueue(myqueue); return 0; }
Produzione:
La coda myqueue è: 2 4 6 8
myqueue.size (): 4
myqueue.front (): 2
myqueue.back (): 8
myqueue.pop (): 4 6 8
Come mostrato sopra, dichiariamo prima un contenitore di code. Quindi, utilizzando l'operazione push, aggiungiamo i primi quattro numeri pari. Dopodiché estraiamo l'elemento dalla coda e visualizziamo la coda modificata.
Conclusione
Con questo, siamo arrivati alla fine di questo tutorial su pile e code. Come già accennato, questi sono i contenitori più semplici che abbiamo in STL. Un'altra variante del contenitore della coda è nota come 'coda prioritaria'.
Nel nostro prossimo tutorial, discuteremo di più sulla coda prioritaria in STL !!
=> Visita qui per imparare il C ++ da zero.