Menu

Stack Struttura Dati In C ++ Con Illustrazione

stack data structure c with illustration

cosa significa mancata corrispondenza della chiave di sicurezza della rete

Prova Il Nostro Strumento Per Eliminare I Problemi

Tutto quello che devi sapere sullo stack in C ++.

Stack è una struttura dati fondamentale che viene utilizzata per memorizzare gli elementi in modo lineare.

Stack segue LIFO (ultimo entrato, primo uscito) ordine o approccio in cui vengono eseguite le operazioni. Ciò significa che l'elemento che è stato aggiunto per ultimo allo stack sarà il primo elemento a essere rimosso dallo stack.

=> Visita qui per vedere l'intera serie di formazione C ++ per tutti.

PILA

Cosa imparerai:

Stack in C ++

Una pila è simile alla pila della vita reale o una pila di cose che mettiamo una sopra l'altra.

Di seguito è riportata una rappresentazione pittorica di Stack.

rappresentazione pittorica della pila

Come mostrato sopra, c'è una pila di piatti impilati uno sopra l'altro. Se vogliamo aggiungere un altro elemento, lo aggiungiamo in cima alla pila come mostrato nella figura sopra (lato sinistro). Questa operazione di aggiunta di un elemento alla pila è chiamata ' spingere '.

Sul lato destro, abbiamo mostrato un'operazione opposta, ovvero rimuoviamo un elemento dalla pila. Anche questo viene fatto dalla stessa estremità, ovvero la parte superiore della pila. Questa operazione si chiama ' Pop '.

Come mostrato nella figura sopra, vediamo che push e pop vengono eseguiti dalla stessa estremità. Questo fa sì che lo stack segua l'ordine LIFO. La posizione o l'estremità da cui gli elementi vengono inseriti o estratti dalla pila è chiamata ' In cima alla pila '.

Inizialmente, quando non ci sono elementi nella pila, la parte superiore della pila è impostata su -1. Quando aggiungiamo un elemento alla pila, la parte superiore della pila viene incrementata di 1 indicando che l'elemento è stato aggiunto. Al contrario, la parte superiore della pila viene decrementata di 1 quando un oggetto viene estratto dalla pila.

Successivamente, vedremo alcune delle operazioni di base della struttura dati dello stack che richiederemo durante l'implementazione dello stack.

Operazioni di base

Di seguito sono riportate le operazioni di base supportate dallo stack.

  • spingere - Aggiunge o inserisce un elemento nello stack.
  • pop - Rimuove o estrae un elemento dalla pila.
  • sbirciare - Ottiene l'elemento superiore dello stack ma non lo rimuove.
  • è pieno - Verifica se la pila è piena.
  • è vuoto - Verifica se la pila è vuota.

Illustrazione

Illustrazione dello stack

L'illustrazione sopra mostra la sequenza di operazioni eseguite sullo stack. Inizialmente, la pila è vuota. Per una pila vuota, la parte superiore della pila è impostata su -1.

Successivamente, inseriamo l'elemento 10 nello stack. Vediamo che la parte superiore della pila ora punta all'elemento 10.

Successivamente, eseguiamo un'altra operazione di spinta con l'elemento 20, in conseguenza della quale la parte superiore della pila ora punta a 20. Questo stato è la terza cifra.

Ora nell'ultima figura, eseguiamo un'operazione pop (). Come risultato dell'operazione di estrazione, l'elemento puntato nella parte superiore della pila viene rimosso dalla pila. Quindi nella figura, vediamo che l'elemento 20 viene rimosso dalla pila. Quindi la parte superiore della pila ora punta a 10.

In questo modo, possiamo facilmente distinguere l'approccio LIFO utilizzato dallo stack.

Implementazione

# 1) Utilizzo di array

Di seguito è riportata l'implementazione C ++ dello stack utilizzando gli array:

#include using namespace std; #define MAX 1000 //max size for stack class Stack { int top; public: int myStack(MAX); //stack array Stack() { top = -1; } bool push(int x); int pop(); bool isEmpty(); }; //pushes element on to the stack bool Stack::push(int item) { if (top >= (MAX-1)) { cout << 'Stack Overflow!!!'; return false; } else { myStack(++top) = item; cout<

Produzione:

Lo Stack Push

Due

4

6

The Stack Pop:

6

4

Due

