J'ai trouvé cette description d'un TAD que je ne connaissais pas:

The data structure GrabBag is similar to a stack or a queue, but instead of the first or last element being removed on a pop or dequeue, a random element is removed on a grab. Grabbags are very useful for simulating random draws without repetition, like drawing cards from a deck or numbers in a bingo game. Consider the following ADT:

  • Insert(item e): e is inserted into the grabbag
  • Grab(): if the grabbag is not empty, return a random element from the bag
  • Size(): return how many items are in the grabbag
  • List(): return a list of all items in the grabbag
En cherchant j'ai trouvé plusieurs implantations sub-optimales en temps (trop de random) et en espace (les noeuds portent trop d'information).
Ma question :
  • c'est seulement un exercice pour étudiant ?
  • ou bien c'est un TAD intéressant qui mérite une implantation optimale (pas très difficile à réaliser)