Une pile est un type de données abstrait (ADT) dans les langages de programmation. Les piles fonctionnent sur la base du LIFO.
Elle stocke des données 1D comme un tableau, mais c'est une structure de données spécialisée qui ne permet à un utilisateur que d'ajouter, d'accéder et de supprimer le dernier élément.
- "Last in, First out"
- Super rapide (O(1)) pour ces opérations car elle est intégrée directement dans le matériel. (O(1) désigne la complexité temporelle.)
Les exemples réels de piles sont les rôtis, les vêtements, les assiettes dans le réfectoire, les feuilles de questions dans la salle d'examen, etc....
En informatique, les exemples de pile sont -
- Les appels de fonction
- Garder la trace des modifications à annuler ou des pages visitées sur un site Web pour revenir en arrière.
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