Uno stack è un tipo di dati astratto (ADT) nei linguaggi di programmazione. Gli stack funzionano sulla base del LIFO.
Conserva dati 1D proprio come un array, ma è una struttura dati specializzata che permette all'utente di aggiungere, accedere e rimuovere solo l'ultimo elemento.
- "Last in, First out"
- Super-veloce (O(1)) per queste operazioni perché è costruito direttamente nell'hardware. (O(1) denota la complessità del tempo.)
Esempi di vita reale delle pile sono Rotis, Vestiti, Piatti nella sala da pranzo, Carte delle domande nella sala degli esami, ecc....
In informatica, esempi di pile sono -
- Chiamate di funzioni
- Tenere traccia delle modifiche da annullare o delle pagine visitate in un sito web a cui tornare.
Main operations (C++ STL functions):
- s.push(value) : add an element on the top of the stack.
- s.pop () : removes the top element of the stack.
- s.top() : returns the top value without removing it.
- s.empty() : returns true if stack has no elements.
- s.size() : returns the number of elements in stack.
You cannot access a stack's elements by index. Instead, you pull elements out of the stack one at a time.
common pattern: pop each element until the stack is empty.
Some beginner programmers get confused when to use what:
In summary :
- 2D data: use 2D array
- 1D data: which element do I need to access?
- Frequent looping or middle elements : use 1D Array or Vector.
- first element : use Queue.
- last element : use Stack.
For more information visit : stack - C++ Reference
Image courtesy: google