Raisons d'utiliser un sac en Java
J'étudie actuellement les Algorithmes et les Structures de Données et pendant que je lisais la 4e édition du Livre des algorithmes, j'ai découvert la Bag data-structure avec les Stack et Queue.
Après avoir lu l'explication de cela, je ne sais toujours pas ce que je préférerais utiliser un Bag (qui n'a pas de méthode remove()) par rapport à d'autres structures de données telles que Stack, Queue, LinkedList ou un Set?
Pour autant que je puisse comprendre du livre, l'implémentation d'un Bag, est la même que pour un Stack, il suffit de remplacer le nom de push() par add() et de supprimer la méthode pop().
Donc, l'idée d'un Bag est essentiellement d'avoir la possibilité de collecter des objets, puis de parcourir les objets collectés, de vérifier si un sac est vide et de trouver le nombre d'objets qu'il contient.
Mais dans quelles circonstances je ferais mieux d'utiliser un Bag sur l'une des collections mentionnées ci-dessus? Et pourquoi un Bag n'a pas de méthode remove() fondamentalement? est-il une raison spécifique pour cela?
Merci dans avance.
1 answers
Stack est ADT de la collection d'éléments avec un ordre de suppression spécifique = LIFO (dernier entré, premier sorti), autorise les doublons,
Queue est ADT de la collection d'éléments avec un ordre de suppression spécifique = FIFO (premier entré, premier sorti), autorise les doublons,
LinkedList est la mise en œuvre de la liste,
Set est ADT de la collection d'éléments qui interdit les doublons,
Bag est ADT de la collection d'éléments qui permet les doublons.
En général, tout ce qui contient un élément est Collection.
Toute collection qui autorise les doublons est Bag, sinon c'est Set.
Tout sac qui accède aux éléments via index est List.
Le sac qui ajoute un nouvel élément après le dernier et a une méthode pour supprimer l'élément de la tête (premier index) est Queue.
Le sac qui ajoute un nouvel élément après le dernier et a une méthode pour supprimer l'élément de la queue (dernier index) est Stack.
Exemple: En Java, LinkedList est une collection, un sac, une liste, une file d'attente et vous pouvez également travailler avec elle comme c'était une pile car elle prend en charge les opérations de pile (add~addLast~push, peekLast, removeLast~pop), donc, vous pouvez l'appeler aussi stack. La raison pour laquelle elle n'implémente pas l'interface Stack est que la méthode peek est réservée par l'implémentation Queue qui récupère la tête de la liste (premier élément). Par conséquent, dans le cas de LinkedList, les "méthodes de pile" sont dérivées de Deque.
Si Bag contient remove(Object) ou non peut dépendre de l'implémentation, par exemple, vous pouvez implémenter votre propre type Bag qui prend en charge cette opération. Vous pouvez également implémenter l'opération get(int) pour accéder à l'objet sur l'index spécifié. La complexité temporelle du get(int) dépendrait de votre implémentation, par exemple, on peut implémenter Bag via linked-list afin que la complexité soit en moyenne O(n/2), l'autre via un tableau redimensionnable (array-list) avec un accès direct à l'élément via index, donc la complexité serait O(1).
Mais le principal l'idée du Bag est, qu'il permet les doublons et l'itération à travers cette collection. La prise en charge d'autres opérations utiles dépend de la décision de conception de l'implémenteur.
Lequel du type de collection à utiliser dépend de vos besoins, si les doublons ne sont pas souhaités, vous utiliseriez Set au lieu de Bag. De plus, si vous vous souciez de l'ordre de suppression, vous choisiriez Stack ou Queue qui sont essentiellement Bags avec un ordre de suppression spécifique. Vous pouvez penser à Bag comme super-type du Stack et Queue, qui étend son api par des opérations spécifiques.
La plupart du temps, il vous suffit de collecter des objets et de les traiter d'une manière ou d'une autre (itération + traitement des éléments). Vous utiliserez donc l'implémentation Bag la plus simple qui est une liste liée directionnelle.