Nell'output, possiamo vedere che gli elementi vengono inseriti nello stack in un ordine e vengono estratti dallo stack nell'ordine inverso. Questo mostra l'approccio LIFO (Last in, First out) per lo stack.

Per l'implementazione dell'array dello stack sopra, possiamo concludere che è molto facile da implementare poiché non sono coinvolti puntatori. Ma allo stesso tempo, la dimensione dello stack è statica e lo stack non può crescere o ridursi dinamicamente.

Successivamente, implementeremo lo stack utilizzando gli array nel linguaggio di programmazione Java.

class Stack { static final int MAX = 1000; // Maximum Stack size int top; int myStack() = new int(MAX); boolean isEmpty() { return (top = (MAX-1)) { System.out.println('Stack Overflow'); return false; } else { myStack(++top) = item; System.out.println(item); return true; } } int pop() { if (top <0) { System.out.println('Stack Underflow'); return 0; } else { int item = myStack(top--); return item; } } } //Main class code class Main { public static void main(String args()) { Stack stack = new Stack(); System.out.println('Stack Push:'); stack.push(1); stack.push(3); stack.push(5); System.out.println('Stack Pop:'); while(!stack.isEmpty()) { System.out.println(stack.pop()); } } }

Produzione:

Stack Push:

1

3

5

Stack Pop:

5

3

1

La logica di implementazione è la stessa dell'implementazione C ++. L'output mostra la tecnica LIFO di spingere dentro e fuori gli elementi da / verso lo stack.

Come già affermato, l'implementazione dello stack utilizzando gli array è l'implementazione più semplice ma è di natura statica in quanto non è possibile aumentare o ridurre dinamicamente lo stack.

# 2) Utilizzo di un elenco collegato

Successivamente, implementiamo le operazioni di stack utilizzando un elenco collegato sia in C ++ che in Java. Innanzitutto, dimostreremo l'implementazione del C ++.

#include using namespace std; // class to represent a stack node class StackNode { public: int data; StackNode* next; }; StackNode* newNode(int data) { StackNode* stackNode = new StackNode(); stackNode->data = data; stackNode->next = NULL; return stackNode; } int isEmpty(StackNode *root) { return !root; } void push(StackNode** root, int new_data){ StackNode* stackNode = newNode(new_data); stackNode->next = *root; *root = stackNode; cout<data; free(temp); return popped; } int peek(StackNode* root) { if (isEmpty(root)) return -1; return root->data; } int main() { StackNode* root = NULL; cout<<'Stack Push:'<

Produzione:

Stack Push:

100

200

le migliori cuffie da realtà virtuale per Xbox One

300

L'elemento superiore è 300

Stack Pop:

300

200

100

L'elemento superiore è -1

Successivamente, presentiamo l'implementazione Java dello stack utilizzando un elenco collegato.

class LinkedListStack { StackNode root; static class StackNode { int data; StackNode next; StackNode(int data) { this.data = data; } } public boolean isEmpty() { if (root == null) { return true; } else return false; } public void push(int new_data) { StackNode newNode = new StackNode(new_data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } System.out.println(new_data); } public int pop() { int popped = Integer.MIN_VALUE; if (root == null) { System.out.println('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { System.out.println('Stack is empty'); return Integer.MIN_VALUE; } else { return root.data; } } } class Main{ public static void main(String() args) { LinkedListStack stack = new LinkedListStack(); System.out.println('Stack Push:'); stack.push(100); stack.push(200); stack.push(300); System.out.println('Top element is ' + stack.peek()); System.out.println('Stack Pop:'); while(!stack.isEmpty()){ System.out.println(stack.pop()); } System.out.println('Top element is ' + stack.peek()); } }

Produzione:

Stack Push:

100

200

300

L'elemento superiore è 300

Stack Pop:

300

200

100

Lo stack è vuoto

L'elemento superiore è -2147483648

Abbiamo appena visto implementazioni C ++ e Java per uno stack utilizzando elenchi collegati. Rappresentiamo ogni voce dello stack come un nodo dell'elenco collegato. Il vantaggio più importante di questa implementazione è che è dinamica. Ciò significa che possiamo aumentare o ridurre la dimensione dello stack secondo il nostro requisito.

Questo è diverso dal caso dell'implementazione dello stack utilizzando array in cui dobbiamo dichiarare la dimensione in anticipo e non possiamo cambiarla dinamicamente.

Lo svantaggio di questa implementazione è che poiché utilizziamo puntatori ovunque, occupa un po 'troppo spazio rispetto all'implementazione dell'array.

Applicazioni di Stack

Parliamo di alcune delle applicazioni della struttura dei dati dello stack. La struttura dei dati dello stack viene utilizzata in una vasta gamma di applicazioni nella programmazione software principalmente per la sua semplicità e facilità di implementazione.

Descriveremo brevemente alcune delle applicazioni dello stack di seguito:

# 1) Espressioni da infisso a suffisso

Qualsiasi espressione aritmetica generale è della forma operando 1 OP operando 2 .

In base alla posizione dell'operatore OP, abbiamo i seguenti tipi di espressioni:

  • Infix - La forma generale dell'espressione infisso è ' operando 1 OP operando 2 '. Questa è la forma di base dell'espressione e usiamo sempre in matematica.
  • Prefisso - Quando un operatore viene posizionato prima degli operandi, è un'espressione prefisso. La forma generale di espressione infissa è ' OP operando1 operando2 '.
  • Postfix - Nelle espressioni con suffisso, gli operandi vengono scritti per primi seguiti dall'operatore. Ha la forma “operando1 operando2 OP”.

Considera l'espressione 'a + b * c ' . Il compilatore analizza l'espressione da sinistra a destra o da destra a sinistra. Prendendo cura della precedenza e dell'associatività degli operatori, analizzerà prima l'espressione per valutare l'espressione b * c. Successivamente, dovrà nuovamente scansionare l'espressione per aggiungere il risultato di b * c ad a.

Man mano che le espressioni diventano sempre più complesse, questo tipo di approccio di scansione continua dell'espressione diventa inefficace.

Per superare questa inefficienza, convertiamo l'espressione in suffisso o prefisso in modo che possano essere facilmente valutati utilizzando una struttura di dati dello stack.

# 2) Analisi / valutazione dell'espressione

Utilizzando lo stack, possiamo anche eseguire la valutazione dell'espressione effettiva. In questo, l'espressione viene scansionata da sinistra a destra e gli operandi vengono inseriti nello stack.

Ogni volta che viene incontrato un operatore, gli operandi vengono estratti e l'operazione viene eseguita. Il risultato dell'operazione viene nuovamente inserito nello stack. In questo modo l'espressione viene valutata utilizzando lo stack e il risultato finale dell'espressione è solitamente la parte superiore corrente dello stack.

# 3) Traversate degli alberi

La struttura dei dati ad albero può essere attraversata per visitare ogni nodo in molti modi ea seconda di quando viene visitato il nodo radice che abbiamo.

  • inOrder traversal
  • preordina Traversal
  • postOrder traversal

Per attraversare in modo efficiente l'albero, utilizziamo la struttura dei dati dello stack per spingere i nodi intermedi sullo stack in modo da mantenere l'ordine di attraversamento.

# 4) Algoritmi di ordinamento

Gli algoritmi di ordinamento come Quicksort possono essere resi più efficienti utilizzando le strutture dati dello stack.

# 5) Torri di Hanoi

Questo è un classico problema che coinvolge n numero di dischi e tre torri e il problema riguarda lo spostamento dei dischi da una torre all'altra con la terza torre usata come intermedia.

Questo problema può essere affrontato in modo efficiente utilizzando la pila mentre spingiamo i dischi da spostare nella pila poiché la pila funge fondamentalmente da una torre utilizzata per spostare i dischi.

Conclusione

Lo stack è la struttura dati più semplice e più facile da implementare come programma. Ha utilizzato l'approccio LIFO (last in, first out), il che significa che l'elemento inserito per ultimo è quello che viene rimosso per primo. Questo perché lo stack utilizza solo un'estremità per aggiungere (push) e rimuovere (pop) gli elementi.

La struttura dei dati dello stack ha molti usi nella programmazione del software. Il più importante tra loro è la valutazione dell'espressione. La valutazione dell'espressione include anche la conversione dell'espressione da infisso a suffisso o prefisso. Coinvolge anche la valutazione dell'espressione per produrre il risultato finale.

In questo tutorial abbiamo visto l'illustrazione e l'implementazione dello stack, nonché le sue varie operazioni.

Nel nostro prossimo tutorial, impareremo in dettaglio la struttura dei dati delle code.

=> Visita qui per il corso completo C ++ degli esperti.

Lettura consigliata

^